Código de residuo cuadrático

Un código de residuo cuadrático es un tipo de código cíclico .

Ejemplos

Ejemplos de códigos de residuos cuadráticos incluyen el código Hamming over , el código binario Golay over y el código ternario Golay over . ${\displaystyle (7,4)}$ ${\displaystyle GF(2)}$ ${\displaystyle (23,12)}$ ${\displaystyle GF(2)}$ ${\displaystyle (11,6)}$ ${\displaystyle GF(3)}$

Construcciones

Hay un código de residuo cuadrático de longitud sobre el campo finito siempre que y sean primos, sea impar y sea un módulo de residuo cuadrático . Su polinomio generador como código cíclico viene dado por ${\displaystyle p}$ ${\displaystyle GF(l)}$ ${\displaystyle p}$ ${\displaystyle l}$ ${\displaystyle p}$ ${\displaystyle l}$ ${\displaystyle p}$

${\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j})}$

donde es el conjunto de residuos cuadráticos de en el conjunto y es una raíz primitiva de la unidad en algún campo de extensión finito de . La condición de que sea un residuo cuadrático de garantiza que los coeficientes de se encuentren en . La dimensión del código es . Reemplazar por otra primitiva -ésima raíz de la unidad da como resultado el mismo código o un código equivalente, según sea o no un residuo cuadrático de . ${\displaystyle Q}$ ${\displaystyle p}$ ${\displaystyle \{1,2,\ldots ,p-1\}}$ ${\displaystyle \zeta }$ ${\displaystyle p}$ ${\displaystyle GF(l)}$ ${\displaystyle l}$ ${\displaystyle p}$ ${\displaystyle f}$ ${\displaystyle GF(l)}$ ${\displaystyle (p+1)/2}$ ${\displaystyle \zeta }$ ${\displaystyle p}$ ${\displaystyle \zeta ^{r}}$ ${\displaystyle r}$ ${\displaystyle p}$

Una construcción alternativa evita las raíces de unidad. Definir

${\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}$

para un adecuado . Cuando elija asegurarse de eso . Si es impar, elija , donde o según sea congruente o módulo . Luego tambié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. ${\displaystyle c\in GF(l)}$ ${\displaystyle l=2}$ ${\displaystyle c}$ ${\displaystyle g(1)=1}$ ${\displaystyle l}$ ${\displaystyle c=(1+{\sqrt {p^{*}}})/2}$ ${\displaystyle p^{*}=p}$ ${\displaystyle -p}$ ${\displaystyle p}$ ${\displaystyle 1}$ ${\displaystyle 3}$ ${\displaystyle 4}$ ${\displaystyle g(x)}$ ${\displaystyle F_{l}[X]/\langle X^{p}-1\rangle }$ ${\displaystyle g(x)}$

Peso

El peso mínimo de un código de residuo cuadrático de longitud es mayor que ; este es el límite de la raíz cuadrada . ${\displaystyle p}$ ${\displaystyle {\sqrt {p}}}$

código extendido

Agregar un dígito de verificación de paridad general a un código de residuo cuadrático da un código de residuo cuadrático extendido . Cuando (mod ) un código de residuo cuadrático extendido es autodual; 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 cualquiera o . ${\displaystyle p\equiv 3}$ ${\displaystyle 4}$ ${\displaystyle PSL_{2}(p)}$ ${\displaystyle SL_{2}(p)}$

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 (verdadera) capacidad de corrección de errores de los códigos de residuos cuadráticos con una longitud de código de hasta 113. Sin embargo, la decodificación de códigos de residuos cuadráticos binarios largos y códigos de residuos 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. ${\displaystyle \lfloor (d-1)/2\rfloor }$

Referencias

• FJ MacWilliams y NJA Sloane, La teoría de los códigos correctores de errores , North-Holland Publishing Co., Amsterdam-Nueva York-Oxford, 1977.
• Blahut, RE (septiembre de 2006), "El teorema de Gleason-Prange", IEEE Trans. inf. Teoría , 37 (5), Piscataway, Nueva Jersey, EE. UU.: IEEE Press: 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, Número: 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). Traducción IEEE. 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). Traducción IEEE. inf. Teoría 38 (3), 974–986 (1992)
• Humphreys, JF Decodificación algebraica del código de residuo cuadrático ternario (13, 7, 5). Traducción IEEE. inf. Teoría 38 (3), 1122-1125 (mayo de 1992)
• Chen, X., Reed, IS, Truong, TK, Decodificando el código de residuos cuadráticos (73, 37, 13). IEE Proc., Computación. Dígito. Tecnología. 141(5), 253–258 (1994)
• Higgs, RJ, Humphreys, JF: Decodificación del código de residuo cuadrático ternario (23, 12, 8). EEI Proc., Comunicaciones. 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). Traducción IEEE. 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)