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

Tadao KASAMI; Toyoo TAKATA; Toru FUJIWARA; Shu LIN

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

Tadao KASAMI, Toyoo TAKATA, Toru FUJIWARA, Shu LIN

Full Text Views

0

Cite this

Summary :

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 2ⁱ-section minimal trellis diagrams for Reed-Muller codes are given.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.9 pp.1411-1421

Publication Date: 1993/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category

Cite this

Copy

Tadao KASAMI, Toyoo TAKATA, Toru FUJIWARA, Shu LIN, "On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 9, pp. 1411-1421, September 1993, doi: .
Abstract: 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 2ⁱ-section minimal trellis diagrams for Reed-Muller codes are given.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_9_1411/_p

Copy

@ARTICLE{e76-a_9_1411,
author={Tadao KASAMI, Toyoo TAKATA, Toru FUJIWARA, Shu LIN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes},
year={1993},
volume={E76-A},
number={9},
pages={1411-1421},
abstract={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 2ⁱ-section minimal trellis diagrams for Reed-Muller codes are given.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - On Structural Complexity of the L-Section Minimal Trellis Diagrams for Binary Linear Block Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1411
EP - 1421
AU - Tadao KASAMI
AU - Toyoo TAKATA
AU - Toru FUJIWARA
AU - Shu LIN
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1993
AB - 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 2ⁱ-section minimal trellis diagrams for Reed-Muller codes are given.
ER -