Quadratic residue code

From Wikipedia, the free encyclopedia

A quadratic residue code is a type of cyclic code.

There is a quadratic residue code of length $p$ over the finite field $G F (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 $ζ$ is a primitive $p$ th root of unity in some finite extension field of $G F (l)$ . The condition that $l$ is a quadratic residue of $p$ ensures that the coefficients of $f$ lie in $G F (l)$ . The dimension of the code is $(p + 1) / 2$

Replacing $ζ$ by another primitive $p$ -th root of unity $ζ 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 $P S L 2 (p)$ or $S L 2 (p)$ .

Examples of quadratic residue codes include the $(7,4)$ Hamming code over $G F (2)$ , the $(23,12)$ binary Golay code over $G F (2)$ and the $(11,6)$ ternary Golay code over $G F (3)$ .