Código ternario Golay

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

En la teoría de la 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 tan grande como sea posible para un código ternario y, por lo tanto, el código ternario de Golay es un código perfecto . El código Golay ternario extendido es un código lineal [12, 6, 6] que se obtiene agregando un dígito de control de suma cero al código [11, 6, 5]. En la teoría de grupos finitos , el código Golay ternario extendido a veces se denomina código Golay ternario. ^{[ cita necesaria ]} ${\displaystyle [11,6,5]_{3}}$

Propiedades

Código ternario Golay

El código ternario Golay consta de 3 ⁶  = 729 palabras en código. Su matriz de verificació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 en clave 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 clave. 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 como máximo 2 resultados erróneos.

El conjunto de palabras en clave con peso 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 automorfismo del código Golay ternario (original) es el grupo M ₁₁ de Mathieu , 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 automorfismo del código Golay ternario extendido es 2. M ₁₂ , donde M ₁₂ es el grupo de Mathieu M ₁₂ .

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

Considere todas las palabras de código del código extendido que tienen solo seis dígitos distintos de cero. Los conjuntos de posiciones en las que aparecen estos dígitos distintos de cero forman el sistema 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 transpuesta 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 verificación de paridad es . ${\displaystyle [-B_{\mathrm {alt} }|I_{6}]^{T}}$

Los tres elementos del campo finito subyacente están representados aquí por , en lugar de por . También se entiende que ( es decir, el inverso aditivo de 1) y . Los productos de estos elementos de campo finitos son idénticos a los de los números enteros. Las sumas de filas y columnas se evalúan en 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 vectorial , de las filas de la matriz producen todas las palabras posibles contenidas en el código. Esto se conoce como la extensión 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 del generador y las matrices de verificación de paridad, es la matriz de todos ceros, y por intención. De hecho, este es un ejemplo de la definición misma de cualquier matriz de control 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 Golay fue publicado por Golay  (1949). Fue descubierto de forma independiente dos años antes por el entusiasta del fútbol finlandés 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 fallas conocido como destilación de estados mágicos . ^[1]

Ver también

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

Referencias

1. Prakash, Shiroman (septiembre de 2020). "Destilación del estado mágico con el código ternario Golay". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de 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 los 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

Otras lecturas

• Blake, IF (1973), Teoría de la codificación algebraica: historia y desarrollo , Stroudsburg, Pensilvania: Dowden, Hutchinson y 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, señor  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, señor  1707296
• Cohen, Gerard ; Honkala, Iiro; Litsyn, Simón; Lobstein, Antoine (1997), Códigos de cobertura , Biblioteca de Matemáticas de Holanda Septentrional, vol. 54, Ámsterdam: Holanda Septentrional, ISBN 0-444-82511-8, SEÑOR  1453577
• Thompson, Thomas M. (1983), Desde códigos de corrección de errores hasta paquetes de esferas hasta grupos simples , Carus Mathematical Monographs, vol. 21, Washington, DC: Asociación Matemática de América, ISBN 0-88385-023-0, señor  0749038