Hispanopedia WikiLos códigos lexicográficos o léxicos son códigos correctores de errores generados de forma voraz con propiedades extraordinariamente buenas. Fueron creados independientemente 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 de Hamming y los códigos binarios de Golay [ 2 ] .
Construcción
Un léxico de longitud n y distancia mínima d sobre un cuerpo finito se genera comenzando con el vector de ceros y añadiendo iterativamente el siguiente vector (en orden lexicográfico ) de distancia de Hamming mínima d a partir de los vectores añadidos hasta el momento. Como ejemplo, el léxico de longitud 3 y distancia mínima 2 estaría formado por los vectores marcados con una "X" en el siguiente ejemplo:
Aquí se muestra una tabla con todos los léxicos de n bits y la distancia de Hamming mínima de d bits, resultantes de un diccionario de un máximo de 2 m palabras clave. Por ejemplo, el código F4 ( n=4, d=2, m=3), el código de Hamming extendido (n=8, d=4, m=4) y, especialmente, el código de Golay (n=24, d=8, m=12) muestran una compacidad excepcional en comparación con sus vecinos.
Todas las distancias léxicas impares de d bits son copias exactas de las distancias pares de d+1 bits 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 de d+1 mencionado anteriormente.
Dado que los léxicos son lineales, también pueden construirse mediante su base . [ 3 ]
Implementación
A continuación, C 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 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 de distancia unsigned int * z = malloc ( 1 << 29 ); for ( i = j = 0 ; i < ( 1 << N ); i ++ ) { // Escanear todos los léxicos anteriores for ( k = j -1 ; k >= 0 ; k -- ) // if ( pc ( z [ k ] ^ i ) < D ) // Invertir la comprobación break ; // es mucho más rápido... if ( k == -1 ) { // Agregar nuevo léxico for ( k = 0 ; k < N ; k ++ ) // & imprimirlo printf ( "%d" , ( i >> k ) & 1 ); printf ( " : %d \n " , j ); z [ j ++ ] = i; } } }teoría de juegos combinatoria
La teoría de los códigos lexicográficos está estrechamente relacionada con la teoría de juegos combinatorios . En particular, las palabras clave en 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 la que cada movimiento consiste en reemplazar cualquier montón por como máximo d − 1 montones más pequeños, y el objetivo es tomar la última piedra. [ 2 ]
Notas
- ↑ Levenšteĭn, VI (1960), "Об одном классе систематических кодов" [ Una clase de códigos sistemáticos ] , Doklady Akademii Nauk SSSR (en ruso), 131 (5): 1011– 1014, MR 0122629 ; Traducción al inglés en Soviet Math. Doklady 1 (1960), 368–371
- 1 2 3 Conway, John H. ; Sloane, NJA (1986), "Códigos lexicográficos: códigos correctores de errores de la teoría de juegos", IEEE Transactions on Information Theory , 32 (3): 337– 348, CiteSeerX 10.1.1.392.795 , doi : 10.1109/TIT.1986.1057187 , MR 0838197
- ↑ Trachtenberg, Ari (2002), "Diseño de códigos lexicográficos con una complejidad de enrejado dada", IEEE Transactions on Information Theory , 48 (1): 89–100 , doi : 10.1109/18.971740 , MR 1866958
Enlaces externos
- Tabla de léxicos binarios de Bob Jenkins
- Generador en línea de léxicos y sus variantes.
- Secuencia OEIS A075928 (Lista de palabras clave en léxico binario con distancia de Hamming 4 escritas como números decimales).
- Códigos de corrección de errores en gráficos: léxicos , diagramas de celosía y gráficos de factores.
- Detección y corrección de errores
