Content deleted Content added
Open access status updates in citations with OAbot #oabot |
|||
| (32 intermediate revisions by 16 users not shown) | |||
Line 1:
'''Lexicographic codes''' or lexicodes are greedily generated [[error-correcting code
[[Vladimir Levenshtein]]<ref>{{citation
| last = Levenšteĭn | first = V. I. | authorlink = Vladimir Levenshtein
| issue = 5
| journal = [[Proceedings of the USSR Academy of Sciences|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 code]]s, and include the [[Hamming code]]s and the [[binary Golay code]]s.<ref name=conslo/>
== Construction ==
A lexicode of
:{| class="wikitable"
|-
! Vector
Line 36 ⟶ 56:
|
|}
Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2<sup>m</sup> codewords dictionnary.
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 (linear algebra) | 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]]
| |||