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\).
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.
Their automorphism group is either \(PSL(2,GF(p))\) or a closely related group by the Gleason-Prange theorem [1,2].
Decoding
Algebraic decoder [3].Cousins
- Divisible code— Extended binary quadratic residue codes of length \(8m\) are self-dual doubly even codes [5; pg. 82].
- Lexicographic code— The \([18,9,6]\) binary QR code is a lexicode [6].
- Quasi-cyclic code— Binary QR codes are equivalent to double circulant codes for all \(n<200\) except 89 and 167 [7].
- \((u|u+v)\)-construction code— The \((u|u+v)\) construction can be used to obtain nonlinear binary quadratic-residue codes [8].
- Quantum synchronizable code— Binary QR codes can be used to construct quantum synchronizable codes via the CSS construction [9].
Primary Hierarchy
References
- [1]
- R. E. Blahut, “The Gleason-Prange theorem”, IEEE Transactions on Information Theory 37, 1269 (1991) DOI
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- Chen, Y. H., Truong, T. K., Chang, Y., Lee, C. D., & Chen, S. H. (2007). Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm. Journal of information science and engineering, 23(1), 127-145.
- [4]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [5]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [6]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [7]
- Beenker, G. J. M. "On double circulant codes." (1980).
- [8]
- N. Sloane and D. Whitehead, “New family of single-error correcting codes”, IEEE Transactions on Information Theory 16, 717 (1970) DOI
- [9]
- Y. Xie, J. Yuan, and Y. Fujiwara, “Quantum Synchronizable Codes From Quadratic Residue Codes and Their Supercodes”, (2014) arXiv:1403.6192
- [10]
- 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