On trellis structures for Reed-Muller codes (Q1971064)

Trellises for Reed-Muller (RM) codes are studied. A trellis \(T\) of a linear code \(C\) is a directed graph with the vertices placed at ordered depths. Edges of \(T\) join vertices at adjacent depths and paths that pass through one vertex at each depth are in one-to-one correspondence with codewords of \(C\). Trellises with low vertex count at each depth are of interest. A code has a unique trellis, the minimal trellis, which simultaneously minimises the number of vertices at each depth. Trellises of the \(m\)th order RM codes are of interest in this work. Equivalent codes can have different trellises and the bit order in the codes is of importance. Section 2 of the paper characterises the local trellis behaviour of a length \(2^m\) RM code whose bit-order is determined by any monomial order of \(F_2^m\). It is shown that a total degree order is as bad as the extended cyclic bit-order with regard to state complexity. The description of the local trellis behaviour described is used to give some new and simpler proofs of some known results. A generator matrix of \(C\) that gives the minimal trellis is called a minimal span generator matrix. Section 3 of the paper gives a general form for a minimal-span generator matrix for the family of RM codes with the standard bit-order. A subtrellis of \(T\) is a trellis whose paths are a subset of the set of paths though \(T\). Subtrellises are parallel if they contain no vertices in common other than the initial and final vertex. Sections 4 and 5 use the general form minimal-span generator matrix to determine the number of parallel subtrellises in uniform sectionalisations of the minimal trellises of RM codes and to design trellises for RM codes with more parallel subtrellises than the minimal trellis but the same state complexity.