Lexicographic code: Difference between revisions

Revision as of 13:17, 6 March 2022

Latest revision as of 23:16, 11 January 2024

(9 intermediate revisions by 3 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 minimum distancelength ''dn'' and lengthminimum distance ''nd'' 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"

Line 56 ⟶ 57:

|}

Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2^m codewords dictionnary.

For example, F₄ 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"

Line 146 ⟶ 147:

! 4

| 4

| {{yes|3}}

| 1

| 1

Line 232 ⟶ 233:

| 7

| 4

| {{goodyes|4}}

| 2

| 1

Line 572 ⟶ 573:

| 13

| 12

| {{wonyes|12}}

| 7

| 6

Line 774 ⟶ 775:

|}

All odd d-bit distancelexicode lexicodesdistances are exact copies of the even d+1 bit distancedistances 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

Line 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 ==