Every linear block code may be represented by a trellis, which canbe employed for maximum likelihood decoding of the code with the Viterbialgorithm or variants thereof. We present a polynomial-time algorithmwhich produces the optimal sectionalization of a given trellis T for ablock code C in time O(n2), where n is the length of C. Thealgorithm is developed in a general setting of certain operations andfunctions defined on the set of trellises; it therefore applies to bothlinear and nonlinear codes, and accommodates a broad range of optimalitycriteria. The optimality criterion based on minimizing the number ofoperations required for trellis decoding of C is investigated in detail.Several methods for decoding a given trellis are discussed and comparedin a number of examples. An analysis of the dynamical properties ofoptimal sectionalizations is also presented
展开▼
