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