Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently byVladimir Levenshtein[1] 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.
A lexicode of length n and minimum distance d 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 |
Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2m codewords dictionary.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.
| n \ d | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | ||||||||||||||||||
| 2 | 2 | 1 | |||||||||||||||||
| 3 | 3 | 2 | 1 | ||||||||||||||||
| 4 | 4 | 1 | 1 | ||||||||||||||||
| 5 | 5 | 4 | 2 | 1 | 1 | ||||||||||||||
| 6 | 6 | 5 | 3 | 2 | 1 | 1 | |||||||||||||
| 7 | 7 | 6 | 4 | 3 | 1 | 1 | 1 | ||||||||||||
| 8 | 8 | 7 | 4 | 2 | 1 | 1 | 1 | ||||||||||||
| 9 | 9 | 8 | 5 | 4 | 2 | 2 | 1 | 1 | 1 | ||||||||||
| 10 | 10 | 9 | 6 | 5 | 3 | 2 | 1 | 1 | 1 | 1 | |||||||||
| 11 | 11 | 10 | 7 | 6 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | ||||||||
| 12 | 12 | 11 | 8 | 7 | 4 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | |||||||
| 13 | 13 | 12 | 9 | 8 | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | 1 | ||||||
| 14 | 14 | 13 | 10 | 9 | 6 | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | 1 | |||||
| 15 | 15 | 14 | 11 | 10 | 7 | 6 | 5 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | ||||
| 16 | 16 | 15 | 11 | 11 | 8 | 7 | 5 | 5 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | |||
| 17 | 17 | 16 | 12 | 11 | 9 | 8 | 6 | 5 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| 18 | 18 | 17 | 13 | 12 | 9 | 9 | 7 | 6 | 3 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 19 | 19 | 18 | 14 | 13 | 10 | 9 | 8 | 7 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 20 | 20 | 19 | 15 | 14 | 11 | 10 | 9 | 8 | 5 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | |
| 21 | 21 | 20 | 16 | 15 | 12 | 11 | 10 | 9 | 5 | 5 | 3 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | |
| 22 | 22 | 21 | 17 | 16 | 12 | 12 | 11 | 10 | 6 | 5 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | |
| 23 | 23 | 22 | 18 | 17 | 13 | 12 | 12 | 11 | 6 | 6 | 5 | 4 | 2 | 2 | 2 | 1 | 1 | 1 | |
| 24 | 24 | 23 | 19 | 18 | 14 | 13 | 12 | 7 | 6 | 5 | 5 | 3 | 2 | 2 | 2 | 1 | 1 | ||
| 25 | 25 | 24 | 20 | 19 | 15 | 14 | 12 | 12 | 8 | 7 | 6 | 5 | 3 | 3 | 2 | 2 | 1 | 1 | |
| 26 | 26 | 25 | 21 | 20 | 16 | 15 | 12 | 12 | 9 | 8 | 7 | 6 | 4 | 3 | 2 | 2 | 2 | 1 | |
| 27 | 27 | 26 | 22 | 21 | 17 | 16 | 13 | 12 | 9 | 9 | 7 | 7 | 5 | 4 | 3 | 2 | 2 | 2 | |
| 28 | 28 | 27 | 23 | 22 | 18 | 17 | 13 | 13 | 10 | 9 | 8 | 7 | 5 | 5 | 3 | 3 | 2 | 2 | |
| 29 | 29 | 28 | 24 | 23 | 19 | 18 | 14 | 13 | 11 | 10 | 8 | 8 | 6 | 5 | 4 | 3 | 2 | 2 | |
| 30 | 30 | 29 | 25 | 24 | 19 | 19 | 15 | 14 | 12 | 11 | 9 | 8 | 6 | 6 | 5 | 4 | 2 | 2 | |
| 31 | 31 | 30 | 26 | 25 | 20 | 19 | 16 | 15 | 12 | 12 | 10 | 9 | 6 | 6 | 6 | 5 | 3 | 2 | |
| 32 | 32 | 31 | 26 | 26 | 21 | 20 | 16 | 16 | 13 | 12 | 11 | 10 | 7 | 6 | 6 | 6 | 3 | 3 | |
| 33 | ... | 32 | ... | 26 | ... | 21 | ... | 16 | ... | 13 | ... | 11 | ... | 7 | ... | 6 | ... | 3 |
Since lexicodes are linear, they can also be constructed by means of their basis.
Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8).
int main
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.
