Lexicographic codeLexicographic 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] ConstructionA 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 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.
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] ImplementationFollowing 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 theoryThe 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
External links |
Portal di Ensiklopedia Dunia
