- Quadratic residue code
A quadratic residue code is a type of
cyclic code .There is a quadratic residue code of length pover the finite field GF(l) whenever pand l are primes, p is odd andl is a
quadratic residue modulo p.Its generator polynomial as a cyclic code is given by:f(x)=prod_{jin Q}(x-zeta^j)where Q is the set of quadratic residues ofp in the set 1,2,ldots,p-1} andzeta is a primitive pth root ofunity in some finite extension field of GF(l).The condition that l is a quadratic residueof p ensures that the coefficients of flie in GF(l). The dimension of the code isp+1)/2Replacing zeta by another primitive p-throot of unity zeta^r either results in the same codeor an equivalent code, according to whether or not ris a quadratic residue of p.
An alternative construction avoids roots of unity. Define:g(x)=c+sum_{jin Q}x^jfor a suitable cin GF(l). When l=2choose c to ensure that g(1)=1while if l is odd c=(1+sqrt{p^*})/2where p^*=p or p according to whetherp is congruent to 1 or 3modulo 4. Then g(x) also generatesa quadratic residue code; more precisely the ideal ofF_l [X] /langle X^p-1 angle generated by g(x)corresponds to the quadratic residue code.
The minimum weight of a quadratic residue code of length pis greater than sqrt{p}; this is the square root bound.
Adding an overall parity-check digit to a quadratic residue codegives an extended quadratic residue code. Whenpequiv 3 (mod 4) an extended quadratic residue code is self-dual; otherwise it is equivalent but notequal to its dual. By a theorem ofGleason and Prange, the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic toeither PSL_2(p) or SL_2(p).
Examples of quadraticresidue codes include the 7,4)
Hamming code over GF(2), the 23,12)binary Golay code over GF(2) and the 11,6)ternary Golay code over GF(3).References
F. J. MacWilliams and N. J. A. Sloane,"The Theory of Error-Correcting Codes",North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
Wikimedia Foundation. 2010.