Quadratic residue code

A quadratic residue code is a type of cyclic code.

Examples

Examples of quadratic residue codes include the ${\displaystyle (7,4)}$ Hamming code over ${\displaystyle GF(2)}$, the ${\displaystyle (23,12)}$ binary Golay code over ${\displaystyle GF(2)}$ and the ${\displaystyle (11,6)}$ ternary Golay code over ${\displaystyle GF(3)}$.

Constructions

There is a quadratic residue code of length ${\displaystyle p}$ over the finite field ${\displaystyle GF(l)}$ whenever ${\displaystyle p}$ and ${\displaystyle l}$ are primes, ${\displaystyle p}$ is odd, and ${\displaystyle l}$ is a quadratic residue modulo ${\displaystyle p}$. Its generator polynomial as a cyclic code is given by

${\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j})}$

where ${\displaystyle Q}$ is the set of quadratic residues of ${\displaystyle p}$ in the set ${\displaystyle \{1,2,\ldots ,p-1\}}$ and ${\displaystyle \zeta }$ is a primitive ${\displaystyle p}$th root of unity in some finite extension field of ${\displaystyle GF(l)}$. The condition that ${\displaystyle l}$ is a quadratic residue of ${\displaystyle p}$ ensures that the coefficients of ${\displaystyle f}$ lie in ${\displaystyle GF(l)}$. The dimension of the code is ${\displaystyle (p+1)/2}$. Replacing ${\displaystyle \zeta }$ by another primitive ${\displaystyle p}$-th root of unity ${\displaystyle \zeta ^{r}}$ either results in the same code or an equivalent code, according to whether or not ${\displaystyle r}$ is a quadratic residue of ${\displaystyle p}$.

An alternative construction avoids roots of unity. Define

${\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}$

for a suitable ${\displaystyle c\in GF(l)}$. When ${\displaystyle l=2}$ choose ${\displaystyle c}$ to ensure that ${\displaystyle g(1)=1}$. If ${\displaystyle l}$ is odd, choose ${\displaystyle c=(1+{\sqrt {p^{*}}})/2}$, where ${\displaystyle p^{*}=p}$ or ${\displaystyle -p}$ according to whether ${\displaystyle p}$ is congruent to ${\displaystyle 1}$ or ${\displaystyle 3}$ modulo ${\displaystyle 4}$. Then ${\displaystyle g(x)}$ also generates a quadratic residue code; more precisely the ideal of ${\displaystyle F_{l}[X]/\langle X^{p}-1\rangle }$ generated by ${\displaystyle g(x)}$ corresponds to the quadratic residue code.

Weight

The minimum weight of a quadratic residue code of length ${\displaystyle p}$ is greater than ${\displaystyle {\sqrt {p}}}$; this is the square root bound.

Extended code

Adding an overall parity-check digit to a quadratic residue code gives an extended quadratic residue code. When ${\displaystyle p\equiv 3}$ (mod ${\displaystyle 4}$) an extended quadratic residue code is self-dual; otherwise it is equivalent but not equal to its dual. By the Gleason–Prange theorem (named for Andrew Gleason and Eugene Prange), the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic to either ${\displaystyle PSL_{2}(p)}$ or ${\displaystyle SL_{2}(p)}$.

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. Theory, Piscataway, NJ, USA: IEEE Press, 37 (5): 1269–1273, doi:10.1109/18.133245.