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
Since each polynomial \(f_{\mu}\) is of degree less than \(k\), it has less than \(k\) roots; this is called the degree mantra. Therefore, the polynomial can be determined from its values at \(k\) points. This means that RS codes can correct erasures on up to \(n-k\) registers. The resulting distance, \(d=n-k+1\), saturates the Singleton bound.
Encoding
Bit-serial encoder [4].\([n,k,n-k+1]\) RS code requires an order \(O(n^2)\) operations while encoding if a straightforward matrix multiplication is employed and \(k=O(n)\). Using the FFT algorithm, complexity of evaluating a polynomial at \(n\) roots of unity becomes \(O(n\log n)\). The FFT can be generalized to finite fields and rings, which is referred as Number-theoretic Transform (NTT). However, for some values of \(n\), which can not be factorized into small primes or do not have \(n\) roots of unity, the FFT algorithm fails. Independently developed by [5,6] and generalized in Ref. [7], the additive FFT solves this problem by evaluating the polynomial at \(n-1\) roots of unity when \(n\) is power of 2.
Decoding
Decoding general RS codes is \(NP\)-hard [8].Although using iFFT has its counterpart iNNT for finite fields, the decoding is usually standard polynomial interpolation in \(k=O(n\log^2 n)\). However, in erasure decoding, encoded values are only erased in \(r\) points, which is a specific case of polynomial interpolation and can be done in \(O(n\log n)\) by computing product of the received polynomial and an erasure locator polynomial and using long division to find an original polynomial. The long division step can be omitted to increase speed further by only dividing the derivative of the product polynomial, and derivative of erasure locator polynomial evaluated at erasure locations.Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [9,10].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [11,12] (see exposition in Ref. [13]).Berlekamp-Welch decoder with runtime of order \(O(n^3)\) [14] (see exposition in Ref. [15]), assuming that \(t \geq (n+k)/2\).Gao decoder using extended Euclidean algorithm [16].Fast-Fourier-transform decoder with runtime of order \(O(n \text{polylog}n)\) [17].List decoders try to find a low-degree bivariate polynomial \(Q(x,y)\) such that evaluation of \(Q\) at \((\alpha_i,y_i)\) is zero. By choosing proper degrees, it can be shown such polynomial exists by drawing an analogy between evaluation of \(Q(\alpha_i,y_i)\) and solving a homogenous linear equation (interpolation). Once this is done, one lists roots of \(y\) that agree at \(\geq t\) points. The breakthrough Sudan list-decoding algorithm corrects up to \(1-\sqrt{2R}\) fraction of errors asymptotically in \(n\) [18]. Roth and Ruckenstein proposed a modified key equation that allows for correction of more than \(\left\lfloor (n-k)/2 \right\rfloor\) errors [19]. The Guruswami-Sudan algorithm improved the Sudan algorithm to \(1-\sqrt{R}\) [20], meaning that RS codes achieve list-decoding capacity; see Ref. [21] for bounds. It was later shown that generic RS codes achieve list-decoding capacity [22]. A modification of the Guruswami-Sudan algorithm by Koetter and Vardy is used for soft-decision decoding [23] (see also Ref. [24]). Subcodes of RS codes whose evaluation points lie in a subfield can be decoded up to the \(1-R\) [25]. List decoding of RS codes is known as noisy polynomial interpolation in cryptography [26].The ubiquity of RS codes has yielded off-the-shelf VLSI intergrated-circuit decoding hardware [27] (see also Ref. [28], Ch. 5 and 10).
Realizations
RS Product Code (RSPC) was used in DVDs (see Ref. [28], Ch. 4).DSL technologies and their variants against impluse noise [29].Cryptographic primitives based on the hardness of decoding RS codes for more than \(1-\sqrt{k/n}+\epsilon\) errors. This is equivalent to the polynomial reconstruction problem [30].RS codes as outer codes concatenated with convolutional codes are used indirectly in space exploration programs such as Voyager and Galileo. RS codes were part of a telemetry channel coding standard issued by the Consultative Committee for Space Data Systems (see Ref. [28], Ch. 3).Automatic repeat request (ARQ) data transmission protocols (see Ref. [28], Ch. 7).Slow-frequency-hop spread-spectrum transmission (see Ref. [28], Chs. 8-9).RS codes over \(q=2^m\) are used in RAID 6 [31,32]; see [33].Coded sharding designs in blockchains to increase efficiency [34].Used in QR-Codes to retrieve damaged barcodes [35].Wireless communication systems such as 3G, DVB, and WiMAX [36].Correcting pooled testing results for SARS-CoV-2 [37].DNA storage [38].
Notes
See Kaiserslautern database [39] for explicit codes.See corresponding MinT database entry [40].Popular summary in Quanta Magazine.Certain structured classical optimization problems can be mapped into decoding and list decoding RS codes via the Decoded Quantum Interferomentry (DQI) algorithm [41,42].
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, R. Scholtz, Treiu-Kien Truong, and L. Welch, “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 245 (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, M. Yu, C.-S. Yang, A. S. Avestimehr, S. Kannan, and P. Viswanath, “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, M. O. Hasna, A. Abu-Dayya, and A. Ghrayeb, “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, R. Heckel, M. Puddu, D. Paunescu, and W. J. Stark, “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, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, and R. Babbush, “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