Código ternario de Golay

Par de códigos de corrección de errores relacionados

En teoría de codificación , los códigos ternarios de Golay son dos códigos de corrección de errores estrechamente relacionados . El código generalmente conocido simplemente como código ternario de Golay es un código -, es decir, es un código lineal sobre un alfabeto ternario ; la distancia relativa del código es lo más grande posible para un código ternario y, por lo tanto, el código ternario de Golay es un código perfecto . El código ternario de Golay extendido es un código lineal [12, 6, 6] obtenido agregando un dígito de control de suma cero al código [11, 6, 5]. En teoría de grupos finitos , el código ternario de Golay extendido a veces se denomina código ternario de Golay. ^{[ cita requerida ]} ${\displaystyle [11,6,5]_{3}}$

Propiedades

Código ternario de Golay

El código ternario Golay consta de 3 ⁶  = 729 palabras de código. Su matriz de comprobación de paridad es

${\displaystyle \left[{\begin{array}{cccccc|ccccc}2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1&1&2&2&0&0&0&0&1\end{array}}\right].}$

Dos palabras de código diferentes difieren en al menos 5 posiciones. Cada palabra ternaria de longitud 11 tiene una distancia de Hamming de como máximo 2 desde exactamente una palabra de código. El código también se puede construir como el código de residuo cuadrático de longitud 11 sobre el campo finito F ₃ ( es decir, el campo de Galois GF(3) ).

Utilizado en una quiniela de fútbol con 11 partidos, el código ternario Golay corresponde a 729 apuestas y garantiza exactamente una apuesta con un máximo de 2 resultados incorrectos.

El conjunto de palabras de código con peso de Hamming 5 es un diseño 3-(11,5,4) .

La matriz generadora dada por Golay (1949, Tabla 1.) es

${\displaystyle \left[{\begin{array}{cccccc|ccccc}1&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&1&0&2\\0&0&0&1&0&0&2&1&0&1&2\\0&0&0&0&1&0&2&0&1&2&1\\0&0&0&0&0&1&0&2&2&1&1\\\end{array}}\right].}$

El grupo de automorfismos del código ternario de Golay (original) es el grupo de Mathieu M ₁₁ , que es el más pequeño de los grupos simples esporádicos.

Código Golay ternario extendido

El enumerador de peso completo del código Golay ternario extendido es

${\displaystyle x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).}$

El grupo de automorfismos del código ternario extendido de Golay es 2. M ₁₂ , donde M ₁₂ es el grupo de Mathieu M ₁₂ .

El código Golay ternario extendido se puede construir como la extensión de las filas de una matriz Hadamard de orden 12 sobre el campo F ₃ .

Consideremos todas las palabras clave del código extendido que tienen sólo seis dígitos distintos de cero. Los conjuntos de posiciones en las que aparecen estos dígitos distintos de cero forman el sistema de Steiner S(5, 6, 12).

Una matriz generadora para el código Golay ternario extendido es

${\displaystyle \left[{\begin{array}{cccccc|cccccc}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&2&2&1\\0&0&1&0&0&0&1&1&0&1&2&2\\0&0&0&1&0&0&1&2&1&0&1&2\\0&0&0&0&1&0&1&2&2&1&0&1\\0&0&0&0&0&1&1&1&2&2&1&0\\\end{array}}\right]=[I_{6}|B].}$

La matriz de verificación de paridad correspondiente para esta matriz generadora es , donde denota la transposición de la matriz. ${\displaystyle [-B|I_{6}]^{T}}$ ${\displaystyle T}$

Una matriz generadora alternativa para este código es

${\displaystyle \left[{\begin{array}{rrrrrr|rrrrrr}1&0&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&0&1&-1&-1&1\\0&0&1&0&0&0&1&1&0&1&-1&-1\\0&0&0&1&0&0&1&-1&1&0&1&-1\\0&0&0&0&1&0&1&-1&-1&1&0&1\\0&0&0&0&0&1&1&1&-1&-1&1&0\\\end{array}}\right]=[I_{6}|B_{\mathrm {alt} }].}$

Y su matriz de comprobación de paridad es . ${\displaystyle [-B_{\mathrm {alt} }|I_{6}]^{T}}$

Los tres elementos del campo finito subyacente se representan aquí por , en lugar de por . También se entiende que ( es decir, el inverso aditivo de 1) y . Los productos de estos elementos del campo finito son idénticos a los de los números enteros. Las sumas de filas y columnas se evalúan módulo 3. ${\displaystyle \{0,1,-1\}}$ ${\displaystyle \{0,1,2\}}$ ${\displaystyle 2=1+1=-1}$ ${\displaystyle -2=(-1)+(-1)=1}$

Las combinaciones lineales, o suma de vectores , de las filas de la matriz producen todas las palabras posibles contenidas en el código. Esto se conoce como amplitud de las filas. El producto interno de dos filas cualesquiera de la matriz generadora siempre sumará cero. Se dice que estas filas, o vectores, son ortogonales .

El producto matricial de las matrices generadora y de comprobación de paridad, , es la matriz de todos los ceros y, por intención, este es un ejemplo de la definición misma de cualquier matriz de comprobación de paridad con respecto a su matriz generadora. ${\displaystyle [I_{6}|B_{\mathrm {alt} }]\,[-B_{\mathrm {alt} }|I_{6}]^{T}}$ ${\displaystyle 6\times 6}$

Historia y aplicaciones

El código ternario de Golay fue publicado por Golay  (1949). Fue descubierto de forma independiente dos años antes por el aficionado finlandés al fútbol-billar Juhani Virtakallio, quien lo publicó en 1947 en los números 27, 28 y 33 de la revista de fútbol Veikkaaja . (Barg 1993, p. 25)

Se ha demostrado que el código ternario Golay es útil para un enfoque de computación cuántica tolerante a fallos conocido como destilación de estado mágico . ^[1]

Véase también

• Gráfico de Berlekamp-van Lint-Seidel
• Código binario de Golay

Referencias

1. Prakash, Shiroman (septiembre de 2020). "Destilación del estado mágico con el código ternario de Golay". Actas de la Royal Society A: Ciencias matemáticas, físicas e ingeniería . 476 (2241): 20200187. arXiv : 2003.02717 . doi :10.1098/rspa.2020.0187.

• Barg, Alexander (1993), "En los albores de la teoría de códigos", The Mathematical Intelligencer , 15 (1): 20–26, doi :10.1007/BF03025254, MR  1199273
• Golay, MJE (junio de 1949), "Notas sobre codificación digital" (PDF) , Actas del IRE , 37 : 657, MR  4021352, archivado desde el original (PDF) el 19 de abril de 2015

Lectura adicional

• Blake, IF (1973), Teoría de codificación algebraica: historia y desarrollo , Stroudsburg, Pensilvania: Dowden, Hutchinson & Ross
• Conway, JH ; Sloane, NJA (1999), Empaquetamientos, celosías y grupos de esferas , Grundlehren der Mathematischen Wissenschaften, vol. 290 (3.ª ed.), Nueva York: Springer-Verlag, doi :10.1007/978-1-4757-6568-7, ISBN 0-387-98585-9, Sr.  1662447
• Griess, Robert L. Jr. (1998), Doce grupos esporádicos , Springer Monographs in Mathematics, Berlín: Springer-Verlag, doi :10.1007/978-3-662-03516-0, ISBN 3-540-62778-2, Sr.  1707296
• Cohen, Gérard ; Honkala, Iiro; Litsyn, Simon; Lobstein, Antoine (1997), Códigos de cobertura , Biblioteca matemática de Holanda Septentrional, vol. 54, Ámsterdam: Holanda Septentrional, ISBN 0-444-82511-8, Sr.  1453577
• Thompson, Thomas M. (1983), De códigos de corrección de errores a través de empaquetamientos de esferas hasta grupos simples , Carus Mathematical Monographs, vol. 21, Washington, DC: Asociación Matemática de América, ISBN 0-88385-023-0, Sr.  0749038