gfroots.m

数字通信第四版原书的例程

function [rt, rt_tp, alph] = gfroots(f, ord, p)
%GFROOTS Find roots for GF(P) polynomial f(X) in GF(P^M).
%       RT = GFROOTS(F) finds all roots for GF(2) polynomial F(X) in the
%       GF(2^M), where M is the degree of polynomial F(X). The default
%       polynomial generating GF(2^M) is defined in GFPRIMDF. The output
%       column vector RT contains the exponential index of the roots.
%       RT = [i, j, ..., k] means that the roots of F(X) are the elements
%       alpha^i, alpha^j, ..., alpha^k in GF(2^M). 
%
%       RT = GFROOTS(F, M) finds all roots RT for GF(2) polynomial F(X) in
%       GF(2^M). GF(2^M) is the default degree M primitive polynomial, where
%       M is a positive integer. When M is a vector in GF(2) instead of a
%       positive number, M is a primitive polynomial generated by GF(2^DEG),
%       where DEG is the degree of M(X). DEG should be greater than the
%       degree of F(X). The output roots RT is an column vector with length
%       equals the degree of F(X). The list of GF(P^M) can be found by
%       [TP, IDX] = gftuple([-1 : P^M], M, P).
%       This function outputs only the distinct roots of the polynomial F(X)
%       in the field. It cannot tell the multiple number of a root.
%
%       RT = GFROOTS(F, M, P) finds all roots RT for GF(P) polynomial F(X) in
%       GF(P^M).
%
%       [RT, RT_TUPLE] = GFROOTS(...) outputs the roots RT and the M-tuple of
%       of RT. Each row of RT_TUPLE represents the M-tuple representation of
%       RT.
%
%       [RT, RT_TUPLE, ALPH] = GFROOTS(...) outputs the M-tuple of all
%       exponential indices generated by the primitive polynomial.
%
%       See also: GFREPCOV, HAMMGEN, GFPRIMDF, GFTUPLE.

%       Wes Wang 6/27/94, 10/7/95
%       Copyright (c) 1995-96 by The MathWorks, Inc.
%       $Revision: 1.1 $  $Date: 1996/04/01 17:59:58 $

% routine check
if nargin < 1
    error('Not enough input variable in calling GFROOTS.')
elseif nargin < 2
    ord = length(f) - 1;
end;
if nargin < 3
    p = 2;
end;

if length(ord) > 1
    dim = length(ord) - 1;
else
    dim = ord;
    ord = gfprimdf(dim, p);
end;
length_alph = p^dim;

% a list of all elements in GF(P^DIM)
alph = gftuple([-1 : length_alph - 2]', ord, p);

length_f = length(f);

% all conjugates of a element are also the solution
cs = gfcosets(dim, p);
[n_cs, m_cs] = size(cs);

if f(1) == 0
    rt = -Inf;
    rt_tp = alph(1,:);
else
    rt = [];
    rt_tp = [];
end;

if rem(sum(f), p) == 0
    rt = [rt; 0];
    rt_tp = [rt_tp; alph(2,:)];
end;

i = 2;
while ((i <= n_cs) & (length(rt) < length_f - 1))
    tmp = [f(1) zeros(1, dim - 1)];
    for j = 2 : length_f
        if f(j) ~= 0
            k = cs(i, 1) * (j - 1) + 2;
            if k > length_alph
                k = rem(k - 2, length_alph - 1) + 2;
            end;
            tmp = rem(tmp + alph(k, :) * f(j), p);
        end;
    end;
    if max(tmp) == 0
        inx = cs(i, :);
        inx(isnan(inx)) = [];
        rt = [rt; inx'];
        rt_tp = [rt_tp; alph(inx+2, :)];
    end;
    i = i + 1;
end;

%--end of GFROOTS--