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 el 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 requerida ]
Código Golay ternario perfecto | |
---|---|
Lleva el nombre de | Marcel JE Golay |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | 11 |
Longitud del mensaje | 6 |
Velocidad | 11/6 ~ 0.545 |
Distancia | 5 |
Tamaño del alfabeto | 3 |
Notación | -código |
Código Golay ternario extendido | |
---|---|
Lleva el nombre de | Marcel JE Golay |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | 12 |
Longitud del mensaje | 6 |
Velocidad | 6/12 = 0,5 |
Distancia | 6 |
Tamaño del alfabeto | 3 |
Notación | -código |
Propiedades
Código de Golay ternario
El código ternario de Golay consta de 3 6 = 729 palabras de código. Su matriz de verificación de paridad es
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 de 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 3 ( es decir, el campo Galois GF (3) ).
Utilizado en un grupo de fútbol con 11 juegos, 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 en clave con peso Hamming 5 tiene un diseño de 3- (11,5,4) .
La matriz generadora dada por Golay (1949, Tabla 1.) es
El grupo de automorfismo del código ternario Golay (original) es el grupo de Mathieu M11 , 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
El grupo de automorfismo del código Golay ternario extendido es 2. M 12 , donde M 12 es el grupo de Mathieu M12 .
El código Golay ternario extendido se puede construir como el tramo de las filas de una matriz de Hadamard de orden 12 sobre el campo F 3 .
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 ocurren 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
La matriz de verificación de paridad correspondiente para esta matriz generadora es , dónde denota la transposición de la matriz.
Una matriz generadora alternativa para este código es
Y su matriz de verificación de paridad es .
Los tres elementos del campo finito subyacente están representados aquí por , en lugar de por . También se entiende que( es decir, el aditivo inverso de 1) y. Los productos de estos elementos de campo finito son idénticos a los de los números enteros. Las sumas de filas y columnas se evalúan en módulo 3.
Las combinaciones lineales, o la suma de vectores , 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 del generador 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 el matriz de todos los ceros, y por intención. De hecho, este es un ejemplo de la definición misma de cualquier matriz de verificación de paridad con respecto a su matriz generadora.
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 al billar 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 la computación cuántica tolerante a fallas conocida como destilación de estado mágico . [1]
Ver también
Referencias
- 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", Actas de la IRE , 37 : 657, MR 4021352
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) , Empaquetaduras , celosías y grupos de esferas, Grundlehren der Mathematischen Wissenschaften, 290 (3.a ed.), Nueva York: Springer-Verlag, doi : 10.1007 / 978-1-4757-6568-7 , ISBN 0-387-98585-9, MR 1662447
- Griess, Robert L. Jr. (1998), Doce grupos esporádicos , Monografías de Springer en matemáticas, Berlín: Springer-Verlag, doi : 10.1007 / 978-3-662-03516-0 , ISBN 3-540-62778-2, MR 1707296
- Cohen, Gérard; Honkala, Iiro; Litsyn, Simon; Lobstein, Antoine (1997), Covering codes , North-Holland Mathematical Library, 54 , Amsterdam: North-Holland, ISBN 0-444-82511-8, MR 1453577
- Thompson, Thomas M. (1983), From Error Correcting Codes through Sphere Packings to Simple Groups , Carus Mathematical Monographs, 21 , Washington, DC: Asociación Matemática de América, ISBN 0-88385-023-0, MR 0749038
- ^ Prakash, Shiroman (septiembre de 2020). "Destilación en estado mágico con el código ternario 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 .