Quadratic residue code
A quadratic residue code is a type of cyclic code.
Examples
Examples of quadraticresidue 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 lengthover 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 lengthis greater than ; this is the square root bound.
Extended code
Adding an overall parity-check digit to a quadratic residue codegives 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.