Lexicographic Codes

In this chapter, we examine the theoretical underpinnings of lexicodes and investigate various generalizations. Our intent is to graft desired decoding properties onto the heuristically good features of lexicodes. In this way, we develop a means for designing good codes for specific tasks. For example, we can fashion good codes which maintain a desired dimension, error-correction capability, and memory constraint.

Section 2.1 opens the chapter with a definition of the
lexicographic construction, which iteratively constructs
generator matrices for the family of minimum distance *d* lexicodes,
for any *d*. The lexicographic construction is, in turn, a special
case of the generalized lexicographic construction, which we
abbreviate as the G-construction. This generalized construction
encompasses a variety of code families which graft different
properties onto lexicode features.

Section 2.2 is devoted to various instances of the G-construction. Specifically, Section 2.2.1 analyzes the role of lexicodes as one of these instances and describes tools for efficiently constructing them. In Section 2.2.2 we demonstrate that a simple modification of the lexicode generator produces ``trellis-oriented'' lexicodes which locally minimize trellis complexity. These codes exhibit the same ``approximately optimal'' features of lexicodes but often have a much lower trellis decoding complexity, in some cases reaching the lowest trellis complexity known for their length, rate, and minimum distance. This modification provides a natural heuristic for improving upon the trellis-complexity of a given code. Finally, in Section 2.2.3 we examine methods for designing codes with various trellis characteristics, such as constrained state complexity or constrained Viterbi decoding complexity. These methods are particularly useful for VLSI decoding implementations, where layering bounds favor a small trellis state complexity, and mobile communications, where portability severely limits power consumption.

Section 2.3 investigates the coset relationship which
supports G-construction. This relationship establishes bounds on
the parameters of the codes produced by the construction and suggests
a natural algorithm for computing these codes. The bounds
established, though loose, are asymptotically tighter than the lexicode
bounds of Brualdi and Pless [9]. We also use the coset
relationship to bound the computation time of the *G*-construction
in Section 2.4.

Finally, in Section 2.5 we discuss various applications of the G-construction and present our conclusions. Appendix A lists simulation results for the various algorithms described in this chapter.