Bounds on the trellis size of linear block codes
Yaniv Berger, Yair Be'ery · IEEE Transactions on Information Theory · 1993
The size of minimal trellis representation of linear block codes is addressed. Two general upper bounds on the trellis size, based on the zero-concurring codewords and the contraction index of the subcodes, are presented. The related permutations for attaining the bounds are exhibited. These bounds evidently improve the previously published general bound. Additional bounds based on certain code constructions are derived. The focus is on the squaring construction, and specific constructive bounds for Reed-Muller and repeated-root cyclic codes are obtained. In particular, the recursive squaring construction of Reed-Muller codes is explored and the exact minimal trellis size of this design is obtained. Efficient permutations, in the sense of the trellis size, are also demonstrated by using shortening and puncturing methods. The corresponding bounds are specified.>