Código lexicográfico
Los códigos lexicográficos o lexicodes son códigos de corrección de errores generados con avidez 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]
Construcción
Se genera un lexicodo de distancia mínima d y longitud n sobre un campo finito comenzando con el vector todo cero y agregando iterativamente el siguiente vector (en orden lexicográfico ) de distancia mínima de Hamming d de los vectores agregados hasta ahora. Como ejemplo, el lexicodo de longitud 3 de distancia mínima 2 estaría formado por los vectores marcados con una "X" en el siguiente ejemplo:
Vector ¿En codigo? 000 X 001 010 011 X 100 101 X 110 X 111
Dado que los lexicodes son lineales, también se pueden construir mediante su base . [3]
Teoría de juegos combinatorios
La teoría de los códigos lexicográficos está estrechamente relacionada con la teoría de juegos combinatorios . En particular, las palabras de código en un código lexicográfico binario de distancia d codifican las posiciones ganadoras en una variante del juego de Grundy , jugado en una colección de montones de piedras, en el que cada movimiento consiste en reemplazar cualquier montón por d - 1 más pequeño. montones, 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 matemáticas soviéticas. Doklady 1 (1960), 368–371
- ^ a b c Conway, John H .; Sloane, NJA (1986), "Códigos lexicográficos: códigos de corrección de errores de la teoría de juegos", IEEE Transactions on Information Theory , 32 (3): 337–348, doi : 10.1109 / TIT.1986.1057187 , MR 0838197
- ^ Trachtenberg, Ari (2002), "Diseño de códigos lexicográficos con una complejidad de enrejado determinada", IEEE Transactions on Information Theory , 48 (1): 89-100, doi : 10.1109 / 18.971740 , MR 1866958
enlaces externos
- Tabla de Bob Jenkins de lexicodes binarios
- Generador on-line de lexicodes y sus variantes
- Secuencia OEIS A075928 (Lista de palabras de código en lexicodo binario con la distancia de Hamming 4 escrita como números decimales).
- Códigos de corrección de errores en gráficos: Lexicodes , Trellises y gráficos de factores
- Detección y corrección de errores
