Lexicographic Codes

Lexicographic codes, or lexicodes for short, are greedily constructed codes which were introduced by Conway and Sloane in [13,14]. Lexicodes have surprisingly good encoding parameters and include, among other famous optimal codes, the Hamming codes, the Golay code, and certain quadratic residue codes [14,42]. Several authors [9,14] have proved that lexicodes are linear, and comparison with optimal linear codes of the same length and dimension shows that lexicodes are usually within one of the optimal minimum distances [14] and often exhibit the smallest known covering radius [27]. Hence, lexicodes may be regarded as a heuristically good ``approximation'' to the optimal codes. Brualdi and Pless [9] have examined a similar generalization of lexicodes, known as greedy codes, and presented certain bounds on their parameters.

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.