Código binario de Golay

Tipo de código de corrección de errores lineal

En matemáticas e ingeniería electrónica , un código Golay binario es un tipo de código de corrección de errores lineal utilizado en comunicaciones digitales . El código Golay binario, junto con el código Golay ternario , tiene una conexión particularmente profunda e interesante con la teoría de grupos esporádicos finitos en matemáticas. ^[1] Estos códigos reciben su nombre en honor a Marcel JE Golay , cuyo artículo de 1949 ^[2] en el que los introdujo ha sido calificado por ER Berlekamp como la "mejor página publicada" en teoría de codificación. ^[3]

Existen dos códigos binarios Golay estrechamente relacionados. El código binario Golay extendido , G ₂₄ (a veces llamado simplemente "código Golay" en la teoría de grupos finitos) codifica 12 bits de datos en una palabra de 24 bits de tal manera que cualquier error de 3 bits se puede corregir o cualquier error de 4 bits se puede detectar. El otro, el código binario Golay perfecto , G ₂₃ , tiene palabras de código de longitud 23 y se obtiene del código binario Golay extendido eliminando una posición de coordenadas (por el contrario, el código binario Golay extendido se obtiene del código binario Golay perfecto agregando un bit de paridad ). En la notación de codificación estándar, los códigos tienen parámetros [24, 12, 8] y [23, 12, 7], correspondientes a la longitud de las palabras de código, la dimensión del código y la distancia mínima de Hamming entre dos palabras de código, respectivamente.

Definición matemática

En términos matemáticos, el código binario Golay extendido G _{24 consiste en un} subespacio lineal de 12 dimensiones W del espacio V = F²⁴
₂de palabras de 24 bits de modo que dos elementos distintos de W difieran en al menos 8 coordenadas. W se denomina código lineal porque es un espacio vectorial. En total, W comprende 4096 = 2 ¹² elementos.

• Los elementos de W se denominan palabras de código . También se pueden describir como subconjuntos de un conjunto de 24 elementos, donde la adición se define como tomar la diferencia simétrica de los subconjuntos.
• En el código Golay binario extendido, todas las palabras de código tienen pesos Hamming de 0, 8, 12, 16 o 24. Las palabras de código de peso 8 se denominan octadas y las palabras de código de peso 12 se denominan dodecadas .
• Las óctadas del código G ₂₄ son elementos del sistema de Steiner S(5,8,24) . Hay 759 = 3 × 11 × 23 óctadas y 759 complementos de las mismas. De ello se deduce que hay 2576 = 2 ⁴ × 7 × 23 dodecadas.
• Dos óctadas se intersecan (tienen 1 en común) en las coordenadas 0, 2 o 4 en la representación vectorial binaria (estos son los posibles tamaños de intersección en la representación del subconjunto). Una óctada y una dodecada se intersecan en las coordenadas 2, 4 o 6.
• Hasta el reetiquetado de coordenadas, W es único.

El código binario de Golay, G _23, es un código perfecto . Es decir, las esferas de radio tres alrededor de las palabras de código forman una partición del espacio vectorial. G _{23 es un} subespacio de 12 dimensiones del espacio F²³
₂.

El grupo de automorfismos del código binario perfecto de Golay G ₂₃ (es decir, el subgrupo del grupo S ₂₃ de permutaciones de las coordenadas de F²³
₂que dejan G ₂₃ invariante), es el grupo de Mathieu . El grupo de automorfismos del código binario Golay extendido es el grupo de Mathieu , de orden 2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23 . es transitivo en octadas y en dodecadas. Los otros grupos de Mathieu ocurren como estabilizadores de uno o varios elementos de W . ${\displaystyle M_{23}}$ ${\displaystyle M_{24}}$ ${\displaystyle M_{24}}$

Hay una sola palabra de peso 24, que es un subespacio invariante unidimensional. por lo tanto tiene una representación irreducible de 11 dimensiones en el campo con 2 elementos. Además, dado que el código binario de Golay es un subespacio de 12 dimensiones de un espacio de 24 dimensiones, también actúa sobre el espacio cociente de 12 dimensiones , llamado cocode binario de Golay . Una palabra en el cocode está en la misma clase lateral que una palabra de longitud 0, 1, 2, 3 o 4. En el último caso, 6 palabras cocode (disjuntas) se encuentran todas en la misma clase lateral. Hay un subespacio invariante de 11 dimensiones, que consiste en palabras cocode con peso impar, que da una segunda representación de 11 dimensiones en el campo con 2 elementos. ${\displaystyle M_{24}}$ ${\displaystyle M_{24}}$ ${\displaystyle M_{24}}$

Construcciones

• Código lexicográfico : Ordene los vectores en V lexicográficamente (es decir, interpretelos como enteros binarios de 24 bits sin signo y tome el orden usual). Comenzando con w ₀ = 0, defina w ₁ , w ₂ , ..., w ₁₂ por la regla de que w _n es el entero más pequeño que difiere de todas las combinaciones lineales de elementos anteriores en al menos ocho coordenadas. Entonces W puede definirse como el lapso de w ₁ , ..., w ₁₂ .
• Grupo de Mathieu : Witt publicó en 1938 una construcción del grupo de Mathieu más grande que se puede utilizar para construir el código binario Golay extendido. ^[4]
• Código de residuo cuadrático : considere el conjunto N de residuos cuadráticos no cuadráticos (mod 23). Este es un subconjunto de 11 elementos del grupo cíclico Z /23 Z . Considere las transcripciones t + N de este subconjunto. Aumente cada transcripción a un conjunto de 12 elementos S _t agregando un elemento ∞. Luego, etiquetando los elementos base de V por 0, 1, 2, ..., 22, ∞, W puede definirse como el lapso de las palabras S _t junto con la palabra que consiste en todos los vectores base. (El código perfecto se obtiene omitiendo ∞).
• Como código cíclico : El código G ₂₃ perfecto se puede construir mediante la factorización de sobre el campo binario GF(2) : Es el código generado por . ^[5] Se puede utilizar cualquiera de los factores irreducibles de grado 11 para generar el código. ^[6] ${\displaystyle x^{23}-1}$ $${\displaystyle x^{23}-1=(x-1)(x^{11}+x^{9}+x^{7}+x^{6}+x^{5}+x+1)(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1).}$$ ${\displaystyle \left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right)}$
• Construcción de Turyn de 1967, "Una construcción simple del código binario Golay", que parte del código Hamming de longitud 8 y no utiliza los residuos cuadráticos módulo 23. ^[7]
• Del sistema Steiner S(5,8,24) , que consta de 759 subconjuntos de un conjunto de 24. Si se interpreta el soporte de cada subconjunto como una palabra de código 0-1 de longitud 24 (con peso de Hamming 8), estas son las "octadas" en el código binario de Golay. El código de Golay completo se puede obtener tomando repetidamente las diferencias simétricas de los subconjuntos, es decir, la adición binaria. Una forma más fácil de escribir el sistema Steiner o las octadas es el Generador de Octadas Miracle de RT Curtis, que utiliza una correspondencia particular 1:1 entre las 35 particiones de un conjunto de 8 en dos conjuntos de 4 y las 35 particiones del espacio vectorial finito en 4 planos. ^[8] Hoy en día, a menudo se utiliza el enfoque compacto del hexacódigo de Conway, que utiliza una matriz de 4 × 6 celdas cuadradas. ${\displaystyle \mathbb {F} _{2}^{4}}$
• Posiciones ganadoras en el juego matemático de Mogul: una posición en Mogul es una fila de 24 monedas. Cada turno consiste en lanzar de una a siete monedas de manera que la moneda más a la izquierda pase de cara a cruz. Las posiciones perdedoras son aquellas en las que no se puede hacer ningún movimiento legal. Si cara se interpreta como 1 y cruz como 0, entonces pasar a una palabra clave del código binario extendido de Golay garantiza que será posible forzar una victoria.
• Una matriz generadora para el código binario Golay es IA , donde I es la matriz identidad 12×12 y A es el complemento de la matriz de adyacencia del icosaedro .

Una representación conveniente

Es conveniente utilizar el formato " Miracle Octad Generator ", con coordenadas en una matriz de 4 filas y 6 columnas. La suma consiste en tomar la diferencia simétrica. Las 6 columnas tienen la misma paridad, que es igual a la de la fila superior.

Una partición de las 6 columnas en 3 pares de columnas adyacentes constituye un trío . Se trata de una partición en 3 conjuntos de óctadas. Un subgrupo, el grupo lineal especial proyectivo PSL(2,7) x S ₃ de un subgrupo de trío de M ₂₄ es útil para generar una base. PSL(2,7) permuta las óctadas internamente, en paralelo. S ₃ permuta las 3 óctadas en su conjunto.

La base comienza con la octava T:

0 1 1 1 1 11 0 0 0 0 01 0 0 0 0 01 0 0 0 0 0

y 5 octadas similares. La suma N de todas estas 6 palabras de código consta de todos 1. Sumar N a una palabra de código produce su complemento.

Griess (p. 59) utiliza la etiqueta:

∞ 0 | ∞ 0 | ∞ 03 2 | 3 2 | 3 25 1 | 5 1 | 5 16 4 | 6 4 | 6 4

PSL(2,7) es naturalmente el grupo fraccionario lineal generado por (0123456) y (0∞)(16)(23)(45). El ciclo 7 actúa sobre T para dar un subespacio que incluye también los elementos base.

0 1 1 0 1 00 0 0 0 0 00 1 0 1 0 11 1 0 0 0 0

y

0 1 1 0 1 00 1 0 1 0 11 1 0 0 0 00 0 0 0 0 0

El subespacio de 7 dimensiones resultante tiene un espacio cociente de 3 dimensiones al ignorar las últimas dos octadas.

Hay otras 4 palabras código de estructura similar que completan la base de 12 palabras código para esta representación de W.

W tiene un subespacio de dimensión 4, simétrico bajo PSL(2,7) x S ₃ , abarcado por N y 3 dodecadas formadas por los subconjuntos {0,3,5,6}, {0,1,4,6} y {0,1,2,5}.

Aplicaciones prácticas de los códigos Golay

Misiones de la NASA al espacio profundo

La corrección de errores era vital para la transmisión de datos en las naves espaciales Voyager 1 y 2, en particular porque las limitaciones de memoria dictaban que la descarga de datos se realizaría prácticamente al instante, sin dejar segundas oportunidades. Cientos de fotografías en color de Júpiter y Saturno en sus sobrevuelos de 1979, 1980 y 1981 se transmitirían dentro de un ancho de banda de telecomunicaciones limitado. La transmisión de imágenes en color requería tres veces más datos que las imágenes en blanco y negro, por lo que el código Reed-Muller con siete errores de corrección que se había utilizado para transmitir las imágenes en blanco y negro de la Mariner fue reemplazado por el código Golay (24,12,8) con una velocidad de datos mucho mayor. ^[9]

Comunicaciones por radio

Las normas militares estadounidenses MIL-STD-188 para el establecimiento automático de enlaces en sistemas de radio de alta frecuencia especifican el uso de un código Golay extendido (24,12) para la corrección de errores hacia adelante . ^{[10] [11]}

En la comunicación por radio bidireccional, el sistema de silenciamiento codificado digitalmente (DCS, CDCSS) utiliza una palabra de código Golay (23,12) de 23 bits que tiene la capacidad de detectar y corregir errores de 3 bits o menos.

Véase también

• Red de sanguijuelas
• Código lineal

Referencias

1. Thompson 1983
2. Golay, Marcel JE (1949). «Notas sobre codificación digital» (PDF) . Proc. IRE . 37 : 657. Archivado desde el original (PDF) el 10 de abril de 2023.
3. Berlekamp, ​​ER (1974), Documentos clave en el desarrollo de la teoría de la codificación , IEEE Press, pág. 4
4. Hansen, Robert Peter. "Construcción y simplicidad de los grandes grupos de Mathieu". SJSU Scholar Works .
5. Roman 1996, pág. 324 Ejemplo 7.4.3
6. Pless 1998, pág. 114
7. Turyn 1967, Sección VI
8. Cullinane, Steven H. "El generador de octadas milagroso". Geometría finita del cuadrado y el cubo .
9. Cherowitzo, Bill. "Combinatoria en el espacio: el sistema de telemetría del Mariner 9" (PDF) . Universidad de Colorado en Denver . Archivado desde el original (PDF) el 27 de septiembre de 2013. Consultado el 6 de junio de 2012 .
10. Johnson, Eric E. (24 de febrero de 1991). "Un códec Golay eficiente para MIL-STD-188-141A y FED-STD-1045" (PDF) . Consultado el 9 de diciembre de 2017 .
11. "Estándar militar: Estándar de planificación y orientación para la aplicación de control automatizado para radio HF" (PDF) . EverySpec: especificaciones, estándares, manuales y documentos Mil-Spec . 1994-04-04 . Consultado el 2017-12-09 .

Fuentes

• Conway, John Horton ; Sloane, Neil JA (1999), Empaquetamientos, celosías y grupos de esferas, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3.ª ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98585-5, Sr.  0920369
• Curtis, RT (1976). "Un nuevo enfoque combinatorio para M ₂₄ ". Actas matemáticas de la Cambridge Philosophical Society . 79 (1): 25–42. Bibcode :1976MPCPS..79...25C. doi :10.1017/S0305004100052075. S2CID  122860631.
• Greferath, Marcus (2003). "Códigos Golay". En Proakis, John G. (ed.). Enciclopedia de telecomunicaciones . Wiley. doi :10.1002/0471219282.eot371. ISBN 0471219282.
• Griess, Robert L. (1998). Doce grupos esporádicos . Springer. pág. 167. ISBN. 978-3-540-62778-4.
• Pless, Vera (1998), Introducción a la teoría de los códigos de corrección de errores (3.ª ed.), John Wiley & Sons, ISBN 978-0-471-19047-9
• Roman, Steven (1996), Teoría de la codificación y la información , Textos de posgrado en matemáticas n.° 134, Springer-Verlag, ISBN 0-387-97812-7
• Thompson, Thomas M. (1983). De códigos de corrección de errores a empaquetamientos de esferas y grupos simples . Carus Mathematical Monographs. Vol. 21. Asociación Matemática de Estados Unidos. ISBN 978-0-88385-023-7.
• Turyn, Richard J.; et al. (1967). Investigación para desarrollar la teoría algebraica de códigos (Sección VI) (PDF) (Informe). Air Force Cambridge Research Laboratories. Archivado desde el original (PDF) el 30 de octubre de 2018.