Content deleted Content added
linearity and examples |
Open access status updates in citations with OAbot #oabot |
||
| (12 intermediate revisions by 4 users not shown) | |||
Line 21:
| 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"
Line 56 ⟶ 57:
|}
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
Line 66 ⟶ 788:
| 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 ==
| |||