- Lexicographic code
Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently byLevenshtein [V.I. Levenstein. A class of systematic codes. Soviet Math. Dokl, 1(1):368-371, 1960.] and Conway and Sloane [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.] and are known to be linear over some
finite field s.Construction
A lexicode of minimum distance d and length n over a
finite field mathbb{F} is generated by starting with the all zero vector and iteratively adding the next vector (inlexicographic order ) of minimum Hamming distance d from the vectors added so far. As an example, the length 3 lexicode of minimum distance 2would consist of the vectors marked by an "X" in the following example:Since lexicodes are linear, they can also be constructed by means of their basis. [A. Trachtenberg, Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.]
Notes
External links
[http://burtleburtle.net/bob/math/lexicode.html Bob Jenkins table of binary lexicodes]
[http://www.research.att.com/~njas/sequences/A075928 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 ]
Wikimedia Foundation. 2010.