A quadratic residue code is a type of cyclic code.
Examples of quadratic residue codes include the
Hamming code over
binary Golay code over
ternary Golay code over
There is a quadratic residue code of length
over the finite field
is a quadratic residue modulo
Its generator polynomial as a cyclic code is given by where
is the set of quadratic residues of
th root of unity in some finite extension field of
is a quadratic residue of
ensures that the coefficients of
The dimension of the code is
-th root of unity
is a quadratic residue of
An alternative construction avoids roots of unity.
Define for a suitable
also generates a quadratic residue code; more precisely the ideal of
corresponds to the quadratic residue code.
The minimum weight of a quadratic residue code of length
; this is the square root bound.
Adding an overall parity-check digit to a quadratic residue code gives an extended quadratic residue code.
) 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
Since late 1980, there are many algebraic decoding algorithms were developed for correcting errors on quadratic residue codes.
These algorithms can achieve the (true) error-correcting capacity
of the quadratic residue codes with the code length up to 113.
However, decoding of long binary quadratic residue codes and non-binary quadratic residue codes continue to be a challenge.
Currently, decoding quadratic residue codes is still an active research area in the theory of error-correcting code.