While the complexity of trellis decoding for a given block code is essentially a function of the number of states and branches in its trellis, the decoding complexity may be often reduced by means of an appropriate sectionalization of the trellis. Notwithstanding the many examples of such sectionalizations for particular codes that appeared in the literature, no systematic method for finding the best sectionalization of a given trellis is presently known. We present a polynomial-time algorithm which produces the optimal sectionalization of a given trellis T in time O(n/sup 2/), where n is the length of the code generated by T. The algorithm is developed in a general setting of certain operations and functions defined on the set of trellises; it therefore applies to both linear and nonlinear codes, and easily accommodates a broad range of optimality criteria. The particular optimality criterion based on minimizing the total number of additions and comparisons required for maximum-likelihood trellis decoding is investigated in detail: several different methods for decoding a given trellis are discussed and compared in a number of examples. Finally, analysis of the dynamical properties of certain optimal sectionalizations is presented.

The trellis complexity s(C) of a block code C is defined as the logarithm of the maximum number of states in the minimal trellis realization of the code. The parameter s(C) governs the complexity of maximum-likelihood decoding, and is considered a fundamental descriptive characteristic of the code in a number of recent works. We derive a new lower bound on s(C) which implies that asymptotically good codes have infinite trellis complexity. More precisely, for i/spl ges/1 let C/sub i/ be a code over an alphabet of size q, of length n/sub i/, rate R/sub i/, and minimum distance d/sub i/. The infinite sequence of codes C/sub ,/ C/sub 2spl middotspl middotspl middot/ such that n/sub ispl rarrspl infin/ when i/spl rarrspl infin/ is said to be asymptotically good if both R/sub i/ and d/sub in/sub i/ are bounded away from zero as i/spl rarrspl infin/. We prove that the complexity s(C/sub i/) increases linearly with n/sub i/ in any asymptotically good sequence of codes.>

The trellis state-complexity s of a linear block code is defined as the logarithm of the maximum number of states in its minimal trellis. We present a new lower bound on the state complexity of linear codes, which includes most of the existing bounds as special cases. The new bound is obtained by dividing the time axis for the code into several sections of varying lengths, as opposed to the division into two sections-the past and the future-employed in the well-known DLP bounds. For a large number of codes this results in a considerable improvement upon the DLP bound. Moreover, we generalize the new bound to nonlinear codes, and introduce several alternative techniques for lower-bounding the trellis complexity, based on the distance spectrum and other combinatorial properties of the code. We also show how the general ideas developed in this paper may be employed to lower-bound the maximum and the total number of branches in the trellis, leading to considerably tighter bounds on these quantities. Furthermore, the asymptotic behavior of the new bounds is investigated, and shown to improve upon the previously known asymptotic estimates of trellis state-complexity.