Quadratic residue code


A quadratic residue code is a type of cyclic code.

Examples

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

Constructions

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.
If is odd, choose ,
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.

Weight

The minimum weight of a quadratic residue code of length
is greater than ; 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
an extended quadratic
residue code is self-dual; otherwise it is equivalent but not
equal to its dual. By the Gleason–Prange theorem, the automorphism group of an extended quadratic residue
code has a subgroup which is isomorphic to
either or.