On complexity of trellis structure of linear block codes
Tadao Kasami, Tadafumi Takata, Toru Fujiwara, Shih-Wei Lin · IEEE Transactions on Information Theory · 1993
An upper bound on the number of states of a minimal trellis diagram for a linear block code is derived. Using this derivation a cyclic (or shortened cyclic) code or its extended code is shown to be the worst in terms of trellis state complexity among the linear codes of the same length and dimension. The complexity of the minimal trellis diagrams for linear block codes of length 2/sup m/, including the Reed-Muller codes, is analyzed. The construction of minimal trellis diagrams for some extended and permuted primitive BCH codes is presented. It is shown that these codes have considerably simpler trellis structure than the original codes in cyclic form without bit-position permutation.>