On Trellis Complexity of lock Codes: Opdimal
A. Lafourcade, Alexander Vardy · 1994
We present a polynomial-time algorithm which produces the optimal sectionalization of a given trellis T for a block code C in time O(n2), where n is the length of C. 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 accommodates a broad range of optimality criteria. The optimality criterion based on minimizing the number of opera- tions required for trellis decoding of C is investigated in detail: several methods for decoding a given trellis are discussed and compared in a number of examples. Finally, analysis of the dynamical properties of opti- mal sectionalizations is presented. I. INTRODUCTION It is now well-known (2, 31 that every linear block code may be represented by a trellis, which can be employed for maximum- likelihood decoding of the code with the Viterbi algorithm or variants thereof. The complexity of a given trellis is usually expressed in terms of parameters such as the number of states and/or branches it contains. While, indeed, these parameters govern the complexity of trellis decoding, in many cases this complexity may be reduced with an appropriate sectionaliza- tion of the trellis. By a sectionalization we mean the choice of the symbol alphabet at each time index: for a given order of the time axis 2, the sectionalization shrinks Z at the expense of increasing the code alphabet (2). A wide variety of such gran- ularity adjustments is possible, and each may substantially af- fect the decoding complexity. For a given code C of length n and a given order of its time axis Z, a specific sectionalization of its trellis T is determined by the set {ho, ht,. . . h,) C Z of section boundaries, where ho = 0 < ht < ..+ < h, = n. Clearly, there are 2-' possible ways to select the section boundaries, and the sectionalization problem consists of find- ing the optimal choice among the 2-' possibilities. Examples of specific 'good' sectionalizations for particular codes may be found in (2, 31 among other works. However, at the present time, finding the best sectionalization is more akin to 'art' than to exact science: no systematic method for finding the optimal sectionalization of a given trellis is presently known.