Lexicographic code

Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Levenshtein^[1] and Conway and Sloane ^[2] and are known to be linear over some finite fields.

Construction

A lexicode of minimum distance d and length ${\displaystyle n}$  over a finite field ${\displaystyle \mathbb {F} }$  is generated by starting with the all zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance ${\displaystyle d}$  from the vectors added so far. As an example, the length ${\displaystyle 3}$  lexicode of minimum distance ${\displaystyle 2}$  would consist of the vectors marked by an "X" in the following example:

Vector	In code?
000	X
001
010
011	X
100
101	X
110	X
111

Since lexicodes are linear, they can also be constructed by means of their basis. ^[3]

Notes

1. V.I. Levenstein. A class of systematic codes. Soviet Math. Dokl, 1(1):368-371, 1960.
2. J.H. Conway and N.J.A Sloane. Lexicographic codes: error-correcting codes from game theory. IEEE Transactions on Information Theory, 32:337-348, 1986.
3. Ari Trachtenberg, Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.

External links

• Bob Jenkins table of binary lexicodes
• Entry OEIS: A075928 in the On-Line Encyclopedia of Integer Sequences
• Error-Correcting Codes on Graphs: Lexicodes, [http://www.research.att.com/~njas/sequences/Trellises and Factor Graphs