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}
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)\) is a narrow-sense RS code. In an alternative convention (not used here), the primitive case is called an RS code, and the general-root case is a generalized RS code.
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 Reed-Solomon 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].The ubiquity of RS codes has yielded off-the-shelf VLSI intergrated-circuit decoding hardware [26] (see also Ref. [27], Ch. 5 and 10).
Realizations
RS Product Code (RSPC) was used in DVDs (see Ref. [27], Ch. 4).DSL technologies and their variants against impluse noise [28].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 [29].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. [27], Ch. 3).Automatic repeat request (ARQ) data transmission protocols (see Ref. [27], Ch. 7).Slow-frequency-hop spread-spectrum transmission (see Ref. [27], Chs. 8-9).Coded sharding designs in blockchains to increase efficiency [30].Private Information Retrieval [31].Used in QR-Codes to retrieve damaged barcodes [32].Wireless communication systems such as 3G, DVB, and WiMAX [33].Correcting pooled testing results for SARS-CoV-2 [34].DNA storage [35].
Notes
See Kaiserslautern database [36] for explicit codes.See corresponding MinT database entry [37].Popular summary in Quanta Magazine.
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\).
- DNA storage code — RS codes have been used for DNA storage [35].
Child
- \(q\)-ary parity-check code — RS codes for \(k=n-1\) are parity-check codes [38].
Cousins
- Maximum distance separable (MDS) code — RS codes have distance \(n-k+1\), saturating the Singleton bound. If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [39].
- Bose–Chaudhuri–Hocquenghem (BCH) code — Narrow-sense RS codes are BCH codes [40; Remark 15.3.21][41; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [42; pg. 81]. Moreover, 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 [43; Example 16.4.9].
- Tensor-product code — Tensor codes constructed from RS codes are robustly testable [44].
- \(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)\) [45].
- Justesen code — An RS code is the outer code of Justesen codes.
- Rank-modulation Gray code (RMGC) — RS codes can be used to design rank modulation codes [46].
- B-code — B-codes can be interpreted as RS codes over polynomials whose symbols lie in Galois rings [47,48].
- Maximum-rank distance (MRD) code — MRD rank-metric codes can be thought of as matrix analogues of MDS Reed-Solomon codes as both constructions utilize a Vandermonde matrix [49].
- Convolutional code — Convolutional codes are often used in concatenation with Reed-Solomon codes for communication [50].
- Glynn code — The only other inequivalent \([10,5,6]_9\) code is a Reed-Solomon code, which is the unique Euclidean self-dual code for its parmaters, and which is not Hermitian self-dual [51–53].
- Hexacode — The dual of the shortened hexacode code is a \([5,2,4]_4\) doubly extended RS code [54; Exam. A].
- Bose–Chaudhuri–Hocquenghem (BCH) code — BCH codes are subfield subcodes of RS codes.
- Subsystem qubit stabilizer code — Primitive RS codes yield subsystem stabilizer codes via the subsystem extension of the Hermitian construction to subsystem codes [55; Exam. 3].
- Approximate secret-sharing code — The classical information in this code is encoded using a Reed-Solomon code.
- Galois-qudit RS code — Galois-qudit RS codes are CSS codes constructed from Reed-Solomon codes.
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) 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”, (2023) 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]
- 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
- [27]
- S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE, 1999) DOI
- [28]
- 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) (2012) DOI
- [29]
- A. Kiayias and M. Yung, “Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes”, Automata, Languages and Programming 232 (2002) DOI
- [30]
- S. Li et al., “PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously”, (2020) arXiv:1809.10361
- [31]
- B. Sasidharan and E. Viterbo, “Private Data Access in Blockchain Systems Employing Coded Sharding”, 2021 IEEE International Symposium on Information Theory (ISIT) (2021) DOI
- [32]
- International Organization for Standardization, Information Technology: Automatic Identification and Data Capture Techniques-QR Code 2005 Bar Code Symbology Specification, 2nd ed., IEC18004 (ISO, 2006).
- [33]
- I. Shakeel et al., “Reed-Solomon coding for cooperative wireless communication”, 21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (2010) DOI
- [34]
- N. Shental et al., “Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers”, Science Advances 6, (2020) DOI
- [35]
- 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
- [36]
- 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.
- [37]
- 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. http://mint.sbg.ac.at/desc_CReedSolomon.html
- [38]
- 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. http://mint.sbg.ac.at/desc_CReedSolomon-extended.html
- [39]
- 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 733 (2012) DOI
- [40]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [41]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [42]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [43]
- W. Willems, "Codes in Group Algebras." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [44]
- 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 (1994) DOI
- [45]
- E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) DOI
- [46]
- A. Mazumdar, A. Barg, and G. Zémor, “Constructions of Rank Modulation Codes”, (2011) arXiv:1110.2557
- [47]
- M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction”, IEEE Transactions on Information Theory 39, 66 (1993) DOI
- [48]
- J. L. Fan, “Array Codes as LDPC Codes”, Constrained Coding and Soft Iterative Decoding 195 (2001) DOI
- [49]
- R. Koetter and F. R. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, IEEE Transactions on Information Theory 54, 3579 (2008) DOI
- [50]
- T. Halonen, J. Romero, and J. Melero, editors , “GSM, GPRS and EDGE Performance”, (2003) DOI
- [51]
- 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
- [52]
- 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
- [53]
- M. Grassl and T. A. Gulliver, “On circulant self-dual codes over small fields”, Designs, Codes and Cryptography 52, 57 (2009) DOI
- [54]
- 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
- [55]
- S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Subsystem Codes”, (2006) arXiv:quant-ph/0610153
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