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 \(i-1\)st powers of a primitive \(n\)th root of unity is a narrow-sense RS code. In an alternative convention (not used here), the primitive-root case is called an RS code, and the general-root case is a generalized RS code.
Protection
Rate
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.
Child
- \(q\)-ary parity-check code — RS codes for \(k=n-1\) are parity-check codes [34].
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 [35].
- Bose–Chaudhuri–Hocquenghem (BCH) code — Narrow-sense RS codes are BCH codes [36; Remark 15.3.21][37; Thms. 5.2.1 and 5.2.3]. Their minimal distance is equal to their designed distance [38; 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 [22].
- Cyclic linear \(q\)-ary code — If the length divides \(q-1\), then it is possible to construct a cyclic RS code.
- Tensor-product code — Tensor codes constructed from RS codes are robustly testable [39].
- \(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)\) [40].
- 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 [41].
- B-code — B-codes can be interpreted as RS codes over polynomials whose symbols lie in Galois rings [42,43].
- 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 [44].
- Convolutional code — Convolutional codes are often used in concatenation with Reed-Solomon codes for communication [45].
- Galois-qudit RS code — Galois-qudit RS codes codes are CSS codes constructed from Reed-Solomon codes.
- Approximate secret-sharing code — The classical information in this code is encoded using a Reed-Solomon code.
References
- [1]
- K. A. Bush, “Orthogonal Arrays of Index Unity”, The Annals of Mathematical Statistics 23, 426 (1952) DOI
- [2]
- 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
- [3]
- J. Brakensiek, S. Gopi, and V. Makam, “Generic Reed-Solomon codes achieve list-decoding capacity”, (2023) arXiv:2206.05256
- [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]
- J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969) DOI
- [9]
- E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
- [10]
- W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes”, IEEE Transactions on Information Theory 6, 459 (1960) DOI
- [11]
- 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
- [12]
- R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
- [13]
- E. R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 1986.
- [14]
- P. Gemmell and M. Sudan, “Highly resilient correctors for polynomials”, Information Processing Letters 43, 169 (1992) DOI
- [15]
- S. Gao, “A New Algorithm for Decoding Reed-Solomon Codes”, Communications, Information and Network Security 55 (2003) DOI
- [16]
- 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
- [17]
- M. Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13, 180 (1997) DOI
- [18]
- 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
- [19]
- 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
- [20]
- V. Guruswami and A. Rudra, “Limits to List Decoding Reed–Solomon Codes”, IEEE Transactions on Information Theory 52, 3642 (2006) DOI
- [21]
- R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003) DOI
- [22]
- A. Vardy and Y. Be’ery, “Bit-level soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Communications 39, 440 (1991) DOI
- [23]
- S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE, 1999) DOI
- [24]
- 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
- [25]
- A. Kiayias and M. Yung, “Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes”, Automata, Languages and Programming 232 (2002) 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. Li et al., “PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously”, (2020) arXiv:1809.10361
- [28]
- B. Sasidharan and E. Viterbo, “Private Data Access in Blockchain Systems Employing Coded Sharding”, 2021 IEEE International Symposium on Information Theory (ISIT) (2021) DOI
- [29]
- International Organization for Standardization, Information Technology: Automatic Identification and Data Capture Techniques-QR Code 2005 Bar Code Symbology Specification, 2nd ed., IEC18004 (ISO, 2006).
- [30]
- 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
- [31]
- N. Shental et al., “Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers”, Science Advances 6, (2020) DOI
- [32]
- 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.
- [33]
- 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
- [34]
- 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
- [35]
- 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
- [36]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [37]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [38]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [39]
- 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
- [40]
- E. Ben-Sasson and M. Sudan, “Short PCPs with Polylog Query Complexity”, SIAM Journal on Computing 38, 551 (2008) DOI
- [41]
- A. Mazumdar, A. Barg, and G. Zemor, “Constructions of rank modulation codes”, 2011 IEEE International Symposium on Information Theory Proceedings (2011) DOI
- [42]
- M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction”, IEEE Transactions on Information Theory 39, 66 (1993) DOI
- [43]
- J. L. Fan, “Array Codes as LDPC Codes”, Constrained Coding and Soft Iterative Decoding 195 (2001) DOI
- [44]
- R. Koetter and F. R. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, IEEE Transactions on Information Theory 54, 3579 (2008) DOI
- [45]
- T. Halonen, J. Romero, and J. Melero, editors , GSM, GPRS and EDGE Performance (Wiley, 2003) DOI
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