Trellis decoding

In Chapter 2 we determined a generalized lexicographic construction which is capable of designing codes for efficient decoding. This construction can generate trellis-oriented codes, which locally minimize trellis complexity. More importantly, however, it also enables the design of codes whose decoding trellises are constrained, either by state complexity or by Viterbi decoding complexity.

Thus one may pick a block size in which to parse information (corresponding to the dimension k of the resulting error-correcting code) and a desired number t of errors which should be corrected, and then specify any one the following additional constraints:

1. the trellis should be locally oriented towards decoding efficiency,
2. or the trellis must occupy less than m bits of memory,
3. or the trellis must allow error-correction using at most f (k) operations.

In most cases, Algorithm 2.12 then automatically provides a code which matches these criteria and generally has little redundancy.

For example, if we were to design a triple-error correcting code (i.e. t = 3) for encoding 8-bit messages, one version of the above constraints could produce:

1. a trellis-oriented code of length 19, which requires 64 trellis states and 715 operations for Viterbi decoding,
2. or a code of length 24 whose trellis has been constrained to 16 states and requires 301 operations for Viterbi decoding.

Using the technique in Section 2.5.2 we could also improve the state-constrained code above to one with a 16 state trellis requiring only 295 operations for Viterbi decoding.

The computations of Algorithm 2.12 are made possible by the theoretical backbone of Theorem 2.5. This theorem relates the cosets of successive codes in a generalized lexicographic construction. We have analyzed the bijective mapping describing the coset relationship and have presented a minor improvement over [9] on the parameter bounds of lexicodes.