octave-communications-common 1.2.1-1build1 / usr / share / octave / packages / communications-1.2.1 / decode.m

## Copyright (C) 2003 David Bateman
##
## This program is free software; you can redistribute it and/or modify it under
## the terms of the GNU General Public License as published by the Free Software
## Foundation; either version 3 of the License, or (at your option) any later
## version.
##
## This program is distributed in the hope that it will be useful, but WITHOUT
## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
## details.
##
## You should have received a copy of the GNU General Public License along with
## this program; if not, see <http://www.gnu.org/licenses/>.

## -*- texinfo -*-
## @deftypefn  {Function File} {@var{msg} =} decode (@var{code}, @var{n}, @var{k})
## @deftypefnx {Function File} {@var{msg} =} decode (@var{code}, @var{n}, @var{k}, @var{typ})
## @deftypefnx {Function File} {@var{msg} =} decode (@var{code}, @var{n}, @var{k}, @var{typ}, @var{opt1})
## @deftypefnx {Function File} {@var{msg} =} decode (@var{code}, @var{n}, @var{k}, @var{typ}, @var{opt1}, @var{opt2})
## @deftypefnx {Function File} {[@var{msg}, @var{err}] =} decode (@dots{})
## @deftypefnx {Function File} {[@var{msg}, @var{err}, @var{ccode}] =} decode (@dots{})
## @deftypefnx {Function File} {[@var{msg}, @var{err}, @var{ccode}, @var{cerr}] =} decode (@dots{})
##
## Top level block decoder. This function makes use of the lower level
## functions such as @code{cyclpoly}, @code{cyclgen}, @code{hammgen}, and
## @code{bchenco}. The coded message to decode is pass in @var{code}, the
## codeword length is @var{n} and the message length is @var{k}. This
## function is used to decode messages using either:
##
## @table @asis
## @item A [n,k] linear block code defined by a generator matrix
## @item A [n,k] cyclic code defined by a generator polynomial
## @item A [n,k] Hamming code defined by a primitive polynomial
## @item A [n,k] BCH code code defined by a generator polynomial
## @end table
##
## The type of coding to use is defined by the variable @var{typ}. This
## variable is a string taking one of the values
##
## @table @code
## @item  "linear"
## @itemx "linear/binary"
## A linear block code is assumed with the message @var{msg} being in a
## binary format. In this case the argument @var{opt1} is the generator
## matrix, and is required. Additionally, @var{opt2} containing the
## syndrome lookup table (see @code{syndtable}) can also be passed.
## @item  "cyclic"
## @itemx "cyclic/binary"
## A cyclic code is assumed with the message @var{msg} being in a binary
## format. The generator polynomial to use can be defined in @var{opt1}.
## The default generator polynomial to use will be
## @code{cyclpoly (@var{n}, @var{k})}. Additionally, @var{opt2} containing the
## syndrome lookup table (see @code{syndtable}) can also be passed.
## @item  "hamming"
## @itemx "hamming/binary"
## A Hamming code is assumed with the message @var{msg} being in a binary
## format. In this case @var{n} must be of an integer of the form
## @code{2^@var{m}-1}, where @var{m} is an integer. In addition @var{k}
## must be @code{@var{n}-@var{m}}. The primitive polynomial to use can
## be defined in @var{opt1}. The default primitive polynomial to use is
## the same as defined by @code{hammgen}. The variable @var{opt2} should
## not be defined.
## @item  "bch"
## @itemx "bch/binary"
## A BCH code is assumed with the message @var{msg} being in a binary
## format. The primitive polynomial to use can be defined in @var{opt2}.
## The error correction capability of the code can also be defined in
## @var{opt1}. Use the empty matrix [] to let the error correction
## capability take the default value.
## @end table
##
## In addition the argument "binary" above can be replaced with "decimal",
## in which case the message is assumed to be a decimal vector, with each
## value representing a symbol to be coded. The binary format can be in two
## forms
##
## @table @code
## @item An @var{x}-by-@var{n} matrix
## Each row of this matrix represents a symbol to be decoded
## @item A vector with length divisible by @var{n}
## The coded symbols are created from groups of @var{n} elements of this vector
## @end table
##
## The decoded message is return in @var{msg}. The number of errors encountered
## is returned in @var{err}. If the coded message format is "decimal" or a
## "binary" matrix, then @var{err} is a column vector having a length equal
## to the number of decoded symbols. If @var{code} is a "binary" vector, then
## @var{err} is the same length as @var{msg} and indicated the number of
## errors in each symbol. If the value @var{err} is positive it indicates the
## number of errors corrected in the corresponding symbol. A negative value
## indicates an uncorrectable error. The corrected code is returned in
## @var{ccode} in a similar format to the coded message @var{msg}. The
## variable @var{cerr} contains similar data to @var{err} for @var{ccode}.
##
## It should be noted that all internal calculations are performed in the
## binary format. Therefore for large values of @var{n}, it is preferable
## to use the binary format to pass the messages to avoid possible rounding
## errors. Additionally, if repeated calls to @code{decode} will be performed,
## it is often faster to create a generator matrix externally with the
## functions @code{hammgen} or @code{cyclgen}, rather than let @code{decode}
## recalculate this matrix at each iteration. In this case @var{typ} should
## be "linear". The exception to this case is BCH codes, where the required
## syndrome table is too large. The BCH decoder, decodes directly from the
## polynomial never explicitly forming the syndrome table.
##
## @seealso{encode, cyclgen, cyclpoly, hammgen, bchdeco, bchpoly, syndtable}
## @end deftypefn

function [msg, err, ccode, cerr] = decode (code, n, k, typ, opt1, opt2)

  if (nargin < 3 || nargin > 6)
    print_usage ();
  endif

  if (! (isscalar (n) && n == fix (n) && n >= 3))
    error ("decode: N must be an integer greater than 3");
  endif

  if (! (isscalar (k) && k == fix (k) && k <= n))
    error ("decode: K must be an integer less than N");
  endif

  if (nargin > 3)
    if (!ischar (typ))
      error ("decode: TYP must be a string");
    else
      ## Why the hell did matlab decide on such an ugly way of passing 2 args!
      if (strcmp (typ, "linear") || strcmp (typ, "linear/binary"))
        coding = "linear";
        msgtyp = "binary";
      elseif (strcmp (typ, "linear/decimal"))
        coding = "linear";
        msgtyp = "decimal";
      elseif (strcmp (typ, "cyclic") || strcmp (typ, "cyclic/binary"))
        coding = "cyclic";
        msgtyp = "binary";
      elseif (strcmp (typ, "cyclic/decimal"))
        coding = "cyclic";
        msgtyp = "decimal";
      elseif (strcmp (typ, "bch") || strcmp (typ, "bch/binary"))
        coding = "bch";
        msgtyp = "binary";
      elseif (strcmp (typ, "bch/decimal"))
        coding = "bch";
        msgtyp = "decimal";
      elseif (strcmp (typ, "hamming") || strcmp (typ, "hamming/binary"))
        coding = "hamming";
        msgtyp = "binary";
      elseif (strcmp (typ, "hamming/decimal"))
        coding = "hamming";
        msgtyp = "decimal";
      else
        error ("decode: invalid coding and/or message TYP '%s'", typ);
      endif
    endif
  else
    coding = "hamming";
    msgtyp = "binary";
  endif

  if (strcmp (msgtyp, "binary"))
    vecttyp = 0;
    if ((max (code(:)) > 1) || (min (code(:)) < 0))
      error ("decode: CODE must be a binary matrix");
    endif
    [ncodewords, n2] = size (code);
    len = n2*ncodewords;
    if (len/n != fix (len/n))
      error ("decode: size of CODE must be a multiple of N");
    endif
    if (min (n2, ncodewords) == 1)
      vecttyp = 1;
      ncodewords = len / n;
      code = reshape (code, n, ncodewords);
      code = code';
    elseif (n2 != n)
      error ("decode: CODE must be a matrix with N columns");
    endif
  else
    if (!isvector (code))
      error ("decode: decimal CODE type must be a vector");
    endif
    if (max (code) > 2^n-1 || min (code) < 0)
      error ("decode: all elements of CODE must be in the range [0,2^N-1]");
    endif
    ncodewords = length (code);
    code = de2bi (code(:), n);
  endif

  if (strcmp (coding, "bch"))
    if (nargin < 5 || isempty (opt1))
      tmp = bchpoly (n, k, "probe");
      t = tmp(3);
    else
      t = opt1;
    endif

    if (nargin > 5)
      [msg err ccode] = bchdeco (code, k, t, opt2);
    else
      [msg err ccode] = bchdeco (code, k, t);
    endif
    cerr = err;
  else
    if (strcmp (coding, "linear"))
      if (nargin > 4)
        gen = opt1;
        if ((size (gen, 1) != k) || (size (gen, 2) != n))
          error ("decode: generator matrix must be of size KxN");
        endif
        par = gen2par (gen);
        if (nargin > 5)
          st = opt2;
        else
          st = syndtable (par);
        endif
      else
        error ("decode: linear coding requires a generator matrix");
      endif
    elseif (strcmp (coding, "cyclic"))
      if (nargin > 4)
        [par, gen] = cyclgen (n, opt1);
      else
        [par, gen] = cyclgen (n, cyclpoly (n, k));
      endif
      if (nargin > 5)
        ## FIXME: Should we check that the generator polynomial is
        ## consistent with the syndrome table. Where is the acceleration in
        ## this case???
        st = opt2;
      else
        st = syndtable (par);
      endif
    else
      m = log2 (n + 1);
      if (! (m == fix (m) && m >= 3 && m <= 16))
        error ("decode: N must be equal to 2^M-1 for integer M in the range [3,16]");
      endif
      if (k != (n-m))
        error ("decode: K must be equal to N-M for Hamming decoder");
      endif
      if (nargin > 4)
        [par, gen] = hammgen (m, opt1);
      else
        [par, gen] = hammgen (m);
      endif
      if (nargin > 5)
        error ("decode: too many arguments for Hamming decoder");
      else
        st = syndtable (par);
      endif
    endif

    errvec = st(bi2de ((mod (par * code', 2))', "left-msb") + 1,:);
    ccode = mod (code+errvec, 2);
    err = sum (errvec');
    cerr = err;
    if (isequal (gen(:,1:k), eye (k)))
      msg = ccode(:,1:k);
    elseif (isequal (gen(:,n-k+1:n), eye (k)))
      msg = ccode(:,n-k+1:n);
    else
      error ("decode: generator matrix must be in standard form");
    endif
  endif

  if (strcmp (msgtyp, "binary") && vecttyp == 1)
    msg = msg';
    msg = msg(:);
    ccode = ccode';
    ccode = ccode(:);
    err = ones (k, 1) * err;
    err = err(:);
    cerr = ones (n, 1) * cerr;
    cerr = cerr(:);
  else
    err = err(:);
    cerr = cerr(:);
    if (strcmp (msgtyp, "decimal"))
      msg = bi2de (msg);
      ccode = bi2de (ccode);
    endif
  endif

endfunction

%% Test input validation
%!error decode ()
%!error decode (1)
%!error decode (1, 2)
%!error decode (1, 2, 3, 4, 5, 6, 7)
%!error decode (1, 2, 3)
%!error decode (1, 5, 6)
%!error decode (1, 5, 3, "invalid")