Lexicographic codes or lexicodes are greedily generated
error-correcting codes with remarkably good properties. They were produced independently by
Vladimir Levenshtein and by
John Horton Conway and
Neil Sloane.
The binary lexicographic codes are
linear codes, and include the
Hamming codes and the
binary Golay codes.
[
]
Construction
A lexicode of length ''n'' and minimum distance ''d'' over a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance
In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
''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:
:
Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2m codewords dictionnary.
For example, F4 code (n=4,d=2,m=3), extended Hamming code (n=8,d=4,m=4) and especially Golay code (n=24,d=8,m=12) shows exceptional compactness compared to neighbors.
:
All odd d-bit lexicode distances are exact copies of the even d+1 bit distances minus the last dimension, so
an odd-dimensional space can never create something new or more interesting than the d+1 even-dimensional space above.
Since lexicodes are linear, they can also be constructed by means of their basis.
Implementation
Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8).
#include
#include
int main()
Combinatorial game theory
The theory of lexicographic codes is closely connected to combinatorial game theory. In particular, the codewords in a binary lexicographic code of distance ''d'' encode the winning positions in a variant of Grundy's game, played on a collection of heaps of stones, in which each move consists of replacing any one heap by at most ''d'' − 1 smaller heaps, and the goal is to take the last stone.[
]
Notes
External links
Bob Jenkins table of binary lexicodes
*{{OEIS el, sequencenumber=A075928, name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.
Trellises and Factor Graphs
Error detection and correction