'''Lexicographic codes''' or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein<ref>{{citation | last = Levenšteĭn | first = V. I. | authorlink = Vladimir Levenshtein | issue = 5 | journal = Doklady Akademii Nauk SSSR | language = Russian | mr = 0122629 | pages = 1011–1014 | title = Об одном классе систематических кодов | trans-title = A class of systematic codes | url = http://mi.mathnet.ru/dan39976 | volume = 131 | year = 1960}}; English translation in ''Soviet Math. Doklady'' 1 (1960), 368–371</ref> and by John Horton Conway and Neil Sloane.<ref name=conslo>{{citation | last1 = Conway | first1 = John H. | author1-link = John Horton Conway | last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane | doi = 10.1109/TIT.1986.1057187 | issue = 3 | journal = IEEE Transactions on Information Theory | mr = 838197 | pages = 337–348 | title = Lexicographic codes: error-correcting codes from game theory | volume = 32 | year = 1986| citeseerx = 10.1.1.392.795 }}</ref> The binary lexicographic codes are linear codes, and include the Hamming codes and the binary Golay codes.<ref name=conslo/>
== 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:
:{| class="wikitable" |- ! 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 2<sup>m</sup> codewords dictionary. For example, F<sub>4</sub> 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. :{| class="wikitable"
|- ! 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 |{{yes|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 |{{yes|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 | {{yes|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.<ref>{{citation | last = Trachtenberg | first = Ari | doi = 10.1109/18.971740 | issue = 1 | journal = IEEE Transactions on Information Theory | mr = 1866958 | pages = 89–100 | title = Designing lexicographic codes with a given trellis complexity | volume = 48 | year = 2002}}</ref>
== Implementation == Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8). <syntaxhighlight lang="c"> #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; } } } </syntaxhighlight>
== 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.<ref name=conslo/>
== Notes == <references/>
== External links == *[http://burtleburtle.net/bob/math/lexicode.html Bob Jenkins table of binary lexicodes] *[http://ipsit.bu.edu/comp.html On-line generator for lexicodes and their variants] *{{OEIS el|sequencenumber=A075928|name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers. }} *[http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html Error-Correcting Codes on Graphs: Lexicodes], [http://oeis.org/search?q=Trellises Trellises and Factor Graphs]
Category:Error detection and correction