TOPICS
Search

Quadratic Residue Code


A binary quadratic residue code of prime length p=+/-1  (mod8) is a cyclic code whose defining zeros are zeta^a for the nonzero quadratic residues a modulo p, where zeta is a primitive pth root of unity over a suitable extension of F_2 (MacWilliams and Sloane 1977, Ch. 16). Using the nonresidues instead gives an equivalent code. The code has dimension (p+1)/2, and its minimum Hamming distance satisfies d>=sqrt(p). The binary Hamming code of length 7 and Golay code of length 23 are examples.

Van Lint and MacWilliams (1978) generalized this construction to lengths q that are odd prime powers with q=+/-1  (mod8). The coordinates are indexed by F_q, and the defining transform uses its additive characters, with zeros indexed by its nonzero squares. These generalized quadratic residue codes have dimension (q+1)/2 and d>=sqrt(q); they need not be cyclic for nonprime q. For square q, the minimum distance is exactly sqrt(q).

Gaborit and Lebacque (2026, Theorem 3.1) give a deterministic algorithm correcting every error pattern of weight at most

 |_(sqrt(q)-1)/2_|

in all these binary generalized quadratic residue codes, using O(q^(9/2)) operations in F_q. This is a uniform guarantee from the square-root bound; for prime lengths it need not reach half the actual minimum distance.


See also

Cyclic Code, Golay Code, Hamming Code, Quadratic Residue

Explore with Wolfram|Alpha

References

MacWilliams, F. J. and Sloane, N. J. A. The Theory of Error-Correcting Codes. Amsterdam, Netherlands: North-Holland, 1977.van Lint, J. H. and MacWilliams, F. J. "Generalized Quadratic Residue Codes." IEEE Trans. Inform. Th. 24, 730-737, 1978.Gaborit, P. and Lebacque, P. "A Polynomial-time Decoding Algorithm up to Half the Square-root Bound for Quadratic Residue and Generalized Quadratic Residue Codes." 16 Nov 2026. https://arxiv.org/abs/2611.21888v1.

Cite this as:

Weisstein, Eric W. "Quadratic Residue Code." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QuadraticResidueCode.html

Subject classifications