Lexicographic code explained

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.

Construction

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:

VectorIn code?
000X
001
010
011X
100
101X
110X
111

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.

n \ d1 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
All odd d-bit lexicode distances are exact copies of the even d+1 bit distances minus the last dimension, soan 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).

  1. include
  2. 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

  1. English translation in Soviet Math. Doklady 1 (1960), 368–371

External links