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 field][finite fields]].
Construction
A lexicode of minimum distance d and length over a finite field is generated by starting with the all zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance from the vectors added so far. As an example, the length lexicode of minimum distance 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
- ^ V.I. Levenstein. A class of systematic codes. Soviet Math. Dokl, 1(1):368-371, 1960.
- ^ 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.
- ^ A. 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 in the On-Line Encyclopedia of Integer Sequences
Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs