Lexicographic code
From Wikipedia the free encyclopedia
Top View
Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein 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
[edit]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 2 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.
Implementation
[edit]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
[edit]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
[edit]- ^ 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
- ^ 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
- ^ 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