octave_packages/communications-1.1.1/systematize.m

   1 ## Copyright (C) 2007 Muthiah Annamalai <muthiah.annamalai@uta.edu>
   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} {}  systematize (@var{G})
  18 ##
  19 ## Given @var{G}, extract P partiy check matrix. Assume row-operations in GF(2).
  20 ## @var{G} is of size KxN, when decomposed through row-operations into a @var{I} of size KxK
  21 ## identity matrix, and a parity check matrix @var{P} of size Kx(N-K).
  22 ##
  23 ## Most arbitrary code with a given generator matrix @var{G}, can be converted into its
  24 ## systematic form using this function.
  25 ##
  26 ## This function returns 2 values, first is default being @var{Gx} the systematic version of
  27 ## the @var{G} matrix, and then the parity check matrix @var{P}.
  28 ##
  29 ## @example
  30 ## @group
  31 ##   G=[1 1 1 1; 1 1 0 1; 1 0 0 1];
  32 ##   [Gx,P]=systematize(G);
  33 ##
  34 ##   Gx = [1 0 0 1; 0 1 0 0; 0 0 1 0];
  35 ##   P = [1 0 0];
  36 ## @end group
  37 ## @end example
  38 ##
  39 ## @end deftypefn
  40 ## @seealso{bchpoly,biterr}
  41 function [G,P]=systematize(G)
  42     if ( nargin < 1 )
  43          print_usage();
  44     end
  45
  46     [K,N]=size(G);
  47
  48     if ( K >= N )
  49          error('G matrix must be ordered as KxN, with K < N');
  50     end
  51
  52     %
  53     % gauss-jordan echelon formation,
  54     % and then back-operations to get I of size KxK
  55     % remaining is the P matrix.
  56     %
  57
  58     for row=1:K
  59
  60     %
  61     %pick a pivot for this row, by finding the
  62     %first of remaining rows that have non-zero element
  63     %in the pivot.
  64     %
  65
  66     found_pivot=0;
  67     if ( G(row,row) > 0 )
  68        found_pivot=1;
  69     else
  70      %
  71      % next step of Gauss-Jordan, you need to
  72      % re-sort the remaining rows, such that their
  73      % pivot element is non-zero.
  74      %
  75      for idx=row+1:K
  76         if ( G(idx,row) > 0 )
  77             tmp=G(row,:);
  78             G(row,:)=G(idx,:);
  79             G(idx,:)=tmp;
  80             found_pivot=1;
  81             break;
  82         end
  83      end
  84     end
  85
  86     %
  87     %some linearly dependent problems:
  88     %
  89     if ( ~found_pivot )
  90         error('cannot systematize matrix G');
  91         return
  92     end
  93
  94     %
  95     % Gauss-Jordan method:
  96     % pick pivot element, then remove it
  97     % from the rest of the rows.
  98     %
  99     for idx=row+1:K
 100         if( G(idx,row) > 0 )
 101             G(idx,:)=mod(G(idx,:)+G(row,:),2);
 102         end
 103     end
 104
 105     end
 106
 107     %
 108     % Now work-backward.
 109     %
 110     for row=K:-1:2
 111         for idx=row-1:-1:1
 112             if( G(idx,row) > 0 )
 113                 G(idx,:)=mod(G(idx,:)+G(row,:),2);
 114             end
 115         end
 116     end
 117
 118     %I=G(:,1:K);
 119     P=G(:,K+1:end);
 120     return;
 121 end