octave_packages/communications-1.1.1/decode.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{msg} =} decode (@var{code},@var{n},@var{k})
  18 ## @deftypefnx {Function File} {@var{msg} =} decode (@var{code},@var{n},@var{k},@var{typ})
  19 ## @deftypefnx {Function File} {@var{msg} =} decode (@var{code},@var{n},@var{k},@var{typ},@var{opt1})
  20 ## @deftypefnx {Function File} {@var{msg} =} decode (@var{code},@var{n},@var{k},@var{typ},@var{opt1},@var{opt2})
  21 ## @deftypefnx {Function File} {[@var{msg}, @var{err}] =} decode (@var{...})
  22 ## @deftypefnx {Function File} {[@var{msg}, @var{err}, @var{ccode}] =} decode (@var{...})
  23 ## @deftypefnx {Function File} {[@var{msg}, @var{err}, @var{ccode}, @var{cerr}] =} decode (@var{...})
  24 ##
  25 ## Top level block decoder. This function makes use of the lower level
  26 ## functions such as @dfn{cyclpoly}, @dfn{cyclgen}, @dfn{hammgen}, and
  27 ## @dfn{bchenco}. The coded message to decode is pass in @var{code}, the
  28 ## codeword length is @var{n} and the message length is @var{k}. This
  29 ## function is used to decode messages using either:
  30 ##
  31 ## @table @asis
  32 ## @item A [n,k] linear block code defined by a generator matrix
  33 ## @item A [n,k] cyclic code defined by a generator polynomial
  34 ## @item A [n,k] Hamming code defined by a primitive polynomial
  35 ## @item A [n,k] BCH code code defined by a generator polynomial
  36 ## @end table
  37 ##
  38 ## The type of coding to use is defined by the variable @var{typ}. This
  39 ## variable is a string taking one of the values
  40 ##
  41 ## @table @code
  42 ## @item 'linear' or 'linear/binary'
  43 ## A linear block code is assumed with the message @var{msg} being in a
  44 ## binary format. In this case the argument @var{opt1} is the generator
  45 ## matrix, and is required. Additionally, @var{opt2} containing the
  46 ## syndrome lookup table (see @dfn{syndtable}) can also be passed.
  47 ## @item 'cyclic' or 'cyclic/binary'
  48 ## A cyclic code is assumed with the message @var{msg} being in a binary
  49 ## format. The generator polynomial to use can be defined in @var{opt1}.
  50 ## The default generator polynomial to use will be
  51 ## @dfn{cyclpoly(@var{n},@var{k})}. Additionally, @var{opt2} containing the
  52 ## syndrome lookup table (see @dfn{syndtable}) can also be passed.
  53 ## @item 'hamming' or 'hamming/binary'
  54 ## A Hamming code is assumed with the message @var{msg} being in a binary
  55 ## format. In this case @var{n} must be of an integer of the form
  56 ## @code{2^@var{m}-1}, where @var{m} is an integer. In addition @var{k}
  57 ## must be @code{@var{n}-@var{m}}. The primitive polynomial to use can
  58 ## be defined in @var{opt1}. The default primitive polynomial to use is
  59 ## the same as defined by @dfn{hammgen}. The variable @var{opt2} should
  60 ## not be defined.
  61 ## @item 'bch' or 'bch/binary'
  62 ## A BCH code is assumed with the message @var{msg} being in a binary
  63 ## format. The primitive polynomial to use can be defined in @var{opt2}.
  64 ## The error correction capability of the code can also be defined in
  65 ## @var{opt1}. Use the empty matrix [] to let the error correction
  66 ## capability take the default value.
  67 ## @end table
  68 ##
  69 ## In addition the argument 'binary' above can be replaced with 'decimal',
  70 ## in which case the message is assumed to be a decimal vector, with each
  71 ## value representing a symbol to be coded. The binary format can be in two
  72 ## forms
  73 ##
  74 ## @table @code
  75 ## @item An @var{x}-by-@var{n} matrix
  76 ## Each row of this matrix represents a symbol to be decoded
  77 ## @item A vector with length divisible by @var{n}
  78 ## The coded symbols are created from groups of @var{n} elements of this vector
  79 ## @end table
  80 ##
  81 ## The decoded message is return in @var{msg}. The number of errors encountered
  82 ## is returned in @var{err}. If the coded message format is 'decimal' or a
  83 ## 'binary' matrix, then @var{err} is a column vector having a length equal
  84 ## to the number of decoded symbols. If @var{code} is a 'binary' vector, then
  85 ## @var{err} is the same length as @var{msg} and indicated the number of
  86 ## errors in each symbol. If the value @var{err} is positive it indicates the
  87 ## number of errors corrected in the corresponding symbol. A negative value
  88 ## indicates an uncorrectable error. The corrected code is returned in
  89 ## @var{ccode} in a similar format to the coded message @var{msg}. The
  90 ## variable @var{cerr} contains similar data to @var{err} for @var{ccode}.
  91 ##
  92 ## It should be noted that all internal calculations are performed in the
  93 ## binary format. Therefore for large values of @var{n}, it is preferable
  94 ## to use the binary format to pass the messages to avoid possible rounding
  95 ## errors. Additionally, if repeated calls to @dfn{decode} will be performed,
  96 ## it is often faster to create a generator matrix externally with the
  97 ## functions @dfn{hammgen} or @dfn{cyclgen}, rather than let @dfn{decode}
  98 ## recalculate this matrix at each iteration. In this case @var{typ} should
  99 ## be 'linear'. The exception to this case is BCH codes, where the required
 100 ## syndrome table is too large. The BCH decoder, decodes directly from the
 101 ## polynomial never explicitly forming the syndrome table.
 102 ##
 103 ## @end deftypefn
 104 ## @seealso{encode,cyclgen,cyclpoly,hammgen,bchdeco,bchpoly,syndtable}
 105
 106 function [msg, err, ccode, cerr] = decode(code, n, k, typ, opt1, opt2)
 107
 108   if ((nargin < 3) || (nargin > 6))
 109     usage ("[msg, err, ccode] = decode (code, n, k [, typ [, opt1 [, opt2]]])");
 110   endif
 111
 112   if (!isscalar(n) || (n != floor(n)) || (n < 3))
 113     error ("decode: codeword length must be an integer greater than 3");
 114   endif
 115
 116   if (!isscalar(k) || (k != floor(k)) || (k > n))
 117     error ("decode: message length must be an integer less than codeword length");
 118   endif
 119
 120   if (nargin > 3)
 121     if (!ischar(typ))
 122       error ("decode: type argument must be a string");
 123     else
 124       ## Why the hell did matlab decide on such an ugly way of passing 2 args!
 125       if (strcmp(typ,"linear") || strcmp(typ,"linear/binary"))
 126               coding = "linear";
 127               msgtyp = "binary";
 128       elseif (strcmp(typ,"linear/decimal"))
 129               coding = "linear";
 130               msgtyp = "decimal";
 131       elseif (strcmp(typ,"cyclic") || strcmp(typ,"cyclic/binary"))
 132               coding = "cyclic";
 133               msgtyp = "binary";
 134       elseif (strcmp(typ,"cyclic/decimal"))
 135               coding = "cyclic";
 136               msgtyp = "decimal";
 137       elseif (strcmp(typ,"bch") || strcmp(typ,"bch/binary"))
 138               coding = "bch";
 139               msgtyp = "binary";
 140       elseif (strcmp(typ,"bch/decimal"))
 141               coding = "bch";
 142               msgtyp = "decimal";
 143       elseif (strcmp(typ,"hamming") || strcmp(typ,"hamming/binary"))
 144               coding = "hamming";
 145               msgtyp = "binary";
 146       elseif (strcmp(typ,"hamming/decimal"))
 147               coding = "hamming";
 148               msgtyp = "decimal";
 149       else
 150               error ("decode: unrecognized coding and/or message type");
 151       endif
 152     endif
 153   else
 154     coding = "hamming";
 155     msgtyp = "binary";
 156   endif
 157
 158   if (strcmp(msgtyp,"binary"))
 159     vecttyp = 0;
 160     if ((max(code(:)) > 1) || (min(code(:)) < 0))
 161       error ("decode: illegal value in message");
 162     endif
 163     [ncodewords, n2] = size(code);
 164     len = n2*ncodewords;
 165     if ((n * floor(len/n)) != len)
 166       error ("decode: coded message of incorrect length");
 167     endif
 168     if (min(n2,ncodewords) == 1)
 169       vecttyp = 1;
 170       ncodewords = len / n;
 171       code = reshape(code,n,ncodewords);
 172       code = code';
 173     elseif (n2 != n)
 174       error ("decode: coded message matrix must be n columns wide");
 175     endif
 176   else
 177     if (!isvector(code))
 178       error ("decode: decimally decoded message must be a vector");
 179     endif
 180     if ((max(code) > 2^n-1) || (min(code) < 0))
 181       error ("decode: illegal value in message");
 182     endif
 183     ncodewords = length(code);
 184     code = de2bi(code(:),n);
 185   endif
 186
 187   if (strcmp(coding,"bch"))
 188     if ((nargin < 5) || (isempty(opt1)))
 189       tmp = bchpoly(n, k,"probe");
 190       t = tmp(3);
 191     else
 192       t = opt1;
 193     endif
 194
 195     if (nargin > 5)
 196       [msg err ccode] = bchdeco(code,k,t,opt2);
 197     else
 198       [msg err ccode] = bchdeco(code,k,t);
 199     endif
 200     cerr = err;
 201   else
 202     if (strcmp(coding,"linear"))
 203       if (nargin > 4)
 204               gen = opt1;
 205               if ((size(gen,1) != k) || (size(gen,2) != n))
 206                 error ("decode: generator matrix is in incorrect form");
 207               endif
 208               par = gen2par(gen);
 209               if (nargin > 5)
 210                 st = opt2;
 211               else
 212                 st = syndtable(par);
 213               endif
 214       else
 215               error ("decode: linear coding must supply the generator matrix");
 216       endif
 217     elseif (strcmp(coding,"cyclic"))
 218       if (nargin > 4)
 219               [par, gen] = cyclgen(n,opt1);
 220       else
 221               [par, gen] = cyclgen(n,cyclpoly(n,k));
 222       endif
 223       if (nargin > 5)
 224               ## XXX FIXME XXX Should we check that the generator polynomial is
 225               ## consistent with the syndrome table. Where is the acceleration in
 226               ## this case???
 227               st = opt2;
 228       else
 229               st = syndtable(par);
 230       endif
 231     else
 232       m = log2(n + 1);
 233       if ((m != floor(m)) || (m < 3) || (m > 16))
 234               error ("decode: codeword length must be of the form '2^m-1' with integer m");
 235       endif
 236       if (k != (n-m))
 237               error ("decode: illegal message length for hamming code");
 238       endif
 239       if (nargin > 4)
 240               [par, gen] = hammgen(m, opt1);
 241       else
 242               [par, gen] = hammgen(m);
 243       endif
 244       if (nargin > 5)
 245               error ("decode: illegal call for hamming coding");
 246       else
 247               st = syndtable(par);
 248       endif
 249     endif
 250
 251     errvec = st(bi2de((mod(par * code',2))',"left-msb")+1,:);
 252     ccode = mod(code+errvec,2);
 253     err = sum(errvec');
 254     cerr = err;
 255     if (isequal(gen(:,1:k),eye(k)))
 256       msg = ccode(:,1:k);
 257     elseif (isequal(gen(:,n-k+1:n),eye(k)))
 258       msg = ccode(:,n-k+1:n);
 259     else
 260       error ("decode: generator matrix must be in standard form");
 261     endif
 262   endif
 263
 264   if (strcmp(msgtyp,"binary") && (vecttyp == 1))
 265     msg = msg';
 266     msg = msg(:);
 267     ccode = ccode';
 268     ccode = ccode(:);
 269     err = ones(k,1) * err;
 270     err = err(:);
 271     cerr = ones(n,1) * cerr;
 272     cerr = cerr(:);
 273   else
 274     err = err(:);
 275     cerr = cerr(:);
 276     if (strcmp(msgtyp,"decimal"))
 277       msg = bi2de(msg);
 278       ccode = bi2de(ccode);
 279     endif
 280   endif
 281
 282 endfunction