Kvadratisk restkod

En kvadratisk restkod är en typ av cyklisk kod .

Exempel

Exempel på kvadratiska restkoder inkluderar $(7,4)$ Hamming-koden över $GF(2)$ , ${\displaystyle (23$ $GF( 3)$ Golay-kod över $GF(2)$ $(11,6)$ den ternära Golay-koden över .

Konstruktioner

Det finns en kvadratisk restkod med längden $p$ över det finita fältet $GF(l)$ när $p$ och $l$ är primtal, $p$ är udda, och $l$ är en kvadratisk restmodulo p $\displaystyle p}$ . Dess generatorpolynom som en cyklisk kod ges av

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

där $Q$ är mängden kvadratiska rester av $p$ i mängden $\{1,2,\ldots ,p-1\ }$ och $\zeta$ är en primitiv ${\displaystyle p}:$ te roten av enhet i något ändligt förlängningsfält av $GF(l)$ . Villkoret att $l$ är en kvadratisk rest av $p$ säkerställer att koefficienterna för $f$ ligger i $GF(l)$ . Dimensionen på koden är $(p+1)/2$ . Att ersätta $\zeta$ med en annan primitiv $p$ -th roten av enhet $\zeta ^{r}$ resulterar antingen i samma kod eller en ekvivalent kod, beroende på om eller inte $r$ är en kvadratisk rest av $p$ .

En alternativ konstruktion undviker rötter till enhet. Definiera

g(x)=c+\summa _{j\in Q}x^{j}

för en lämplig $c\in GF(l)$ . När $l=2$ välj $c$ för att säkerställa att $g(1)=1$ . Om $l$ är udda, välj ${\displaystyle c=(1+{\sqrt {p^{*}}})/2} ,$ där $p^{*}=p$ eller $-p$ beroende på om $p$ är kongruent med $1$ eller $3$ modulo $4$ . Sedan $g(x)$ också en kvadratisk restkod; närmare bestämt idealet för $F_{l}[X]/\langle X^{p}-1\rangle$ genererat av $g (x)$ motsvarar den kvadratiska restkoden.

Vikt

Minimivikten för en kvadratisk restkod med längden $p$ är större än ${\sqrt {p}$ } ; detta är kvadratroten bunden .

Utökad kod

Att lägga till en övergripande paritetskontrollsiffra till en kvadratisk restkod ger en utökad kvadratisk restkod . När $p\equiv 3$ (mod $4$ ) är en utökad kvadratisk restkod självdual; annars är den likvärdig men inte lika med dess dubbla. Enligt Gleason-Prange-satsen (uppkallad efter Andrew Gleason och Eugene Prange ) har automorfismgruppen i en utökad kvadratisk restkod en undergrupp som är isomorf till antingen $PSL_{2}(p)$ eller $SL_{2}(p)$ .

Avkodningsmetod

Sedan slutet av 1980 har många algebraiska avkodningsalgoritmer utvecklats för att korrigera fel på kvadratiska restkoder. Dessa algoritmer kan uppnå den (sanna) felkorrigerande kapaciteten $\lfloor (d-1)/2\rfloor$ för de kvadratiska restkoderna med kodlängden upp till 113. , avkodning av långa binära kvadratiska restkoder och icke-binära kvadratiska restkoder fortsätter att vara en utmaning. För närvarande är avkodning av kvadratiska restkoder fortfarande ett aktivt forskningsområde inom teorin om felkorrigerande kod.

FJ MacWilliams och NJA Sloane, The Theory of Error-Correcting Codes , North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
Blahut, RE (september 2006), "The Gleason-Prange theorem", IEEE Trans. Inf. Theory , Piscataway, NJ, USA: IEEE Press, 37 (5): 1269–1273, doi : 10.1109/18.133245 .
M. Elia, Algebraisk avkodning av (23,12,7) Golay-koden, IEEE Transactions on Information Theory, Volym: 33 , Utgåva: 1 , sid. 150-151, januari 1987.
Reed, IS, Yin, X., Truong, TK, algebraisk avkodning av den (32, 16, 8) kvadratiska restkoden. IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
Reed, IS, Truong, TK, Chen, X., Yin, X., Den algebraiska avkodningen av den (41, 21, 9) kvadratiska restkoden. IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
Humphreys, JF Algebraisk avkodning av den ternära (13, 7, 5) kvadratiska restkoden. IEEE Trans. Inf. Theory 38(3), 1122–1125 (maj 1992)
Chen, X., Reed, IS, Truong, TK, Avkodning av (73, 37, 13) kvadratisk restkod. IEE Proc., Comput. Siffra. Tech. 141(5), 253–258 (1994)
Higgs, RJ, Humphreys, JF: Avkodning av den ternära (23, 12, 8) kvadratiska restkoden. IEE Proc., Comm. 142(3), 129–134 (juni 1995)
He, R., Reed, IS, Truong, TK, Chen, X., Avkodning av den (47, 24, 11) kvadratiska restkoden. IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
….
Y. Li, Y. Duan, HC Chang, H. Liu, TK Truong, Använda skillnaden mellan syndrom för att avkoda kvadratiska restkoder, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)