• Images
• Videos
• Documents
• Books
• Articles

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.⁴

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.⁵

Notes

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

References

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 /wiki/Vladimir_Levenshtein ↩

2. 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 /wiki/John_Horton_Conway ↩

3. 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 /wiki/John_Horton_Conway ↩

4. 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 /wiki/IEEE_Transactions_on_Information_Theory ↩

5. 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 /wiki/John_Horton_Conway ↩