Quadratic residue code explained

Quadratic residue code should not be confused with QR Code.

A quadratic residue code is a type of cyclic code.

Examples

Examples of quadraticresidue codes include the

( 7 , 4 ) Hamming codeover GF( 2 ) , the ( 23 , 12 ) binary Golay codeover GF( 2 ) and the ( 11 , 6 ) ternary Golay codeover GF( 3 ) .

Constructions

There is a quadratic residue code of length

p over the finite field GF(l) whenever p and l are primes, p is odd, and l is a quadratic residue modulo p .Its generator polynomial as a cyclic code is given byf(x) = \prod _{j\in} (x - \zeta ^{j)} where Q is the set of quadratic residues ofp in the set \{ 1 , 2 ,\ldots,p -1 \} and\zeta is a primitive p th root ofunity in some finite extension field of GF(l) .The condition that l is a quadratic residueof p ensures that the coefficients of f lie in GF(l) . The dimension of the code is(p +1 )/ 2 .Replacing \zeta by another primitive p -throot of unity \zeta ^{r} either results in the same codeor an equivalent code, according to whether or not r is a quadratic residue of p .

An alternative construction avoids roots of unity. Define

g(x) = c + \sum _{j\in} x ^{j} for a suitable c\in GF(l) . When l =2 choose c to ensure that g( 1 ) =1 .If l is odd, choose c = ( 1+ \sqrt{p ^{*})/2} ,where p ^{*=p} or - p according to whetherp is congruent to 1 or 3 modulo 4 . Then g(x) also generatesa quadratic residue code; more precisely the ideal ofF _{l[X]/\langle} X ^{p-1\rangle} generated by g(x) corresponds to the quadratic residue code.

Weight

The minimum weight of a quadratic residue code of length

p is greater than \sqrt{p} ; this is the square root bound.

Extended code

Adding an overall parity-check digit to a quadratic residue codegives an extended quadratic residue code. When

p\equiv 3 (mod 4 ) an extended quadraticresidue code is self-dual; otherwise it is equivalent but notequal to its dual. By the Gleason–Prange theorem (named for Andrew Gleason and Eugene Prange), the automorphism group of an extended quadratic residuecode has a subgroup which is isomorphic toeither PSL _{2(p)} or SL _{2(p)} .

Decoding Method

Since late 1980, there are many algebraic decoding algorithms were developed for correcting errors on quadratic residue codes. These algorithms can achieve the (true) error-correcting capacity

\lfloor(d -1 )/ 2 \rfloor of the quadratic residue codes with the code length up to 113. However, decoding of long binary quadratic residue codes and non-binary quadratic residue codes continue to be a challenge. Currently, decoding quadratic residue codes is still an active research area in the theory of error-correcting code.

References

• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
• .
• M. Elia, Algebraic decoding of the (23,12,7) Golay code, IEEE Transactions on Information Theory, Volume: 33, Issue: 1, pg. 150-151, January 1987.
• Reed, I.S., Yin, X., Truong, T.K., Algebraic decoding of the (32, 16, 8) quadratic residue code. IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
• Reed, I.S., Truong, T.K., Chen, X., Yin, X., The algebraic decoding of the (41, 21, 9) quadratic residue code. IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
• Humphreys, J.F. Algebraic decoding of the ternary (13, 7, 5) quadratic-residue code. IEEE Trans. Inf. Theory 38(3), 1122–1125 (May 1992)
• Chen, X., Reed, I.S., Truong, T.K., Decoding the (73, 37, 13) quadratic-residue code. IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
• Higgs, R.J., Humphreys, J.F.: Decoding the ternary (23, 12, 8) quadratic-residue code. IEE Proc., Comm. 142(3), 129–134 (June 1995)
• He, R., Reed, I.S., Truong, T.K., Chen, X., Decoding the (47, 24, 11) quadratic residue code. IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
• ….
• Y. Li, Y. Duan, H. C. Chang, H. Liu, T. K. Truong, Using the difference of syndromes to decode quadratic residue codes, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)