On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.9   pp.1411-1421
Publication Date: 1993/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
linear code,  block code,  trellis diagram,  Reed-Muller code,  

Full Text: PDF>>
Buy this Article

A linear block code has a finite-length trellis diagram which terminates at the length of the code. Such a trellis diagram is expressed and constructed in terms of sections. The complexity of an L-section trellis diagram for a linear block code is measured by the state and branch complexities, the state connectivity, and the parallel structure. The state complexity is defined as the number of states at the end of each section of the L-section trellis diagram, the branch complexity is defined as the number of parallel branches between two adjacent states, the state connectivity is defined in terms of the number of states which are adjacent to and from a given state and the connections between disjoint subsets of states, and the parallel structure is expressed in terms of the number of parallel sub-trellis diagrams without cross connections between them. This paper investigates the branch complexity, the state connectivity, and the parallel structure of an L-section minimal trellis diagram for a binary linear block code. First these complexities and structure are expressed in terms of the dimensions of specific subcodes of the given code. Then, the complexities of 2i-section minimal trellis diagrams for Reed-Muller codes are given.