For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes
Tadao KASAMI Toyoo TAKATA Toru FUJIWARA Shu LIN
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/09/25
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(819.9KB)>>
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.