Quadratic residue code
Encyclopedia
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 a theorem of
Gleason and 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
.
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 ofunity in some finite extension field of
.The condition that
is a quadratic residueof
ensures that the coefficients of lie in
. The dimension of the code isReplacing
by another primitive -throot of unity
either results in the same codeor 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 generatesa 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 quadraticresidue code is self-dual; otherwise it is equivalent but not
equal to its dual. By a theorem of
Gleason and 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 codeHamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
over
, the binary Golay codeBinary Golay code
In mathematics and electronics engineering, a binary Golay code is a type of error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics....
over
and the ternary Golay codeTernary Golay code
There are two closely related error-correcting codes known as ternary Golay codes. The code generally known simply as the ternary Golay code is a perfect [11, 6, 5] ternary linear code; the extended ternary Golay code is a [12, 6, 6] linear code obtained by adding a zero-sum check digit to the...
over
.