Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein[1] and by John Horton Conway and Neil Sloane.[2] The binary lexicographic codes are linear codes, and include the Hamming codes and the binary Golay codes.[2]

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:

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 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 \ 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 3 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 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 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.[3]

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.[2]

Notes

  1. ↑ Levenšteĭn, V. I. (1960), "Об одном классе систематических кодов" [A class of systematic codes], Doklady Akademii Nauk SSSR (in Russian), 131 (5): 1011–1014, MR 0122629; English translation in Soviet Math. Doklady 1 (1960), 368–371
  2. 1 2 3 Conway, John H.; Sloane, N. J. A. (1986), "Lexicographic codes: error-correcting codes from game theory", IEEE Transactions on Information Theory, 32 (3): 337–348, CiteSeerX 10.1.1.392.795, doi:10.1109/TIT.1986.1057187, MR 0838197
  3. ↑ Trachtenberg, Ari (2002), "Designing lexicographic codes with a given trellis complexity", IEEE Transactions on Information Theory, 48 (1): 89–100, doi:10.1109/18.971740, MR 1866958
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.