Tail-Biting Trellises of Block Codes: Trellis Complexity and Viterbi Decoding Complexity
I. Reuven, Non-members · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 1999
SUMMARY Tail-biting trellises of linear and nonlinear block codes are addressed. We refine the information-theoretic approach of a previous work on conventional trellis representation, and show that the same ideas carryover to tail-biting trellises. We present lower bounds on the state and branch complexity profiles of these representations. These bounds are expressed in terms of mutual information between different portions of the code, and theyintroduce the notions of superstates and superbranches. For linear block codes, our bounds implythat the total number of superstates, and respectivelysuperbranches, of a tail-biting trellis of the code cannot be smaller than the total number of states, and respectivelybranches, of the corresponding minimal conventional trellis, though the total number of states and branches of a tail-biting trellis is usuallysmaller than that of the conventional trellis. We also develop some improved lower bounds on the state complexityof a tail-biting trellis for two classes of codes: the first-order Reed-Muller codes and cyclic codes. We show that the superstates and superbranches determine the Viterbi decoding complexityof a tail-biting trellis. Thus, the computational complexityof the maximum-likelihood decoding of linear block codes on a tail-biting trellis, using the Viterbi algorithm, is not smaller than that of the conventional trellis of the code. However, tail-biting trellises are beneficial for suboptimal and iterative decoding techniques.