Lexicographic code

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]

## Contents

* 1 Construction
* 2 Implementation
* 3 Combinatorial game theory
* 4 Notes
* 5 External links

## 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. ↑ "Об одном классе систематических кодов" (in Russian), Doklady Akademii Nauk SSSR 131 (5): 1011–1014, 1960, http://mi.mathnet.ru/dan39976 ; English translation in Soviet Math. Doklady 1 (1960), 368–371
2. ↑ 2.0 2.1 2.2 "Lexicographic codes: error-correcting codes from game theory", IEEE Transactions on Information Theory 32 (3): 337–348, 1986, doi:10.1109/TIT.1986.1057187
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

## External links

* Bob Jenkins table of binary lexicodes
* On-line generator for lexicodes and their variants
* OEIS sequence A075928 (List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.)
* Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Lexicographic code. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Lexicographic_code&oldid=3377427"
*[OEIS]: On-Line Encyclopedia of Integer Sequences