This file is indexed.

/usr/share/octave/packages/communications-1.2.0/poly2trellis.m is in octave-communications-common 1.2.0-2.

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
## Copyright (C) 2012 Mike Miller <mtmiller@ieee.org>
##
## 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{t} =} poly2trellis (@var{m}, @var{g})
##
## Convert convolutional code generator polynomials into trellis form.
##
## The arguments @var{m} and @var{g} together describe a rate k/n feedforward
## convolutional encoder.  The output @var{t} is a trellis structure describing
## the same encoder with the fields listed below.
##
## The vector @var{m} is a k-by-1 array containing the lengths of each of the
## shift registers for the k input bits to the encoder.
##
## The matrix @var{g} is a k-by-n octal-value matrix describing the generation
## of each of the n outputs from each of the k inputs.  For a particular entry
## of @var{g}, the least-significant bit corresponds to the most-delayed input
## bit in the kth shift-register.
##
## The returned trellis structure contains the following fields:
##
## @table @samp
## @item numInputSymbols
## The number of k-bit input symbols possible, i.e. 2^k.
##
## @item numOutputSymbols
## The number of n-bit output symbols possible, i.e. 2^n.
##
## @item numStates
## The number of states in the trellis.
##
## @item nextStates
## The state transition table for the trellis.  The ith row contains the indices
## of the states reachable from the (i-1)th state for each possible input
## symbol.
##
## @item outputs
## A table of octal-encoded output values for the trellis.  The ith row contains
## values representing the output symbols produced in the (i-1)th state for each
## possible input symbol.
## @end table
##
## Input symbols, output symbols, and encoder states are all interpreted with
## the lowest indices being the most significant bits.
##
## References:
##
##     [1] S. Lin and D. J. Costello, "Convolutional codes," in @cite{Error
##     Control Coding}, 2nd ed. Upper Saddle River, NJ: Pearson, 2004,
##     ch. 11, pp. 453-513.
##
## @seealso{istrellis}
## @end deftypefn

function t = poly2trellis (m, g)

  if (nargin != 2)
    print_usage ();
  endif

  ## Notation agrees with Lin & Costello for the most part:
  ## m = length of each modulo-2 adder
  ##   = 1 + nu(:) = one more than length of each shift register
  ## g = generator sequences, k-by-n
  ## k = bits per input symbol = number of shift registers
  ## n = bits per output symbol = number of modulo-2 adders
  [nr, k] = size (m);
  if (nr != 1)
    error ("poly2trellis: M must be a 1-by-k positive integer row vector");
  endif
  if (! (all (m == fix (m)) && all (m > 0)))
    error ("poly2trellis: M must be a 1-by-k positive integer row vector");
  endif

  [nr, n] = size (g);
  if (nr != k)
    error ("poly2trellis: G must be a k-by-n octal matrix");
  endif

  ## Convert g to decimal, let oct2dec validate the octal values
  g = oct2dec (g);

  ## Check the ranges of the generators
  ## nu = total number of linear shift registers for all k
  nu = sum (m) - k;

  ## Number of states and input symbols needed to capture the state machine
  nstates  = 2^nu;
  ninputs  = 2^k;
  noutputs = 2^n;

  t = struct ("numInputSymbols",  ninputs,
              "numOutputSymbols", noutputs,
              "numStates",        nstates,
              "nextStates",       zeros (nstates, ninputs),
              "outputs",          zeros (nstates, ninputs));

  ## Split state indices into values for each distinct shift register.
  ## Also precalculate new bit position for each shift register and the left
  ## shifts required to reassemble the states into one state value.
  ##
  ## Conventions:
  ## - Each shift register shifts to the right, MSB-to-LSB
  ## - The MSB of each shift register is the newest input
  ## - The MSBs of the state represent the k=1 shift register
  statebits = de2bi (0:nstates - 1);
  states = zeros (nstates, k);
  newbit = zeros (1, k);
  shifts = zeros (1, k);
  offset = 1;
  for i = 1:k
    nu_i = m(i) - 1;
    if (nu_i > 0)
      states(:,i) = bi2de (statebits(:, offset:offset + nu_i - 1));
    endif
    newbit(i) = bitshift (1, nu_i);
    shifts(i) = offset - 1;
    offset += nu_i;

    if (any (g(i,:) >= 2^m(i)))
      error ("poly2trellis: code size is greater than constraint length");
    endif
    if (all (g(i,:) < 2^nu_i) || !any (mod (g(i,:), 2)))
      error ("poly2trellis: code size is less than constraint length");
    endif
  endfor

  ## Generate conversion list of all possible output octal values
  outputs = str2num (dec2base (0:noutputs - 1, 8));

  ## Walk the trellis, each row index is state, each column index is input
  for s = 1:nstates

    for i = 1:k
      ## For each next input bit [0,1] calculate inputs to modulo-2 adder
      ## and the next state for the ith linear shift register, left-shifted
      ## to be combined into the total state.
      state = states(s,i) + [0; newbit(i)];
      next = bitshift (bitshift (state, -1), shifts(i));

      ## Calculate the modulo-2 sum of the state plus input for each n for
      ## this particular shift register.
      ## The MSB of the output represents the n=1 generator(s)
      out = [0; 0];
      for adder = 1:n
        val = mod (sum (de2bi (bitand (g(i, adder), state)), 2), 2);
        out += bitshift (val, n - adder);
      endfor

      ## Accumulate contributions to the trellis for this shift register.
      ## The contribution to each input symbol depends on whether the
      ## (k-i)th bit is 0 or 1.
      bitpos = k - i;
      for symbol = 1:ninputs
        idx = bitget (symbol - 1, bitpos + 1) + 1;
        t.nextStates(s, symbol) += next(idx);
        t.outputs(s, symbol) = bitxor (t.outputs(s, symbol), out(idx));
      endfor

    endfor

    ## Convert output values to octal representation
    t.outputs(s,:) = outputs(t.outputs(s,:) + 1);

  endfor

endfunction

%% Test the simple (2,1,3) encoder from Lin & Costello example 11.1
%!test
%! T = struct ("numInputSymbols",  2,
%!             "numOutputSymbols", 4,
%!             "numStates",        8,
%!             "nextStates",       [0 4; 0 4; 1 5; 1 5; 2 6; 2 6; 3 7; 3 7],
%!             "outputs",          [0 3; 3 0; 3 0; 0 3; 1 2; 2 1; 2 1; 1 2]);
%! t = poly2trellis (4, [13 17]);
%! assert (t, T)
%! assert (istrellis (t), true)

%% Test input validation
%!error poly2trellis ()
%!error poly2trellis (1, 2, 3)
%!error poly2trellis (1)
%!error poly2trellis (2, 8)
%!error poly2trellis (0, 0)
%!error poly2trellis (2, 0)
%!error poly2trellis (2, 2)
%!error poly2trellis (2, 7)