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.
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 | |
| 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 [http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html | Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs ]