Description
An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\).
Let \(\{\alpha_1,\cdots,\alpha_n\}\) be \(n\) distinct points in \(GF(q)\). An RS code encodes a message \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(\alpha_1),\cdots,f_\mu(\alpha_n)\}\) using a message-dependent polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \tag*{(1)}\end{align} In other words, each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), \begin{align} \mu\to\left( f_{\mu}\left(\alpha_{1}\right),f_{\mu}\left(\alpha_{2}\right),\cdots,f_{\mu}\left(\alpha_{n}\right)\right) \,. \tag*{(2)}\end{align}
Protection
Encoding
Decoding
Realizations
Notes
Parents
- Generalized RS (GRS) code — A GRS code for which all multipliers \(v_i\) are unity reduces to an RS code.
- Interleaved RS (IRS) code — An IRS code utilizing one polynomial \(f\) reduces to an RS code.
- Folded RS (FRS) code — An FRS code with no extra grouping (\(m=1\)) reduces to an RS code.
- Multiplicity code — Univariate multiplicity codes of degree \(s=1\) reduce to RS codes.
- Tamo-Barg code — Tamo-Barg codes reduce to RS codes when \(r=k\).
- RS NRT code — RS NRT codes reduce to RS codes when the NRT metric is equivalent to the Hamming metric [43].
Children
- Narrow-sense RS code — A narrow-sense RS is an RS code with length \(n=q-1\) whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element of \(GF(q)\).
- \(q\)-ary parity-check code — RS codes for \(k=n-1\) are parity-check codes [44].
Cousins
- DNA storage code — RS codes have been used for DNA storage [38].
- Maximum distance separable (MDS) code — If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [45].
- Bose–Chaudhuri–Hocquenghem (BCH) code — An RS code can be represented as a union of cosets, with each coset being an interleaver of several binary BCH codes [24].
- Cyclic linear \(q\)-ary code — If the length divides \(q-1\), then it is possible to construct a cyclic RS code. Such codes a Abelian group-algebra codes [46; Example 16.4.9].
- Tensor-product code — Tensor codes constructed from RS codes are robustly testable [47].
- \(q\)-ary linear LTC — RS codes can be used to construct LTCs encoding \(k\) bits with length \(k \text{polylog}(k)\) and query complexity \(\text{polylog}(k)\) [48].
- Private information retrieval (PIR) code — RS codes can be used to construct PIR codes [49].
- Justesen code — An RS code is the outer code of Justesen codes.
- Array code — RS codes over \(q=2^m\) are used in RAID 6 [31,32]; see [33].
- B-code — B-codes can be interpreted as RS codes over polynomials whose symbols lie in Galois rings [50,51].
- Maximum-rank distance (MRD) code — MRD rank-metric codes can be thought of as matrix analogues of MDS RS codes as both constructions utilize a Vandermonde matrix [52].
- Linearized RS code — RS codes are particular cases of linearized RS codes because the sum-rank metric generalizes the Hamming metric [53].
- Berlekamp code — Berlekamp codes are obtained by first constructing an RS-like parity-check matrix out of a certain field extension of \(GF(p)\) and then taking the subfield subcode of the corresponding code; see [54; Ch. 10.6]..
- Hyperbolic evaluation code — Hyperbolic evaluation codes were initially formulated as generalized concatenations (a.k.a. cascades) of RS codes [55,56].
- Bose–Chaudhuri–Hocquenghem (BCH) code — BCH codes are subfield subcodes of RS codes.
- Convolutional code — Convolutional codes are often used in concatenation with RS codes for communication [57].
- Pyramid code — A pyramid code is an LRC whose generator matrix is that of an RS code in standard form, but some of whose columns are split into multiple columns
- Glynn code — The only other inequivalent \([10,5,6]_9\) code is an RS code, which is the unique Euclidean self-dual code for its parameters, and which is not Hermitian self-dual [58–60].
- Hexacode — The dual of the shortened hexacode code is a \([5,2,4]_4\) doubly extended RS code [61; Exam. A].
- Subsystem qubit stabilizer code — Primitive RS codes yield subsystem stabilizer codes via the subsystem extension of the Hermitian construction to subsystem codes [62; Exam. 3].
- Approximate secret-sharing code — The classical information in this code is encoded using an RS code.
- Galois-qudit RS code — Galois-qudit RS codes are CSS codes constructed from RS codes.
- Galois-qudit expander code — Hypergraph products of expander codes with RS inner codes yield \([[n,k\geq n^{1-\epsilon},d\geq n^{1/r}/\text{poly}(\log n)]]_q\) QLDPC Galois-qudit quantum expander codes with transversal \(C^{r-1} Z\) gates [63].
References
- [1]
- Bush, K. A. “Orthogonal Arrays of Index Unity.” The Annals of Mathematical Statistics 23, no. 3 (1952): 426–34.
- [2]
- K. A. Bush, “Orthogonal Arrays of Index Unity”, The Annals of Mathematical Statistics 23, 426 (1952) DOI
- [3]
- I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields”, Journal of the Society for Industrial and Applied Mathematics 8, 300 (1960) DOI
- [4]
- E. Berlekamp, “Bit-serial Reed - Solomon encoders”, IEEE Transactions on Information Theory 28, 869 (1982) DOI
- [5]
- Y. Wang and X. Zhu, “A fast algorithm for the Fourier transform over finite fields and its VLSI implementation”, IEEE Journal on Selected Areas in Communications 6, 572 (1988) DOI
- [6]
- D. G. Cantor, “On arithmetical algorithms over finite fields”, Journal of Combinatorial Theory, Series A 50, 285 (1989) DOI
- [7]
- J. von zur Gathen and J. Gerhard, Modern Computer Algebra (Cambridge University Press, 2013) DOI
- [8]
- V. Guruswami and A. Vardy, “Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard”, (2004) arXiv:cs/0405005
- [9]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [10]
- E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
- [11]
- W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [12]
- D. Gorenstein and N. Zierler, “A Class of Error-Correcting Codes in \(p^m \) Symbols”, Journal of the Society for Industrial and Applied Mathematics 9, 207 (1961) DOI
- [13]
- R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
- [14]
- E. R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 1986.
- [15]
- P. Gemmell and M. Sudan, “Highly resilient correctors for polynomials”, Information Processing Letters 43, 169 (1992) DOI
- [16]
- S. Gao, “A New Algorithm for Decoding Reed-Solomon Codes”, Communications, Information and Network Security 55 (2003) DOI
- [17]
- I. Reed et al., “The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions”, IEEE Transactions on Information Theory 24, 100 (1978) DOI
- [18]
- M. Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13, 180 (1997) DOI
- [19]
- R. M. Roth and G. Ruckenstein, “Efficient decoding of Reed-Solomon codes beyond half the minimum distance”, IEEE Transactions on Information Theory 46, 246 (2000) DOI
- [20]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) 28 DOI
- [21]
- V. Guruswami and A. Rudra, “Limits to List Decoding Reed–Solomon Codes”, IEEE Transactions on Information Theory 52, 3642 (2006) DOI
- [22]
- J. Brakensiek, S. Gopi, and V. Makam, “Generic Reed-Solomon Codes Achieve List-decoding Capacity”, (2024) arXiv:2206.05256
- [23]
- R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
- [24]
- A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [25]
- V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (2013) DOI
- [26]
- M. Naor and B. Pinkas, “Oblivious transfer and polynomial evaluation”, Proceedings of the thirty-first annual ACM symposium on Theory of Computing (1999) DOI
- [27]
- D. V. Sarwate and N. R. Shanbhag, “High-speed architectures for Reed-Solomon decoders”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 9, 641 (2001) DOI
- [28]
- S. B. Wicker and V. K. Bhargava, “Reed-Solomon Codes and Their Applications”, (1999) DOI
- [29]
- D. Zhang, K. Ho-Van, and T. Le-Ngoc, “Impulse noise detection techniques for retransmission to reduce delay in DSL systems”, 2012 IEEE International Conference on Communications (ICC) 3160 (2012) DOI
- [30]
- A. Kiayias and M. Yung, “Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes”, Lecture Notes in Computer Science 232 (2002) DOI
- [31]
- Anvin, H. Peter. "The mathematics of RAID-6." (2007).
- [32]
- S. T. Position. (2009) Common raid disk data format specification. [Online]. Available: https://www.snia.org/tech activities/standards/curr standards/ddf
- [33]
- M. Blaum, P. G. Farrell, H. C. A. van Tilborg, 1998. Array codes. Handbook of coding theory, 2 (Part 2), pp. 1855-1909.
- [34]
- S. Li et al., “PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously”, (2020) arXiv:1809.10361
- [35]
- International Organization for Standardization, Information Technology: Automatic Identification and Data Capture Techniques-QR Code 2005 Bar Code Symbology Specification, 2nd ed., IEC18004 (ISO, 2006).
- [36]
- I. Shakeel et al., “Reed-Solomon coding for cooperative wireless communication”, 21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications 1021 (2010) DOI
- [37]
- N. Shental et al., “Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers”, Science Advances 6, (2020) DOI
- [38]
- R. N. Grass et al., “Robust Chemical Preservation of Digital Information on DNA in Silica with Error‐Correcting Codes”, Angewandte Chemie International Edition 54, 2552 (2015) DOI
- [39]
- Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
- [40]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Reed–Solomon Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://mint.sbg.ac.at/desc_CReedSolomon.html
- [41]
- S. P. Jordan et al., “Optimization by Decoded Quantum Interferometry”, (2024) arXiv:2408.08292
- [42]
- A. Chailloux and J.-P. Tillich, “Quantum advantage from soft decoders”, (2024) arXiv:2411.12553
- [43]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Reed-Solomon Codes for OOAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2024-09-05. https://mint.sbg.ac.at/desc_OReedSolomon.html
- [44]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Extended Reed–Solomon Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://mint.sbg.ac.at/desc_CReedSolomon-extended.html
- [45]
- S. Ball, “On sets of vectors of a finite vector space in which every subset of basis size is a basis”, Journal of the European Mathematical Society 14, 733 (2012) DOI
- [46]
- W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [47]
- A. Polishchuk and D. A. Spielman, “Nearly-linear size holographic proofs”, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC ’94 194 (1994) DOI
- [48]
- E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) DOI
- [49]
- B. Sasidharan and E. Viterbo, “Private Data Access in Blockchain Systems Employing Coded Sharding”, 2021 IEEE International Symposium on Information Theory (ISIT) 2684 (2021) DOI
- [50]
- M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction”, IEEE Transactions on Information Theory 39, 66 (1993) DOI
- [51]
- J. L. Fan, “Array Codes as LDPC Codes”, Constrained Coding and Soft Iterative Decoding 195 (2001) DOI
- [52]
- R. Koetter and F. R. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, IEEE Transactions on Information Theory 54, 3579 (2008) DOI
- [53]
- U. Martínez-Peñas, “Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring”, (2018) arXiv:1710.03109
- [54]
- R. Roth, Introduction to Coding Theory (Cambridge University Press, 2006) DOI
- [55]
- K. Saints and C. Heegard, “On hyperbolic cascaded Reed-Solomon codes”, Lecture Notes in Computer Science 291 (1993) DOI
- [56]
- Gui-Liang Feng and T. R. N. Rao, “Improved geometric Goppa codes. I. Basic theory”, IEEE Transactions on Information Theory 41, 1678 (1995) DOI
- [57]
- T. Halonen, J. Romero, and J. Melero, editors , “GSM, GPRS and EDGE Performance”, (2003) DOI
- [58]
- T. Baicheva, I. Bouyukliev, S. Dodunekov, and W. Willems, “On the [10; 5; 6] Reed-Solomon and Glynn codes,” Mathematica Balkanica, New Series, vol. 18, pp. 67–78, 200
- [59]
- T. A. Gulliver, J.-L. Kim, and Y. Lee, “New MDS or Near-MDS Self-Dual Codes”, IEEE Transactions on Information Theory 54, 4354 (2008) DOI
- [60]
- M. Grassl and T. A. Gulliver, “On circulant self-dual codes over small fields”, Designs, Codes and Cryptography 52, 57 (2009) DOI
- [61]
- G. D. Forney, M. Grassl, and S. Guha, “Convolutional and Tail-Biting Quantum Error-Correcting Codes”, IEEE Transactions on Information Theory 53, 865 (2007) arXiv:quant-ph/0511016 DOI
- [62]
- S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153
- [63]
- L. Golowich and T.-C. Lin, “Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes”, (2024) arXiv:2410.14662
Page edit log
- Victor V. Albert (2022-08-12) — most recent
- Victor V. Albert (2022-04-28)
- Mustafa Doger (2022-04-03)
- Victor V. Albert (2021-10-29)
Cite as:
“Reed-Solomon (RS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/reed_solomon