Quadratic residue code

A quadratic residue code is a type of cyclic code.

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 by:$f(x)=prod\_\{jin\; Q\}(x-zeta^j)$where $Q$ is the set of quadratic residues of$p$ 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\_\{jin\; Q\}x^j$for a suitable $cin\; GF(l)$. When $l=2$choose $c$ to ensure that $g(1)=1$while if $l$ is odd $c=(1+sqrt\{p^*\})/2$where $p^*=p$ or $-p$ according to whether$p$ is congruent to $1$ or $3$modulo $4$. Then $g(x)$ also generatesa quadratic residue code; more precisely the ideal of$F\_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 $p$is 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. When$pequiv\; 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 codeover $GF(2)$, the $(23,12)$ binary Golay codeover $GF(2)$ and the $(11,6)$ ternary Golay codeover $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.