Código binario Golay

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

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

Hay dos códigos Golay binarios estrechamente relacionados. El código Golay binario 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 7 bits. Se pueden detectar errores de bits. El otro, el código Golay binario perfecto , G ₂₃ , tiene palabras de código de longitud 23 y se obtiene del código Golay binario extendido eliminando una posición de coordenadas (por el contrario, el código Golay binario extendido se obtiene del código Golay binario perfecto agregando una bit de paridad ). En 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 extendido de Golay G _{24 consta de un} subespacio lineal de 12 dimensiones W del espacio V = F²⁴
₂de palabras de 24 bits tales que dos elementos distintos de W difieren en al menos 8 coordenadas. W se llama código lineal porque es un espacio vectorial. En total, W comprende 4096 = 2 ¹² elementos.

• Los elementos de W se llaman palabras de código . También pueden describirse como subconjuntos de un conjunto de 24 elementos, donde la suma se define como la diferencia simétrica de los subconjuntos.
• En el código binario extendido de Golay, 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 dodecads .
• Las octadas del código G ₂₄ son elementos del sistema Steiner S(5,8,24) . Hay 759 = 3 × 11 × 23 octadas y 759 complementos de las mismas. Se deduce que hay 2576 = 2 ⁴ × 7 × 23 dodécadas.
• Dos octadas se cruzan (tienen unos en común) en 0, 2 o 4 coordenadas en la representación vectorial binaria (estos son los posibles tamaños de intersección en la representación de subconjunto). Una octada y una dodécada se cruzan en 2, 4 o 6 coordenadas.
• Hasta volver a etiquetar las coordenadas, W es único.

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

El grupo de automorfismo del código Golay binario perfecto G ₂₃ (es decir, el subgrupo del grupo S ₂₃ de permutaciones de las coordenadas de F²³
₂que dejan invariante a G ₂₃ ), es el grupo de Mathieu . El grupo de automorfismo del código binario extendido de Golay es el grupo de Mathieu , de orden 2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23 . es transitivo en octadas y dodécadas. Los otros grupos de Mathieu se presentan como estabilizadores de uno o varios elementos de W. ${\displaystyle M_{23}}$ ${\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 habitual). 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 Mathieu : Witt publicó en 1938 una construcción del grupo Mathieu más grande que se puede utilizar para construir el código binario Golay extendido. ^[4]
• Código de residuos cuadráticos : considere el conjunto N de 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. Aumente cada traducción a un conjunto de 12 elementos S _t agregando un elemento ∞. Luego, etiquetar los elementos base de V como 0, 1, 2, ..., 22, ∞, W _se puede definir como el intervalo de las palabras St junto con la palabra que consta de 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 del campo binario GF(2) : ${\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).}$$
  Es el código generado por . ^[5] Cualquiera de los factores irreducibles de grado 11 se puede utilizar para generar el código. ^[6] ${\displaystyle \left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right)}$
• La 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 mod 23. ^[7]
• Del sistema Steiner S(5,8,24) , que consta de 759 subconjuntos de un conjunto de 24. Si uno interpreta el soporte de cada subconjunto como una palabra de código 0-1 de longitud 24 (con peso Hamming 8), estas son las "octadas" en el código binario de Golay. El código Golay completo se puede obtener tomando repetidamente las diferencias simétricas de subconjuntos, es decir, suma binaria. Una manera más fácil de anotar el sistema Steiner resp. las octadas es el Generador de Octadas Milagrosas 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 se utiliza a menudo el enfoque compacto del hexacódigo de Conway, que utiliza una matriz de 4×6 de 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 modo que la moneda lanzada más a la izquierda vaya de la cabeza a la cola. Las posiciones perdedoras son aquellas que no tienen ningún movimiento legal. Si cara se interpreta como 1 y cruz como 0, 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 de Golay es IA , donde I es la matriz identidad de 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 es tomar la diferencia simétrica. Las 6 columnas tienen la misma paridad, que es igual a la de la fila superior.

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

La base comienza con octada T:

0 1 1 1 1 1

1 0 0 0 0 0

1 0 0 0 0 0

1 0 0 0 0 0

y 5 octadas similares. La suma N de las 6 palabras de código consta de unos. Agregar N a una palabra clave produce su complemento.

Griess (p. 59) utiliza el etiquetado:

∞ 0 |∞ 0 |∞ 0

3 2 |3 2 |3 2

5 1 |5 1 |5 1

6 4 |6 4 |6 4

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

0 1 1 0 1 0

0 0 0 0 0 0

0 1 0 1 0 1

1 1 0 0 0 0

y

0 1 1 0 1 0

0 1 0 1 0 1

1 1 0 0 0 0

0 0 0 0 0 0

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

Hay otras 4 palabras clave de estructura similar que completan la base de 12 palabras clave 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 dodécadas formadas por 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 fue vital para la transmisión de datos en las naves espaciales Voyager 1 y 2, particularmente porque las limitaciones de memoria dictaban la descarga de datos prácticamente instantáneamente 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 requirió tres veces más datos que las imágenes en blanco y negro, por lo que el código Reed-Muller de corrección de 7 errores que se había utilizado para transmitir las imágenes Mariner en blanco y negro fue reemplazado por el Golay con una velocidad de datos mucho mayor (24, 12). ,8) código. ^[9]

Comunicaciones por radio

Los estándares 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 directos . ^{[10] [11]}

En la comunicación por radio bidireccional, el sistema de silenciamiento codificado digital (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.

Ver también

• celosía de sanguijuela
• 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), Artículos clave en el desarrollo de la teoría de la codificación , IEEE Press, p. 4
4. Hansen, Robert Peter. "Construcción y simplicidad de los grandes grupos Mathieu". Trabajos académicos de SJSU .
5. Romano 1996, pag. 324 Ejemplo 7.4.3
6. Pless 1998, pag. 114
7. Turyn 1967, Sección VI
8. Cullinane, Steven H. "El generador de octadas milagrosas". Geometría Finita del Cuadrado y del Cubo .
9. Cherowitzo, Bill. "Combinatoria en el espacio: el sistema de telemetría Mariner 9" (PDF) . Universidad de Colorado 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 aplicaciones de control automatizado para radio HF" (PDF) . EverySpec: especificaciones, estándares, manuales y documentos Mil-Spec . 1994-04-04 . Consultado el 9 de diciembre de 2017 .

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, señor  0920369
• Curtis, RT (1976). "Un nuevo enfoque combinatorio del M ₂₄ ". Actas matemáticas de la Sociedad Filosófica de Cambridge . 79 (1): 25–42. Código Bib : 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 . Saltador. pag. 167.ISBN​ 978-3-540-62778-4.
• Pless, Vera (1998), Introducción a la teoría de los códigos correctores de errores (3.ª ed.), John Wiley & Sons, ISBN 978-0-471-19047-9
• Roman, Steven (1996), Codificación y teoría de la información , Textos de posgrado en matemáticas n.° 134, Springer-Verlag, ISBN 0-387-97812-7
• Thompson, Thomas M. (1983). Desde códigos de corrección de errores pasando por empaquetamientos de esferas hasta grupos simples . Monografías matemáticas de Carus. vol. 21. Asociación Matemática de América. ISBN 978-0-88385-023-7.
• Turyn, Richard J.; et al. (1967). Investigación para el desarrollo de la teoría algebraica de códigos (Sección VI) (PDF) (Reporte). Laboratorios de investigación de Cambridge de la Fuerza Aérea. Archivado desde el original (PDF) el 30 de octubre de 2018.