Un código de residuo cuadrático es un tipo de código cíclico .
Ejemplos de
Ejemplos de códigos de residuos cuadráticos incluyen el Código de Hamming terminado, la código binario de Golay sobre y el código ternario de Golay sobre.
Construcciones
Hay un código de residuo cuadrático de longitud sobre el campo finito cuando sea y son primos, es extraño, y es un módulo de residuo cuadrático. Su polinomio generador como código cíclico viene dado por
dónde es el conjunto de residuos cuadráticos de en el set y es un primitivo la raíz de la unidad en algún campo de extensión finito de . La condición que es un residuo cuadrático de asegura que los coeficientes de quedarse en cama . La dimensión del código es. Reemplazo por otro primitivo -ésima raíz de la unidad da como resultado el mismo código o un código equivalente, según sea o no es un residuo cuadrático de .
Una construcción alternativa evita las raíces de la unidad. Definir
para un adecuado . Cuándo escoger para asegurar eso . Si es extraño, elige , dónde o según si es congruente con o modulo . Luegotambién genera un código de residuo cuadrático; más precisamente el ideal de generado por corresponde al código de residuo cuadrático.
Peso
El peso mínimo de un código de longitud de residuo cuadrático es mayor que ; este es el límite de la raíz cuadrada .
Código extendido
Agregar un dígito de control de paridad general a un código de residuo cuadrático da un código de residuo cuadrático extendido . Cuándo (modificación ) un código de residuo cuadrático ampliado es auto-dual; de lo contrario, es equivalente pero no igual a su dual. Según el teorema de Gleason-Prange (llamado así por Andrew Gleason y Eugene Prange ), el grupo de automorfismo de un código de residuo cuadrático extendido tiene un subgrupo que es isomorfo a o .
Método de decodificación
Desde finales de 1980, se desarrollaron muchos algoritmos de decodificación algebraica para corregir errores en códigos de residuos cuadráticos. Estos algoritmos pueden lograr la capacidad (verdadera) de corrección de errores ⌊ (d - 1) / 2⌋ de los códigos de residuo cuadráticos con una longitud de código de hasta 113. Sin embargo, decodificación de códigos de residuo cuadráticos binarios largos y códigos de residuo cuadráticos no binarios sigue siendo un desafío. Actualmente, la decodificación de códigos de residuos cuadráticos sigue siendo un área de investigación activa en la teoría del código de corrección de errores.
Referencias
- FJ MacWilliams y NJA Sloane, The Theory of Error-Correcting Codes , North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
- Blahut, RE (septiembre de 2006), "El teorema de Gleason-Prange", IEEE Trans. Inf. Theory , Piscataway, NJ, EE.UU .: IEEE Press, 37 (5): 1269–1273, doi : 10.1109 / 18.133245.
- M. Elia, Decodificación algebraica del código Golay (23,12,7), IEEE Transactions on Information Theory, Volumen: 33, Edición: 1, pág. 150-151, enero de 1987.
- Reed, IS, Yin, X., Truong, TK, decodificación algebraica del código de residuo cuadrático (32, 16, 8). IEEE Trans. Inf. Teoría 36 (4), 876–880 (1990)
- Reed, IS, Truong, TK, Chen, X., Yin, X., La decodificación algebraica del código de residuo cuadrático (41, 21, 9). IEEE Trans. Inf. Teoría 38 (3), 974–986 (1992)
- Humphreys, JF Decodificación algebraica del código ternario (13, 7, 5) de residuo cuadrático. IEEE Trans. Inf. Theory 38 (3), 1122-1125 (mayo de 1992)
- Chen, X., Reed, IS, Truong, TK, Decodificando el código de residuo cuadrático (73, 37, 13). IEE Proc., Computación. Dígito. Tech. 141 (5), 253-258 (1994)
- Higgs, RJ, Humphreys, JF: Decodificación del código de residuo cuadrático ternario (23, 12, 8). IEE Proc., Com. 142 (3), 129-134 (junio de 1995)
- He, R., Reed, IS, Truong, TK, Chen, X., Decodificando el código de residuo cuadrático (47, 24, 11). IEEE Trans. Inf. Teoría 47 (3), 1181-1186 (2001)
- ….
- Y. Li, Y. Duan, HC Chang, H. Liu, TK Truong, Uso de la diferencia de síndromes para decodificar códigos de residuos cuadráticos, IEEE Trans. Inf. Teoría 64 (7), 5179-5190 (2018)