# Quadratic residue code

A **quadratic residue code** is a type of cyclic code.

There is a quadratic residue code of length over the finite field whenever and are primes, is odd and is a quadratic residue modulo . Its generator polynomial as a cyclic code is given by

where is the set of quadratic residues of in the set and is a primitive th root of unity in some finite extension field of . The condition that is a quadratic residue of ensures that the coefficients of lie in . The dimension of the code is

Replacing by another primitive -th root of unity either results in the same code or an equivalent code, according to whether or not is a quadratic residue of .

An alternative construction avoids roots of unity. Define

for a suitable . When choose to ensure that while if is odd where or according to whether is congruent to or modulo . Then also generates a quadratic residue code; more precisely the ideal of generated by corresponds to the quadratic residue code.

The minimum weight of a quadratic residue code of length
is greater than ; this is the **square root bound**.

Adding an overall parity-check digit to a quadratic residue code
gives an **extended quadratic residue code**. When
(mod ) 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 or .

Examples of quadratic residue codes include the Hamming code over , the binary Golay code over and the ternary Golay code over .

## References

- F. J. MacWilliams and N. J. A. Sloane,
*The Theory of Error-Correcting Codes*, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. - {{#invoke:citation/CS1|citation

|CitationClass=citation }}.