octave_packages/communications-1.1.1/rsgenpoly.m

   1 ## Copyright (C) 2003 David Bateman
   2 ##
   3 ## This program is free software; you can redistribute it and/or modify it under
   4 ## the terms of the GNU General Public License as published by the Free Software
   5 ## Foundation; either version 3 of the License, or (at your option) any later
   6 ## version.
   7 ##
   8 ## This program is distributed in the hope that it will be useful, but WITHOUT
   9 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10 ## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  11 ## details.
  12 ##
  13 ## You should have received a copy of the GNU General Public License along with
  14 ## this program; if not, see <http://www.gnu.org/licenses/>.
  15
  16 ## -*- texinfo -*-
  17 ## @deftypefn {Function File} {@var{g} = } rsgenpoly (@var{n},@var{k})
  18 ## @deftypefnx {Function File} {@var{g} = } rsgenpoly (@var{n},@var{k},@var{p})
  19 ## @deftypefnx {Function File} {@var{g} = } rsgenpoly (@var{n},@var{k},@var{p},@var{b},@var{s})
  20 ## @deftypefnx {Function File} {@var{g} = } rsgenpoly (@var{n},@var{k},@var{p},@var{b})
  21 ## @deftypefnx {Function File} {[@var{g}, @var{t}] = } rsgenpoly (@var{...})
  22 ##
  23 ## Creates a generator polynomial for a Reed-Solomon coding with message
  24 ## length of @var{k} and codelength of @var{n}. @var{n} must be greater
  25 ## than @var{k} and their difference must be even. The generator polynomial
  26 ## is returned on @var{g} as a polynomial over the Galois Field GF(2^@var{m})
  27 ## where @var{n} is equal to @code{2^@var{m}-1}. If @var{m} is not integer
  28 ## the next highest integer value is used and a generator for a shorten
  29 ## Reed-Solomon code is returned.
  30 ##
  31 ## The elements of @var{g} represent the coefficients of the polynomial in
  32 ## descending order. If the length of @var{g} is lg, then the generator
  33 ## polynomial is given by
  34 ## @iftex
  35 ## @tex
  36 ## $$
  37 ## g_0 x^{lg-1} + g_1 x^{lg-2} + \cdots + g_{lg-1} x + g_lg.
  38 ## $$
  39 ## @end tex
  40 ## @end iftex
  41 ## @ifinfo
  42 ##
  43 ## @example
  44 ## @var{g}(0) * x^(lg-1) + @var{g}(1) * x^(lg-2) + ... + @var{g}(lg-1) * x + @var{g}(lg).
  45 ## @end example
  46 ## @end ifinfo
  47 ##
  48 ## If @var{p} is defined then it is used as the primitive polynomial of the
  49 ## the Galois Field GF(2^@var{m}). The default primitive polynomial will
  50 ## be used if @var{p} is equal to [].
  51 ##
  52 ## The variables @var{b} and @var{s} determine the form of the generator
  53 ## polynomial in the following manner.
  54 ## @iftex
  55 ## @tex
  56 ## $$
  57 ## g = (x - A^{bs}) (x - A^{(b+1)s})  \cdots (x - A ^{(b+2t-1)s}).
  58 ## $$
  59 ## @end tex
  60 ## @end iftex
  61 ## @ifinfo
  62 ##
  63 ## @example
  64 ## @var{g} = (@var{x} - A^(@var{b}*@var{s})) * (@var{x} - A^((@var{b}+1)*@var{s})) * ... * (@var{x} - A^((@var{b}+2*@var{t}-1)*@var{s})).
  65 ## @end example
  66 ## @end ifinfo
  67 ##
  68 ## where @var{t} is @code{(@var{n}-@var{k})/2}, and A is the primitive element
  69 ## of the Galois Field. Therefore @var{b} is the first consecutive root of the
  70 ## generator polynomial and @var{s} is the primitive element to generate the
  71 ## the polynomial roots.
  72 ##
  73 ## If requested the variable @var{t}, which gives the error correction
  74 ## capability of the the Reed-Solomon code
  75 ## @end deftypefn
  76 ## @seealso{gf,rsenc,rsdec}
  77
  78 function [g, t] = rsgenpoly(n, k, _prim, _b, _s)
  79
  80   if ((nargin < 2) || (nargin > 5))
  81     error ("usage: [g, t] = rsgenpoly(n, k, p, b, s)");
  82   endif
  83
  84   if (!isscalar(n) || (n < 3) || ((n - floor(n)) != 0))
  85     error ("rsgenpoly: invalid codeword length");
  86   endif
  87
  88   if (!isscalar(k) || (k < 1) || ((k- floor(k)) != 0))
  89     error ("rsgenpoly: invalid message length");
  90   endif
  91
  92   if (((n-k)/2 - floor((n-k)/2)) != 0)
  93     error ("rsgenpoly: difference of codeword and message lengths must be even");
  94   endif
  95
  96   m = ceil(log2(n+1));
  97   ## Adjust n and k if n not equal to 2^m-1
  98   dif = 2^m - 1 - n;
  99   n = n + dif;
 100   k = k + dif;
 101
 102   prim = 0;
 103   if (nargin > 2)
 104     if (isempty(_prim))
 105       prim = 0;
 106     else
 107       prim = _prim;
 108     endif
 109   endif
 110
 111   if (!isscalar(prim) || (prim<0) || ((prim - floor(prim)) != 0))
 112     error ("rsgenpoly: primitive polynomial must use integer representation");
 113   endif
 114
 115   if (prim != 0)
 116     if (!isprimitive(prim))
 117       error ("rsgenpoly: polynomial is not primitive");
 118     endif
 119
 120     if ((prim < 2^m) || (prim > 2^(m+1)))
 121       error ("rsgenpoly: invalid order of the primitive polynomial");
 122     endif
 123   endif
 124
 125   b = 1;
 126   if (nargin > 3)
 127     b = _b;
 128   endif
 129
 130   if (!isscalar(b) || (b < 0) || ((b - floor(b)) != 0))
 131     error ("rsgenpoly: invalid value of b");
 132   endif
 133
 134   s = 1;
 135   if (nargin > 4)
 136     s = _s;
 137   endif
 138
 139   if (!isscalar(s) || (s < 0) || ((s - floor(s)) != 0))
 140     error ("rsgenpoly: invalid value of s");
 141   endif
 142
 143   alph = gf(2, m, prim);
 144   t = (n - k) / 2;
 145
 146   g = gf(1, m, prim);
 147   for i= 1:2*t
 148     g = conv(g, gf([1,alph^((b+i-1)*s)], m, prim));
 149   end
 150
 151 endfunction