On the Labeling of Minimal Trellises for Linear Block Codes
Hari T IvIoorthy, Shu Lin · International Symposium on Information Theory and its Applications · 1994
The first study of the trellis structure of linear block codes in known literature was done by Wolf in 1978. He presented a trellis construction method for a (n, k) linear block code whose complexity is exponential in min(k, n - k) and hence impractical for many block codes of interest to researchers today. Forney introduced the squaring constructions and showed that Reed-Muller codes can readily be expressed as squaring constructions of smaller length Reed-Muller codes. Kasami et. al. analyzed the general structure of L-section minimal trellis diagrams for linear block codes and studied the structural complexity in terms of state complexity, branch complexity, state connectivity and parallel structure. This analysis involved specific subcodes of the given code and their respective dimensions. In the above papers, no mention is made of how the labels for the trellis might be generated. Presently, Viterbi decoders are being considered for decoding linear block codes, and such a Viterbi decoder must implement the labeling of the trellis of the code. In this paper, we consider the specific problem of labeling L-section minimal trellis diagrams for binary linear block codes. It is organized as follows. In section 2, we generalize Wolf's original definition of stole and transition [1] to L-section, .Lf-bit/branch trellises for a linear block code of length LAM. In section 3, we present an efficient algorithm for constructing and labeling the minimal L-section trellis for a linear block code from the generator matrix of the code. This algorithm is computationally far less intensive than Wolf's and has been applied to construct trellises of complexity up to 32,768 states (eg. for the (64,45,8) ex-BCH code). We also prove the minimality of the constructed trellis. In section 4, we illustrate the algorithm by applying it to the 2-level squaring construction.Includes figures and tables. Includes references.