Introduction

Lexicographic codes, or lexicodes for short, are greedily constructed codes which were introduced by Levenshtein [9] and again by Conway and Sloane in [4,5]. Lexicodes have surprisingly good encoding parameters and include, among other famous optimal codes, the Hamming codes, the binary Golay code, and certain quadratic residue codes [5,10]. Several authors [3,5,9] 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 distance [5] and often exhibit the smallest known covering radius [6]. Hence, lexicodes may be regarded as a heuristically good ``approximation'' to optimal codes. Brualdi and Pless [3] have examined a similar generalization of lexicodes, known as greedy codes, and presented certain bounds on their parameters.

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 opens with a definition of the lexicographic construction, which iteratively constructs generator matrices for the family of minimum distance d lexicodes, for any d > 0. The lexicographic construction is, in turn, a special case of the generalized lexicographic construction, which we abbreviate as the $\mathfrak{G}$-construction. This generalized construction encompasses a variety of code families which graft different properties onto lexicode features.

Section 3 is devoted to various instances of the $\mathfrak{G}$-construction. Specifically, Section 3.1 analyzes the role of lexicodes as one of these instances and describes tools for efficiently constructing them. In Section 3.2 we demonstrate that a simple modification of the lexicode generator produces ``trellis-oriented'' lexicodes that 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 transforming a given code into a similar code with (often) a better trellis complexity. Finally, in Section 3.3 we examine methods for designing codes with various trellis characteristics, such as constrained state complexity or constrained Viterbi decoding complexity. These methods might be particularly useful for VLSI-based decoding, where implementation constraints favor a small trellis state complexity, and for mobile communications, where portability severely limits power consumption.

Section 4 investigates the coset relationship which supports the $\mathfrak{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 [3]. We also use the coset relationship to bound the computation time of the $\ensuremath{{\mathfrak{G}}}$-construction in Section 5.

Finally, in Section 6 we discuss various applications of the $\mathfrak{G}$-construction and present our conclusions. The appendix lists simulation results for the some of the algorithms described in the paper, extending the list of lexicode parameters originally published in [5].