Código binario de Golay

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

Existen dos códigos binarios de Golay estrechamente relacionados. El código binario de Golay extendido , G₂₄ (a veces llamado simplemente "código de Golay" en la teoría de grupos finitos), codifica 12 bits de datos en una palabra de 24 bits _, de manera que se pueden corregir errores de 3 bits o detectar errores de 7 bits. El otro, el código binario de Golay perfecto , G₂₃ , tiene palabras clave de longitud ₂₃ y se obtiene a partir del código binario de Golay extendido eliminando una posición de coordenada (a la inversa, el código binario de Golay extendido se obtiene a partir del código binario de Golay perfecto añadiendo 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], que corresponden a la longitud de las palabras clave, la dimensión del código y la distancia de Hamming mínima entre dos palabras clave, respectivamente.

En términos matemáticos, el código binario extendido de Golay G _{24 consiste en un} subespacio lineal W de 12 dimensiones del espacio V = F ²⁴ ₂ de palabras de 24 bits, de modo que cualesquiera dos elementos distintos de W difieren 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 clave . También se pueden describir 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 Golay binario extendido, todas las palabras de código tienen pesos de Hamming de 0, 8, 12, 16 o 24. Las palabras de código de peso 8 se llaman octadas y las palabras de código de peso 12 se llaman dodecadas .
• 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. Por lo tanto, hay 2576 = 2 ⁴ × 7 × 23 dodecadas.
• Dos octadas se intersecan (tienen un 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 de subconjuntos). Una octada y un dodecada se intersecan en las coordenadas 2, 4 o 6.
• Salvo que se cambie el nombre de las 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 del 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 .${\displaystyle M_{23}}$El grupo de automorfismos del código binario extendido de Golay es el grupo de Mathieu .${\displaystyle M_{24}}$, de orden 2 ¹⁰ × 3 ³ × 5 × 7 × 11 × 23 .${\displaystyle M_{24}}$es transitivo en octadas y en dodecadas. Los otros grupos de Mathieu aparecen como estabilizadores de uno o varios elementos de W.

Existe una sola palabra de peso 24, que es un subespacio invariante unidimensional.${\displaystyle M_{24}}$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,${\displaystyle M_{24}}$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 (disjuntas) del cocode se encuentran todas en la misma clase lateral. Hay un subespacio invariante de 11 dimensiones, que consiste en palabras del cocode con peso impar, que da${\displaystyle M_{24}}$una segunda representación de 11 dimensiones en el campo con 2 elementos.

• Código lexicográfico : Ordene los vectores en V lexicográficamente (es decir, interprételos como enteros binarios sin signo de 24 bits 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 se puede definir como el espacio generado por w ₁ , ..., w ₁₂ .
• Grupo de Mathieu : Witt publicó en 1938 una construcción del grupo de Mathieu más grande que puede usarse para construir el código Golay binario extendido. ^{[ 4 ]}
• Código de residuos cuadráticos : Consideremos el conjunto N de no residuos cuadráticos (mod 23). Este es un subconjunto de 11 elementos del grupo cíclico Z /23 Z . Consideremos las traslaciones t + N de este subconjunto. Ampliemos cada traslación a un conjunto S _t de 12 elementos añadiendo un elemento ∞. Entonces, etiquetando los elementos base de V con 0, 1, 2, ..., 22, ∞, W se puede definir como el espacio generado por las palabras S _t 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 de${\displaystyle x^{23}+1}$sobre el campo binario GF(2) :$${\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${\displaystyle \left(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1\right)}$. ^{[ 5 ]} Cualquiera de los factores irreducibles de grado 11 puede usarse para generar el código. ^{[ 6 ]}
• La construcción de Turyn de 1967, "Una construcción simple del código binario de Golay", que parte del código de Hamming de longitud 8 y no utiliza los residuos cuadráticos módulo 23. ^{[ 7 ]}
• Del sistema de Steiner S(5,8,24) , que consta de 759 subconjuntos de un conjunto de 24 elementos. Si se interpreta el soporte de cada subconjunto como una palabra clave 0-1 de longitud 24 (con peso de Hamming 8), estos son los "octádos" 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 suma binaria. Una forma más sencilla de escribir el sistema de Steiner o los octados es el Generador de Octadas Milagroso de RT Curtis, que utiliza una correspondencia 1:1 particular entre las 35 particiones de un conjunto de 8 elementos en dos conjuntos de 4 elementos y las 35 particiones del espacio vectorial finito.${\displaystyle \mathbb {F} _{2}^{4}}$en 4 planos. ^{[ 8 ]} Hoy en día se suele utilizar el enfoque compacto del hexacódigo de Conway, que utiliza una matriz de 4 × 6 celdas cuadradas.
• 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 hay movimientos válidos. 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 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 .

0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0

∞ 0 | ∞ 0 | ∞ 0 3 2 | 3 2 | 3 2 5 1 | 5 1 | 5 1 6 4 | 6 4 | 6 4

0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0

0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0

• Red de sanguijuelas
• Código lineal