Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by
Levenshtein and Conway and Sloane and are known to be linear

Linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

 over some finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

s.

Construction

A lexicode of minimum distance d and length n over a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 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

Basis (linear algebra)

In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

.

External links

• Bob Jenkins table of binary lexicodes
• On-line generator for lexicodes and their variants
• http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html Error-Correcting Codes on Graphs: Lexicodes, and Factor Graphs