/usr/share/octave/packages/communications-1.2.1/bchpoly.m is in octave-communications-common 1.2.1-1build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 | ## 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{p} =} bchpoly ()
## @deftypefnx {Function File} {@var{p} =} bchpoly (@var{n})
## @deftypefnx {Function File} {@var{p} =} bchpoly (@var{n}, @var{k})
## @deftypefnx {Function File} {@var{p} =} bchpoly (@var{prim}, @var{k})
## @deftypefnx {Function File} {@var{p} =} bchpoly (@var{n}, @var{k}, @var{prim})
## @deftypefnx {Function File} {@var{p} =} bchpoly (@dots{}, @var{probe})
## @deftypefnx {Function File} {[@var{p}, @var{f}] =} bchpoly (@dots{})
## @deftypefnx {Function File} {[@var{p}, @var{f}, @var{c}] =} bchpoly (@dots{})
## @deftypefnx {Function File} {[@var{p}, @var{f}, @var{c}, @var{par}] =} bchpoly (@dots{})
## @deftypefnx {Function File} {[@var{p}, @var{f}, @var{c}, @var{par}, @var{t}] =} bchpoly (@dots{})
##
## Calculates the generator polynomials for a BCH coder. Called with no input
## arguments @code{bchpoly} returns a list of all of the valid BCH codes for
## the codeword length 7, 15, 31, 63, 127, 255 and 511. A three column matrix
## is returned with each row representing a separate valid BCH code. The first
## column is the codeword length, the second the message length and the third
## the error correction capability of the code.
##
## Called with a single input argument, @code{bchpoly} returns the valid BCH
## codes for the specified codeword length @var{n}. The output format is the
## same as above.
##
## When called with two or more arguments, @code{bchpoly} calculates the
## generator polynomial of a particular BCH code. The generator polynomial
## is returned in @var{p} as a vector representation of a polynomial in
## GF(2). The terms of the polynomial are listed least-significant term
## first.
##
## The desired BCH code can be specified by its codeword length @var{n}
## and its message length @var{k}. Alternatively, the primitive polynomial
## over which to calculate the polynomial can be specified as @var{prim}.
## If a vector representation of the primitive polynomial is given, then
## @var{prim} can be specified as the first argument of two arguments,
## or as the third argument. However, if an integer representation of the
## primitive polynomial is used, then the primitive polynomial must be
## specified as the third argument.
##
## When called with two or more arguments, @code{bchpoly} can also return the
## factors @var{f} of the generator polynomial @var{p}, the cyclotomic coset
## for the Galois field over which the BCH code is calculated, the parity
## check matrix @var{par} and the error correction capability @var{t}. It
## should be noted that the parity check matrix is calculated with
## @code{cyclgen} and limitations in this function means that the parity
## check matrix is only available for codeword length up to 63. For
## codeword length longer than this @var{par} returns an empty matrix.
##
## With a string argument @var{probe} defined, the action of @code{bchpoly}
## is to calculate the error correcting capability of the BCH code defined
## by @var{n}, @var{k} and @var{prim} and return it in @var{p}. This is
## similar to a call to @code{bchpoly} with zero or one argument, except that
## only a single code is checked. Any string value for @var{probe} will
## force this action.
##
## In general the codeword length @var{n} can be expressed as
## @code{2^@var{m}-1}, where @var{m} is an integer. However, if
## [@var{n},@var{k}] is a valid BCH code, then a shortened BCH code of
## the form [@var{n}-@var{x},@var{k}-@var{x}] can be created with the
## same generator polynomial
##
## @seealso{cyclpoly, encode, decode, cosets}
## @end deftypefn
function [p, f, c, par, t] = bchpoly (nn, k, varargin)
if (nargin < 0 || nargin > 4)
print_usage ();
endif
probe = 0;
prim = 0; ## Set to zero to use default primitive polynomial
if (nargin == 0)
m = [3:9];
n = 2.^m - 1;
nn = n;
elseif (isscalar (nn))
m = ceil (log2 (nn+1));
n = 2.^m - 1;
if (! (n == fix (n) && n >= 7 && m == fix (m)))
error ("bchpoly: N must be a integer greater than 3");
endif
else
prim = bi2de (n);
if (!isprimitive (prim))
error ("bchpoly: PRIM must be a primitive polynomial of GF(2^M)");
endif
m = length (n) - 1;
n = 2^m - 1;
endif
if (nargin > 1 && ! (isscalar (k) && k == fix (k) && k <= n))
error ("bchpoly: K must be an integer less than N");
endif
for i = 1:length (varargin)
arg = varargin{i};
if (ischar (arg))
probe = 1;
if (nargout > 1)
error ("bchpoly: only one output argument allowed when probing valid codes");
endif
else
if (prim != 0)
error ("bchpoly: primitive polynomial already defined");
endif
prim = arg;
if (!isscalar (prim))
prim = bi2de (prim);
endif
if (! (prim == fix (prim) && prim >= 2^m && prim <= 2^(m+1)
&& isprimitive (prim)))
error ("bchpoly: PRIM must be a primitive polynomial of GF(2^M)");
endif
endif
endfor
## Am I using the right algo to calculate the correction capability?
if (nargin < 2)
if (nargout > 1)
error ("bchpoly: only one output argument allowed when probing valid codes");
endif
p = [];
for ni = 1:length (n)
c = cosets (m(ni), prim);
nc = length (c);
fc = zeros (1, nc);
f = [];
for t = 1:floor (n(ni)/2)
for i = 1:nc
if (fc(i) != 1)
cl = log (c{i});
for j = 2*(t-1)+1:2*t
if (find (cl == j))
f = [f, c{i}.x];
fc(i) = 1;
break;
endif
endfor
endif
endfor
k = nn(ni) - length (f);
if (k < 2)
break;
endif
if (!isempty (p) && (k == p(size (p, 1),2)))
p(size (p, 1),:) = [nn(ni), k, t];
else
p = [p; [nn(ni), k, t]];
endif
endfor
endfor
else
c = cosets (m, prim);
nc = length (c);
fc = zeros (1, nc);
f = [];
fl = 0;
f0 = [];
f1 = [];
t = 0;
do
t++;
f0 = f1;
for i = 1:nc
if (fc(i) != 1)
cl = log (c{i});
for j = 2*(t-1)+1:2*t
if (find (cl == j))
f1 = [f1, c{i}.x];
fc(i) = 1;
ptmp = gf ([c{i}(1), 1], m, prim);
for l = 2:length (c{i})
ptmp = conv (ptmp, [c{i}(l), 1]);
endfor
f = [f; [ptmp.x, zeros(1, m - length (ptmp) + 1)]];
fl = fl + length (ptmp);
break;
endif
endfor
endif
endfor
until (length (f1) > nn - k)
t--;
if (nn - length (f0) != k)
error ("bchpoly: could not find valid generator polynomial for parameters");
endif
if (probe)
p = [nn, k, t];
else
## Have to delete a line from the list of minimum polynomials
## since we've gone one past in calculating f1 above to be
## sure or the error correcting capability
f = f(1:size (f, 1) - 1,:);
p = gf ([f0(1), 1], m, prim);
for i = 2:length (f0)
p = conv (p, [f0(i), 1]);
endfor
p = p.x;
if (nargout > 3)
if (n > 64)
warning ("bchpoly: could not create parity matrix");
par = [];
else
par = cyclgen (n, p);
endif
endif
endif
endif
endfunction
%% Test input validation
%!error bchpoly (1)
%!error bchpoly (1, 2, 3, 4, 5)
%!error bchpoly (5, 10)
|