Código Binario de Golay

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En las matemáticas y en la informática el código binario de Golay es un tipo de código corrector de errores usado en las comunicaciones digitales. El código binario de Golay, junto con el código terciario de Golay tienen una particularidad y conexión interesante con la teoría de los grupos esporádicos finitos en matemáticas. El código lleva el nombre en honor a Marcel J.E Golay.

Hay dos tipos de códigos Golay que están relacionados entre sí. El primero es el código Golay extendido binario que codifica 12 bits de datos en una palabra de 24 bits de tal manera que cualquier error de 3 bits puede ser corregido y cualquier error de 4 bits puede ser detectado. El otro es el código binario perfecto de Golay tiene palabras código de longitud 23 bits, y es obtenido directamente del código binario extendido de Golay al suprimir una posición de coordenadas, de otra manera se puede decir que el código binario extendido de Golay se obtiene a partir del código binario perfecto al añadir un bit de paridad.

Cómo son los códigos Golay trasmitidos[editar]

Es posible enviar 8 bits estándar utilizando el código binario de Golay estándar que utiliza una modulación de 8 a 12.Otros esquemas para posicionar los bits puede ser la utilización que permite compartir 8 bits de datos en el ancho de banda con 4 bits de telemetría.

Definición matemática[editar]

En los términos matemáticos el código binario extendido de Golay consiste en un subespacio W de 12 dimensiones del espacio V=F224 de palabras de 24 bits de tal manera que dos elementos distintos en el espacio W se diferencian en al menos en la últimas 8 coordenadas. De manera equivalente cualquier elemento no cero de W tiene al menos 8 coordenadas que no son cero.

  • El conjunto posible de coordenadas no cero así como los rangos w sobre el espacio W son llamadas palabras código. En el código binario extendido de Golay todas la palabras código tienen un peso Hamiltoniano de 0,8,12,16 ó 24.
  • Hasta el reetiquetado de coordenadas, W es único.

El código binario perfecto de Golay es un código perfecto, lo que significa que esferas de radio 3 alrededor de las palabras código forman una partición del espacio vectorial.

El grupo de automorfismos de código binario de Golay es el grupo Mathieu M_23.Y el grupo de automorfismo del código binario extendido de Golay es el Mathieu M_24. Los grupos Mathieu ocurren como estabilizadores de uno o de varios elementos de W.

Las palabras código Golay son elementos de S(5,8,24) del sistema Steiner.

Construcciones[editar]

  1. Código lexicográfico: El orden de los vectores en V (por ejemplo, se interpretan como enteros binarios sin signo de 24 bits y toman el orden normal). Empezando con w_1=0, definimos w_2, w_3,..., w_12 suponiendo que w_n es el entero más pequeño que se diferencia de las combinaciones lineales de los elementos previos en al menos 8 coordenadas. Entonces el espacio W se puede definir como el espacio formado por w_1,..., w_12.
  2. Código residual cuadrático: Considera el conjunto N de los cuadrados no residuales (mod 23). Esto es un subconjunto de 11 elementos del grupo cíclico Z/23Z. Considera la translación t+N de este subconjunto. Aumenta cada traslado al conjunto de 12 elementos S_t al añadir un elemento infinito. Entonces el etiquetado de los elementos básicos de V es 0, 1, 2,..., 22, ∞, W se puede definir como el espacio de las palabras de S_t con las palabras conseguidas a través de los vectores básicos. (El código perfecto se obtiene dejando fuera el infinito)
  3. Código cíclico: El código perfecto G23, se puede construir al factorizar x^{23}-1, es el código generado por x^{11}+x^{10}+x^6+x^5+x^4+x^2+1 / x^{23}-1
  4. Generador milagroso de octarios de R, T Curtis: Utiliza un matriz de 4x6 celdas cuadradas para dibujar los 759 palabras código del código de Hamming de peso 8, o octarios de código binario extendido de Golay. Las palabras que quedan se obtienen a través de diferencias simétricas de subconjuntos de 24 celdas, por ejemplo a través de la adicción binaria.
  5. La posición ganadora en el juego matemático de Mogul: la posición es Mogul es una columna de 24 monedas. Cada turno consiste en tirar de 1 a 7 monedas de tal forma que la que más lejos quede va a la cabeza de la cola. Las posiciones perdedoras son aquellas que no tiene un movimiento legal. Si las cabezas son interpretadas como uno y las cruces como cero mueves de tal manera las palabras código del código extendido de Golay entonces garantizas que es posible ganar la partida.

Aplicaciones prácticas de los códigos de Golay[editar]

Misiones NASA en el espacio[editar]

Los satélites Voyage 1&2 necesitaban transmitir cientos de fotografías en color de Júpiter y Saturno entre 1979 y 1980 con un ancho de banda de comunicaciones muy bajo.

  • Cada imagen transmitida requería 3 veces la cantidad de datos, de manera que se usaba el código de Golay(24,12,8).
  • Este código de Golay solo corregía 3 errores, pero puede transmitir datos a mucha más velocidad.

Comunicaciones de datos de alta frecuencia ALE[editar]

Los estándar del nuevo gobierno de EEUU para el ALE (automatic link establishment) en el sistema de radio de alta frecuencia especifica el uso del código en bloque extendido Golay(24,12) para poder corregir el error antes de que se produzca.

  • El código extendido de Golay(24,12) es un código en bloque (24,12).
  • El código codifica 12 bits de datos para producir palabras de 24 bits.
  • Además es un código sistemático, significa que las palabras de 12 bits se presentan en un formato incambiable en todas las palabras código.
  • El polinomio generador de este código es g(x) = x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1

La mínima distancia entre dos palabras código (es el número de bits en que se diferencian) es 8, lo que proporciona que este código pueda detectar hasta 7 errores en cada palabra código(y corregir ninguno), corrige 3 errores y detecta 4 en cualquier combinación intermedia.

Enlaces externos[editar]