Lexicographic code
Lexicographic codesor lexicodes are greedily generatederror-correcting codeswith remarkably good properties. They were produced independently by Vladimir Levenshtein[1]and byJohn Horton ConwayandNeil Sloane.[2]The binary lexicographic codes arelinear codes,and include theHamming codesand thebinary Golay codes.[2]
Construction
[edit]A lexicode of lengthnand minimum distancedover afinite fieldis generated by starting with the all-zero vector and iteratively adding the next vector (inlexicographic order) of minimumHamming distancedfrom 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 2mcodewords dictionnary. For example, F4code (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 theirbasis.[3]
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>
intmain(){/* GOLAY CODE generation */
inti,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
unsignedint*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 tocombinatorial game theory.In particular, the codewords in a binary lexicographic code of distancedencode the winning positions in a variant ofGrundy's game,played on a collection of heaps of stones, in which each move consists of replacing any one heap by at mostd− 1 smaller heaps, and the goal is to take the last stone.[2]
Notes
[edit]- ^Levenšteĭn, V. I.(1960),"Об одном классе систематических кодов"[A class of systematic codes],Doklady Akademii Nauk SSSR(in Russian),131(5): 1011–1014,MR0122629;English translation inSoviet Math. Doklady1 (1960), 368–371
- ^abcConway, John H.;Sloane, N. J. A.(1986), "Lexicographic codes: error-correcting codes from game theory",IEEE Transactions on Information Theory,32(3): 337–348,CiteSeerX10.1.1.392.795,doi:10.1109/TIT.1986.1057187,MR0838197
- ^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,MR1866958