lexicographic code

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:

:

Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2^m codewords dictionnary.

For example, F₄ 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.{{citation

| last = Trachtenberg | first = Ari

| doi = 10.1109/18.971740

| issue = 1

| journal = IEEE Transactions on Information Theory

| mr = 1866958

| pages = 89–100

| title = Designing lexicographic codes with a given trellis complexity

| volume = 48

| year = 2002}}

Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8).

1. include
2. include

int main() { /* GOLAY CODE generation */

int i, j, k;

int _pc[1<<16] = {0}; // PopCount Macro

for (i=0; i < (1<<16); i++)

for (j=0; j < 16; j++)

_pc[i] += (i>>j)&1;

1. define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff])

1. define N 24 // N bits
2. define D 8 // D bits distance

unsigned int * z = malloc(1<<29);

for (i=j=0; i < (1<

{ // Scan all previous

for (k=j-1; k >= 0; k--) // lexicodes.

if (pc(z[k]^i) < D) // Reverse checking

break; // is way faster...

if (k == -1) { // Add new lexicode

for (k=0; k < N; k++) // & print it

printf("%d", (i>>k)&1);

printf(" : %d\n", j);

z[j++] = i;

}

}

}

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.

• [http://burtleburtle.net/bob/math/lexicode.html Bob Jenkins table of binary lexicodes]
• [http://ipsit.bu.edu/comp.html On-line generator for lexicodes and their variants]
• {{OEIS el|sequencenumber=A075928|name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers. }}
• [http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html Error-Correcting Codes on Graphs: Lexicodes], [http://oeis.org/search?q=Trellises Trellises and Factor Graphs]

Category:Error detection and correction