Description
Member of a quadruple of cyclic \(q\)-ary codes of prime length \(n\) where \(q\) is prime and a quadratic-residue modulo \(n\) [1; Def. 3.2.8]. The codes are constructed using quadratic residues and nonresidues of \(n\). The definition extends to prime-power alphabet sizes and to prime-power lengths [2,3][1; Rem. 3.2.9]. A quadratic-residue code of prime length \(p\) has dimension \((p+1)/2\) [1; Sec. 3.2.1].
The roots of the generator polynomial \(r(x)\) of the first code (see Cyclic-to-polynomial correspondence) are all of the inequivalent quadratic residues of \(n\), and the second code’s generator polynomial is \((x-1)r(x)\). The roots of the generator polynomial \(a(x)\) of the third code are all inequivalent nonresidues of \(n\), and the fourth code’s generator polynomial is \((x-1)a(x)\). The codes corresponding to polynomials \(r,a\) are often called augmented quadratic-residue codes, while the remaining codes are called expurgated.
The extended versions of odd-like quadratic-residue codes have automorphism groups containing \(PSL(2,p)\) [1; Thm. 3.2.11]; such codes are the only codes with these symmetries [4].
Protection
For odd-like quadratic-residue codes of prime length, the common minimum distance \(d\) satisfies \(d^2 \geq n\); if \(-1\) is a quadratic non-residue, then \(d^2-d+1 \geq n\) [5; Thm. 2.7.4].Cousins
- Combinatorial design— The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [9–11], including \(3\)-designs [12].
- \([2m+2,m+1]\) Karlin code— Karlin codes can be mapped to extended cyclic and extended quadratic-residue codes over \(\mathbb{F}_4\) [13,14][7; Ch. 16][15; Sec. 2.4.2] by identifying \((0,\omega,\bar{\omega},1)\) with \((00),(10),(01),(11)\) [13].
- \([2q+2,q+1]_3\) Pless symmetry code— Pless symmetry codes for lengths 24, 48, and 60 have the same Hamming weight enumerators as the corresponding extended QR codes but are not equivalent [7; pg. 511].
- \([6,3,4]_4\) Hexacode— The hexacode is the smallest example of an extended quadratic-residue code of Type \(4^H\) [15; Sec. 2.4.6][8; Exer. 363].
- \([4,2,3]_4\) RS\(_4\) code— The RS\(_4\) code is the smallest quaternary extended QR code [15; Sec. 2.4.2]. The shortened RS\(_4\) code is the smallest quaternary QR code.
- Octacode— The octacode is equivalent to the length-eight quaternary extended quadratic-residue code over \(\mathbb{Z}_4\) [16].
- \([[13,1,5]]\) quantum QR code— The stabilizer group of the \([[13,1,5]]\) code is defined by a quaternary QR code of length 13 [17; pg. 11].
- Quantum quadratic-residue (QR) code— Quantum quadratic-residue codes are quantum analogues of \(q\)-ary quadratic-residue codes.
Primary Hierarchy
References
- [1]
P. R. J. Östergård, “Construction and Classification of Codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 61-78 DOI
- [2]
J. van Lint and F. MacWilliams, “Generalized quadratic residue codes”, IEEE Transactions on Information Theory 24, 730 (1978) DOI
- [3]
J. H. Lint, “Generalized quadratic-residue codes”, Algebraic Coding Theory and Applications 285 (1979) DOI
- [4]
C. Ding, H. Liu, and V. D. Tonchev, “All binary linear codes that are invariant under \(\PSL_2(n)\)”, (2017) arXiv:1704.01199
- [5]
C. Ding, “Cyclic Codes over Finite Fields”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 45-60 DOI
- [6]
K. Ivanov and R. L. Urbanke, “Capacity-achieving codes: a review on double transitivity”, (2020) arXiv:2010.15453
- [7]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [8]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [9]
E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [10]
E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [11]
M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
- [12]
M. Awada, “Infinite series of \(3\)-designs in the extended quadratic residue code”, (2024) arXiv:2310.14281
- [13]
P. Gaborit, V. Pless, P. Solé, and O. Atkin, “Type II Codes over F4”, Finite Fields and Their Applications 8, 171 (2002) DOI
- [14]
M. Karlin and F. J. MacWilliams, “Quadratic residue codes over GF(4) and their binary images”, in IEEE Int. Symp. on Information Theory, Asilomar, CA, 1972
- [15]
Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [16]
A. Bonnecaze, P. Sole, and A. R. Calderbank, “Quaternary quadratic residue codes and unimodular lattices”, IEEE Transactions on Information Theory 41, 366 (1995) DOI
- [17]
F. Vatan, V. P. Roychowdhury, and M. P. Anantram, “Spatially Correlated Qubit Errors and Burst-Correcting Quantum Codes”, (1997) arXiv:quant-ph/9704019
- [18]
V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993) DOI
Page edit log
- Victor V. Albert (2026-06-08) — most recent
- Victor V. Albert (2022-07-15)
Cite as:
“Quadratic-residue (QR) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/q-ary_quad_residue, arXiv:2606.11484