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 _{j\in 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 of unity in some finite extension field of $GF(l)$. The condition that $l$ is a quadratic residue of $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$-th root of unity $\zeta ^{r}$ either results in the same code or 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 Q}x^{j}$

for a suitable $c\in 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 generates a quadratic residue code; more precisely the ideal of $F_{l}[X]/\langle X^{p}-1\rangle$ 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 code gives an extended quadratic residue code. When $p\equiv 3$ (mod $4$) an extended quadratic residue code is self-dual; otherwise it is equivalent but not equal to its dual. By a theorem of Gleason and Prange, the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic to either $PSL_{2}(p)$ or $SL_{2}(p)$.

Examples of quadratic residue 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.

• Blahut, R. E. (September 2006), "The Gleason-Prange theorem", IEEE Trans. Inf. Theor., 37 (5), Piscataway, NJ, USA: IEEE Press: 1269–1273, doi:10.1109/18.133245.