Description
Member of a quadruple of cyclic \(q\)-ary codes of prime length \(n\) where \(q\) is prime and a quadratic-residue modulo \(n\). The codes are constructed using quadratic residues and nonresidues of \(n\). Extensions to prime-power \(q\) are also known [1,2].
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 automorphism group of extended odd-like quadratic-residue codes is \(PSL(2,\mathbb{F}_q)\), and these codes are the only codes with such symmetries [3].
Rate
Achieve capacity of the binary erasure channel; see Ref. [4].Cousins
- Combinatorial design— The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [7–9], including \(3\)-designs [10].
- Karlin double circulant code— Karlin double circulant codes can be mapped to extended cyclic and extended quadratic-residue codes over \(\mathbb{F}_4\) [11,12][5; Ch. 16][13; Sec. 2.4.2] by identifying \((0,\omega,\bar{\omega},1)\) with \((00),(10),(01),(11)\) [11].
- Reed-Solomon (RS) code— The \([4,2,3]_4\) RS code is the smallest example of a quaternary quadratic-residue code and can be mapped to the \([8,4,4]\) extended Hamming code [13; Sec. 2.4.2] by identifying \((0,\omega,\bar{\omega},1)\) with \((00),(10),(01),(11)\) [11].
- Quantum quadratic-residue (QR) code
Primary Hierarchy
References
- [1]
- J. van Lint and F. MacWilliams, “Generalized quadratic residue codes”, IEEE Transactions on Information Theory 24, 730 (1978) DOI
- [2]
- J. H. Lint, “Generalized quadratic-residue codes”, Algebraic Coding Theory and Applications 285 (1979) DOI
- [3]
- C. Ding, H. Liu, and V. D. Tonchev, “All binary linear codes that are invariant under \(\PSL_2(n)\)”, (2017) arXiv:1704.01199
- [4]
- K. Ivanov and R. L. Urbanke, “Capacity-achieving codes: a review on double transitivity”, (2020) arXiv:2010.15453
- [5]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [6]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [7]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [8]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [9]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
- [10]
- M. Awada, “Infinite series of \(3\)-designs in the extended quadratic residue code”, (2024) arXiv:2310.14281
- [11]
- P. Gaborit, V. Pless, P. Solé, and O. Atkin, “Type II Codes over F4”, Finite Fields and Their Applications 8, 171 (2002) DOI
- [12]
- Karlin M, MacWilliams FJ. Quadratic residue codes over GF(4) and their binary images. InIEEE Int. Symp. on Information Theory, Asilomar, CA 1972.
- [13]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [14]
- V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993) DOI
Page edit log
- Victor V. Albert (2022-07-15) — most recent
Cite as:
“Quadratic-residue (QR) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_quad_residue