Lexicographic code
From Wikipedia, the free encyclopedia
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.
[edit] Construction
A lexicode of minimum distance d and length n 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 d from the vectors added so far. As an example, the length 3 lexicode of minimum distance 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]
[edit] 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.
[edit] 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
