Description
Member of a quadruple of cyclic binary codes of prime length \(n=8m\pm 1\) for \(m\geq 1\) constructed using quadratic residues and nonresidues of \(n\) [1; Def. 3.2.8].
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 binary quadratic-residue codes have automorphism groups containing \(PSL_2(p)\) by the Gleason-Prange theorem [1; Thm. 3.2.11]; the extensions of the \([7,4,3]\) Hamming and \([23,12,7]\) Golay codes are exceptional examples with larger automorphism groups [1; Rem. 3.2.12].
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\) [2; Thm. 2.7.4].Decoding
Algebraic decoder [3].Notes
Introduction of quadratic-residue codes in Refs. [4,5][2; Sec. 2.7].Cousins
- Divisible code— Extended binary quadratic residue codes of length \(8m\) are self-dual doubly even codes [6; pg. 82].
- Self-dual linear code— The length-\(72\) extended binary quadratic-residue code is self-dual but not extremal [7; Rem. 4.3.10].
- Lexicographic code— The \([18,9,6]\) binary QR code is a lexicode [8].
- Quasi-cyclic code— Binary QR codes are equivalent to double circulant codes for all \(n<200\) except 89 and 167 [9].
- \([24, 12, 8]\) Extended Golay code— The extended Golay code is an extended binary quadratic-residue code [4; Ch. 16].
- \([48,24,12]\) self-dual code— The \([48,24,12]\) self-dual code is an extended quadratic-residue code [4; Ch. 16].
- \([2^m,m,2^{m-1}]\) Hadamard code— For Hadamard matrices obtained from the Paley construction, the linear span of the resulting Hadamard codes yields quadratic-residue codes [4; pg. 49].
- \([2^r-1,2^r-r-1,3]\) Hamming code— The \([7,4,3]\) Hamming code is a binary quadratic-residue code [1; Ex. 3.2.10].
- \([8,4,4]\) extended Hamming code— The \([8,4,4]\) extended Hamming code is an extended quadratic-residue code [4].
- \((u|u+v)\)-construction code— The \((u|u+v)\) construction can be used to obtain nonlinear binary quadratic-residue codes [10].
- Quantum synchronizable code— Binary QR codes can be used to construct quantum synchronizable codes via the CSS construction [11].
Primary Hierarchy
References
- [1]
- P. R. J. Östergård, “Construction and Classification of Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S. H. Chen (2007). “Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm”. Journal of information science and engineering, 23(1), 127-145.
- [4]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [5]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [6]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [7]
- S. Bouyuklieva, “Self-dual codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [9]
- G. J. M. Beenker, “On double circulant codes.” (1980).
- [10]
- N. Sloane and D. Whitehead, “New family of single-error correcting codes”, IEEE Transactions on Information Theory 16, 717 (1970) DOI
- [11]
- Y. Xie, J. Yuan, and Y. Fujiwara, “Quantum Synchronizable Codes From Quadratic Residue Codes and Their Supercodes”, (2014) arXiv:1403.6192
- [12]
- V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993) DOI
Page edit log
- Victor V. Albert (2022-07-15) — most recent
- Yijia Xu (2022-04-25)
Cite as:
“Binary quadratic-residue (QR) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_quad_residue