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$ .

Some important examples of error-correcting codes are quadratic residue codes including 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)$ .