On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes

Abstract

It was shown earlier that for a punctured Reed-Muller (RM) code or a primitive BCH code, which contains a punctured RM code of the same minimum distance as a large subcode, the state complexity of the minimal trellis diagrams is much greater than that for an equivalent code obtained by a proper permutation of the bit positions. The problem of finding a permutation of the bit positions for a given code that minimizes the state complexity of its minimal trellis diagram is related to the generalized Hamming weight hierarchy of a code, and it is shown that, for RM codes, the standard binary order of bit positions is optimum at every bit position with respect to the state complexity of a minimal trellis diagram by using a theorem due to V.K. Wei (1991). The state complexity of the trellis diagram for the extended and permuted (64, 24) BCH code is discussed.<>