Lexicographic code

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:

:{| class="wikitable" |- ! Vector ! In code? |- | 000

| |- | 010 | |- | 011

| |- | 101

| |}

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. :{| class="wikitable"

|- ! 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

|} 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

Implementation

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

#include <stdio.h>
#include <stdlib.h>
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;
#define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff])
                                                                                    
#define N 24 // N bits
#define D 8  // D bits distance
    unsigned int * z = malloc(1<<29);
    for (i=j=0; i < (1<<N); i++)      
    {                             // 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;                                                             
        }                                                                           
    }                                                                               
}  

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