On trellis structures for Reed-Muller codes

DOI10.1006/FFTA.1999.0265MaRDI QIDQ1971064zbMATH OpenOpenAlexWikidataFDO

Authors T. Blackmore, G. H. Norton

Publication date 22 January 2001

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/ffta.1999.0265

zbMATH Keywords

Reed-Muller codes trellises for codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Review text

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: On trellis structures for Reed-Muller codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971064)