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:
In most cases, Algorithm 2.12 then automatically
provides a code which matches these criteria and generally has
- the trellis should be locally oriented towards decoding efficiency,
- or the trellis must occupy less than m bits of memory,
- or the trellis must allow error-correction using at most f (k) operations.
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:
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.
- a trellis-oriented code of length 19, which requires 64 trellis states
and 715 operations for Viterbi decoding,
- or a code of length 24 whose trellis has been constrained to 16 states and
requires 301 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  on the parameter bounds of lexicodes.