A quadratic residue code is a type of
cyclic code
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detecti ...
.
Examples
Examples of quadratic
residue codes include the
Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
over
, the
binary Golay code
In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection ...
over
and the
ternary Golay code
In coding theory, the ternary Golay codes are two closely related error-correcting codes.
The code generally known simply as the ternary Golay code is an 1, 6, 53-code, that is, it is a linear code over a ternary alphabet; the relative distance ...
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
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic no ...
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
(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
Andrew Mattei Gleason (19212008) was an American mathematician who made fundamental contributions to widely varied areas of mathematics, including the solution of Hilbert's fifth problem, and was a leader in reform and innovation in teaching at ...
and
Eugene Prange Eugene August Prange (July 30, 1917 – February 12, 2006)[Obituary](_blank) ), the automorphism group of an extended quadratic residue
code has a subgroup which is isomorphic to
either
or
.
Decoding Method
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.
References
*F. J. MacWilliams and N. J. A. Sloane, ''The Theory of Error-Correcting Codes'', North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
*{{citation
, last = Blahut , first = R. E.
, date = September 2006
, doi = 10.1109/18.133245
, issue = 5
, journal = IEEE Trans. Inf. Theory
, location = Piscataway, NJ, USA
, pages = 1269–1273
, publisher = IEEE Press
, title = The Gleason-Prange theorem
, volume = 37.
*M. Elia, Algebraic decoding of the (23,12,7) Golay code, IEEE Transactions on Information Theory, Volume: 33 , Issue: 1 , pg. 150-151, January 1987.
*Reed, I.S., Yin, X., Truong, T.K., Algebraic decoding of the (32, 16, 8) quadratic residue code. IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
*Reed, I.S., Truong, T.K., Chen, X., Yin, X., The algebraic decoding of the (41, 21, 9) quadratic residue code. IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
*Humphreys, J.F. Algebraic decoding of the ternary (13, 7, 5) quadratic-residue code. IEEE Trans. Inf. Theory 38(3), 1122–1125 (May 1992)
*Chen, X., Reed, I.S., Truong, T.K., Decoding the (73, 37, 13) quadratic-residue code. IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
*Higgs, R.J., Humphreys, J.F.: Decoding the ternary (23, 12, 8) quadratic-residue code. IEE Proc., Comm. 142(3), 129–134 (June 1995)
*He, R., Reed, I.S., Truong, T.K., Chen, X., Decoding the (47, 24, 11) quadratic residue code. IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
*….
*Y. Li, Y. Duan, H. C. Chang, H. Liu, T. K. Truong, Using the difference of syndromes to decode quadratic residue codes, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)
Quadratic residue
Coding theory