Los códigos lexicográficos o lexicodos son códigos de corrección de errores generados de forma voraz con propiedades notablemente buenas. Fueron producidos de forma independiente por Vladimir Levenshtein [1] y por John Horton Conway y Neil Sloane [2] . Los códigos lexicográficos binarios son códigos lineales e incluyen los códigos Hamming y los códigos binarios Golay [2] .
Se genera un lexicocódigo de longitud n y distancia mínima d sobre un cuerpo finito comenzando con el vector de todos ceros y agregando iterativamente el siguiente vector (en orden lexicográfico ) de distancia mínima de Hamming d a partir de los vectores agregados hasta el momento. Como ejemplo, el lexicocódigo de longitud 3 de distancia mínima 2 consistiría en los vectores marcados con una "X" en el siguiente ejemplo:
Aquí se muestra una tabla de todos los lexicocódigos de n bits por la distancia mínima de Hamming de d bits, resultante de un diccionario de palabras de código de 2 m como máximo . Por ejemplo, el código F 4 (n=4,d=2,m=3), el código Hamming extendido (n=8,d=4,m=4) y especialmente el código Golay (n=24,d=8,m=12) muestran una compacidad excepcional en comparación con sus vecinos.
Todas las distancias de lexicograma de d bits impares son copias exactas de las distancias de bits pares d+1 menos la última dimensión, por lo que un espacio de dimensión impar nunca puede crear algo nuevo o más interesante que el espacio de dimensión par d+1 anterior.
Como los lexicodos son lineales, también pueden construirse por medio de su base . [3]
A continuación se genera el código lexicográfico y se establecen los parámetros para el código Golay (N=24, D=8).
#include <stdio.h> #include <stdlib.h> int main () { /* Generación de CÓDIGO GOLAY */ int i , j , k ; int _pc [ 1 << 16 ] = { 0 }; // Macro PopCount para ( i = 0 ; i < ( 1 << 16 ); i ++ ) para ( 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 // Distancia de D bits unsigned int * z = malloc ( 1 << 29 ); for ( i = j = 0 ; i < ( 1 << N ); i ++ ) { // Escanear todos los for ( k = j -1 ; k >= 0 ; k -- ) // léxicos anteriores. if ( pc ( z [ k ] ^ i ) < D ) // Comprobación inversa break ; // es mucho más rápido... if ( k == -1 ) { // Añadir nuevo léxico for ( k = 0 ; k < N ; k ++ ) // & imprimirlo printf ( "%d" , ( i >> k ) & 1 ); printf ( " : %d \n " , j ); z [ j ++ ] = i ; } } } La teoría de los códigos lexicográficos está estrechamente relacionada con la teoría de juegos combinatorios . En particular, las palabras clave de un código lexicográfico binario de distancia d codifican las posiciones ganadoras en una variante del juego de Grundy , que se juega sobre una colección de montones de piedras, en el que cada movimiento consiste en reemplazar cualquier montón por un máximo de d − 1 montones más pequeños, y el objetivo es tomar la última piedra. [2]