stringtranslate.com

Código binario de Golay

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 fue 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 24 (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 puede corregirse o cualquier error de 4 bits puede detectarse. El otro, el código binario Golay perfecto , G 23 , tiene palabras de código de longitud 23 y se obtiene a partir del código binario Golay extendido eliminando una posición de coordenadas (a la inversa, el código binario Golay extendido se obtiene a partir 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 = F24
2
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 12 elementos.

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 F23
2
.

El grupo de automorfismos del código binario perfecto de Golay G 23 (es decir, el subgrupo del grupo S 23 de permutaciones de las coordenadas de F23
2
que dejan G 23 invariante), es el grupo de Mathieu . El grupo de automorfismos del código binario Golay extendido es el grupo de Mathieu , de orden 2 10 × 3 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 .

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.

Construcciones

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 3 de un subgrupo de trío de M 24 es útil para generar una base. PSL(2,7) permuta las óctadas internamente, en paralelo. S 3 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 óctavas 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 3 , 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

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