Código Golay

En la teoría del código , un código Golay es un código de corrección de errores que puede ser binario o terciario, llamado así en honor a su inventor, Marcel Golay . Hay dos tipos de códigos binarios Golay. El código Golay binario extendido codifica 12 bits de datos en una longitud de palabra de código de 24 bits, de modo que se pueda corregir cualquier error en tres bits y detectar cualquier error de cuatro bits. El otro, el código binario perfecto de Golay , tiene palabras de código de 23 bits de longitud y se obtiene del código binario extendido de Golay eliminando una posición en las coordenadas (a la inversa, el código binario extendido de Golay se obtiene del código binario perfecto de Golay agregando un bit de paridad ).

Código binario de Golay

En términos matemáticos, el código binario extendido de Golay consiste en un subespacio vectorial de 12 dimensiones W del espacio V = F 2 24 palabras de 24 bits de manera que dos elementos distintos de W difieren en al menos ocho coordenadas o, de manera equivalente, de manera que cualquier no -El elemento cero de W tiene al menos ocho coordenadas distintas de cero.

Las coordenadas de los elementos distintos de cero de W se denominan palabras de código. En el código binario extendido de Golay, todas las palabras de código tienen un peso Hamming de 0, 8, 12, 16 o 24.
W es único excepto por el reetiquetado.

El código binario de Golay es perfecto 3-corrector . En otras palabras, las bolas cerradas de radio 3 alrededor de las palabras del código forman una partición del espacio vectorial.

Construcciones

Código lexicográfico: Clasifica los vectores en V por orden lexicográfico . Comenzando con w 1 = 0, defina w 2 , w 3 , ..., w 12 mediante la regla de que w n es el número entero más pequeño que difiere de todas las combinaciones lineales de los elementos precedentes en al menos ocho coordenadas. Entonces W puede definirse como el conjunto generado por w 1 , ..., w 12 .
Código de residuo cuadrático : Considere el conjunto N de los no residuos cuadráticos (mod 23). Este es un subconjunto de 11 elementos del grupo cíclico Z / 23 Z . Considere las traslaciones t + N de este subconjunto. Incrementa cada traslación a un conjunto S t de 12 elementos agregando un elemento ∞. Etiquetando los elementos de la base de V por 0, 1, 2 ..., 22 ∞, W se puede definir el conjunto generado por las palabras S t así como la palabra que consta de todos los vectores base. (El código perfecto se obtiene omitiendo ∞).
Como código cíclico : El código perfecto de G 23 se puede construir mediante la factorización de . Este es el código producido por $x ^ {{23}} - 1$ $x ^ {{11}} + x ^ {{10}} + x ^ {6} + x ^ {5} + x ^ {4} + x ^ {2} + 1 / x ^ {{23}} - 1$
RT Curtis 'Miracle Octad Generator: utiliza celdas cuadradas de 4 × 6 para describir las 759 palabras de código que tienen un peso Hamming de 8, u "octads", del código binario extendido de Golay. Las palabras de código restantes se obtienen mediante las diferencias simétricas de los subconjuntos de las 24 celdas, es decir, por adición binaria. Para obtener más información, consulte la geometría del cuadrado de 4 × 4 .

Código de Golay ternario

Hay dos códigos de corrección de errores estrechamente relacionados conocidos como códigos ternarios de Golay. El código más conocido como código ternario de Golay es un código lineal ternario perfecto (11, 6, 5); El código ternario extendido de Golay es un código lineal (12, 6, 6) que se obtiene agregando un dígito clave de suma cero al código (11, 6, 5).

El enumerador de peso completo del código ternario extendido de Golay es

x ^ {{12}} + y ^ {{12}} + z ^ {{12}} + 22 (x ^ {6} y ^ {6} + y ^ {6} z ^ {6} + z ^ {6} x ^ {6}) + 220 (x ^ {6} y ^ {3} z ^ {3} + y ^ {6} z ^ {3} x ^ {3} + z ^ {6} x ^ {3} y ^ {3})

El código ternario perfecto de Golay se puede construir como el código de residuo cuadrático de longitud 11 sobre el campo finito F 3 .

El grupo de automorfismo del código ternario extendido de Golay es 2. M 12 , donde M 12 es un grupo de Mathieu .

Considere todas las palabras de código de código extendido que tienen solo seis dígitos distintos de cero. Los conjuntos de posiciones en las que se encuentran estos dígitos distintos de cero forman el sistema S de Steiner (5, 6, 12).

Notas y referencias

Pascal Boyer, pequeño compañero de números y sus aplicaciones , y Calvage Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , VI. Criptografía, cap. 8.4 ("Códigos BCH").

Bibliografía

[Conway y Sloane 1988] (in) John H. Conway y Neil JA Sloane , Sphere Packings, Lattices and Groups , Nueva York, Springer, coll. "Grundlehren der mathischen Wissenschaften / Una serie de estudios integrales en matemáticas" ( n o 290),1988( ISBN 978-1-4757-2018-1 , ISSN 0072-7830 , DOI 10.1007 / 978-1-4757-2016-7 ).