On trellis structures for Reed-Muller codes
type: Item
instance of: scholarly article
title: On trellis structures for Reed-Muller codes
zbMATH Open document ID: 0953.94025
author: T. Blackmore
author: G. H. Norton
published in: Finite Fields and their Applications
publication date: 2001-01-22T00:00:00Z
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.
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94B35
zbMATH DE Number: 1421407
zbMATH Keywords: Reed-Muller codes
zbMATH Keywords: trellises for codes
reviewed by: Ian Blake
MaRDI profile type: Publication
full work available at URL: ffta.1999.0265
OpenAlex ID: W1987484145
cites work: Q4004114
cites work: Bounds on the trellis size of linear block codes
cites work: Q4217882
cites work: Coset codes. II. Binary lattices and related codes
cites work: Dimension/length profiles and trellis complexity of linear block codes
cites work: On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes
cites work: On complexity of trellis structure of linear block codes
cites work: Trellis decoding complexity of linear block codes
cites work: On the trellis structure of block codes
cites work: On bit-level trellis complexity of Reed-Muller codes
cites work: On the BCJR trellis for linear block codes
cites work: Minimal trellises for block codes
cites work: Efficient maximum likelihood decoding of linear block codes using a trellis
Wikidata QID: Q126339837
DOI: 10.1006/FFTA.1999.0265
Recommended article: On bit-level trellis complexity of Reed-Muller codes
Recommended article: On the trellis structure of block codes
Recommended article: On algebraic structure of the Reed-Muller codes
Recommended article: On the Reed-Muller codes
Recommended article: On the weight structure of Reed-Muller codes
Recommended article: Q4500975
Recommended article: On generalized ReedMuller codes and their relatives
Recommended article: On a conjecture on Reed-Muller codes
Recommended article: Quasi-cyclic structure of Reed-Muller codes and their smallest regular trellis diagram
Recommended article: The trellis structure of maximal fixed-cost codes
description: scientific article; zbMATH DE number 1421407