Código de residuo cuadrático

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

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

Hay un código de residuo cuadrático de longitud${\displaystyle p}$ sobre el campo finito${\displaystyle GF(l)}$cuando sea${\displaystyle p}$ y${\displaystyle l}$son primos,${\displaystyle p}$es extraño, y ${\displaystyle l}$es un residuo cuadrático módulo${\displaystyle p}$Su polinomio generador como código cíclico viene dado por $${\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j}),}$$ dónde${\displaystyle Q}$es el conjunto de residuos cuadráticos de ${\displaystyle p}$en el conjunto${\displaystyle \{1,2,\ldots ,p-1\}}$y ${\displaystyle \zeta }$es un primitivo${\displaystyle p}$raíz enésima de la unidad en algún campo de extensión finito de${\displaystyle GF(l)}$. La condición de que${\displaystyle l}$es un residuo cuadrático de${\displaystyle p}$asegura que los coeficientes de${\displaystyle f}$ quedarse en cama${\displaystyle GF(l)}$. La dimensión del código es ${\displaystyle (p+1)/2}$. Reemplazando${\displaystyle \zeta }$por otro primitivo${\displaystyle p}$raíz -ésima de la unidad${\displaystyle \zeta ^{r}}$da como resultado el mismo código o un código equivalente, según si se cumple o no${\displaystyle r}$ es un residuo cuadrático de${\displaystyle p}$.

Una construcción alternativa evita las raíces de la unidad. Definir $${\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}$$ para un adecuado${\displaystyle c\in GF(l)}$. Cuando${\displaystyle l=2}$ elegir${\displaystyle c}$para asegurar que${\displaystyle g(1)=1}$. Si${\displaystyle l}$es extraño, elige ${\displaystyle c=(1+{\sqrt {p^{*}}})/2}$, dónde${\displaystyle p^{*}=p}$o${\displaystyle -p}$según si ${\displaystyle p}$es congruente con${\displaystyle 1}$o${\displaystyle 3}$ módulo${\displaystyle 4}$. Entonces${\displaystyle g(x)}$también genera un código de residuo cuadrático; más precisamente el ideal de ${\displaystyle F_{l}[X]/\langle X^{p}-1\rangle }$generado por${\displaystyle g(x)}$ corresponde al código de residuo cuadrático.

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

Agregar un dígito de control de paridad general a un código de residuo cuadrático da como resultado un código de residuo cuadrático extendido . Cuando ${\displaystyle p\equiv 3}$(mod${\displaystyle 4}$) un código de residuo cuadrático extendido es autodual; de lo contrario es equivalente pero no igual a su dual. Por el teorema de Gleason-Prange (llamado así por Andrew Gleason y Eugene Prange ), el grupo de automorfismos de un código de residuo cuadrático extendido tiene un subgrupo que es isomorfo a o${\displaystyle PSL_{2}(p)}$o${\displaystyle SL_{2}(p)}$.

Desde finales de 1980, se han desarrollado muchos algoritmos de decodificación algebraica para corregir errores en códigos de residuos cuadráticos. Estos algoritmos pueden alcanzar la capacidad de corrección de errores (verdadera).${\displaystyle \lfloor (d-1)/2\rfloor }$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 de códigos correctores de errores.

• FJ MacWilliams y NJA Sloane, La teoría de los códigos correctores de errores , North-Holland Publishing Co., Ámsterdam-Nueva York-Oxford, 1977.
• Blahut, RE (septiembre de 2006), "El teorema de Gleason-Prange", IEEE Trans. Inf. Theory , 37 (5), Piscataway, NJ, 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ágs.  150–151, enero de 1987.
• Reed, IS, Yin, X., Truong, TK, Decodificación algebraica del código de residuos cuadráticos (32, 16, 8). IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
• Reed, IS, Truong, TK, Chen, X., Yin, X., La decodificación algebraica del código de residuos cuadráticos (41, 21, 9). IEEE Trans. Inf. Theory 38(3), 974–986 (1992).
• Humphreys, JF Decodificación algebraica del código cuadrático de residuos ternario (13, 7, 5). IEEE Trans. Inf. Theory 38(3), 1122–1125 (mayo de 1992).
• Chen, X., Reed, IS, Truong, TK, Decodificación del código de residuos cuadráticos (73, 37, 13). IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994).
• Higgs, RJ, Humphreys, JF: Decodificación del código cuadrático de residuos ternario (23, 12, 8). IEE Proc., Comm. 142(3), 129–134 (junio de 1995).
• He, R., Reed, IS, Truong, TK, Chen, X., Decodificación del código de residuos cuadráticos (47, 24, 11). IEEE Trans. Inf. Theory 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. Theory 64(7), 5179–5190 (2018).