Reed-Solomon (RS) code[13] 

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

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

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: reed_solomon

Cite as:
“Reed-Solomon (RS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/reed_solomon
BibTeX:
@incollection{eczoo_reed_solomon, title={Reed-Solomon (RS) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/reed_solomon} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/reed_solomon

Cite as:

“Reed-Solomon (RS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/reed_solomon

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/ag/reed_solomon/rs/reed_solomon.yml.