Tail-Biting Trellises of Block Codes: Trellis Complexity and Viterbi Decoding Complexity

Ilan REUVEN  Yair BE'ERY  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.10   pp.2043-2051
Publication Date: 1999/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
trellises,  tail-biting trellis,  mutual information,  maximum likelihood decoding,  Viterbi algorithm,  

Full Text: PDF(372.7KB)>>
Buy this Article

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 carry over 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 they introduce the notions of superstates and superbranches. For linear block codes, our bounds imply that the total number of superstates, and respectively superbranches, of a tail-biting trellis of the code cannot be smaller than the total number of states, and respectively branches, of the corresponding minimal conventional trellis, though the total number of states and branches of a tail-biting trellis is usually smaller than that of the conventional trellis. We also develop some improved lower bounds on the state complexity of 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 complexity of a tail-biting trellis. Thus, the computational complexity of 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.