stringtranslate.com

Lexicographic code

Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently byVladimir 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:

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]

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. ^ a b c 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

External links