Reed-Solomon (RS) code[1,2] 

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

Since each polynomial \(f_{\mu}\) is of degree less than \(k\), it 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.

Rate

Generic Reed-Solomon codes achieve list-decoding capacity [3].

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

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)\) [8,9].Gorenstein-Peterson-Zierler decoder with runtime of order \(O(n^3)\) [10,11] (see exposition in Ref. [12]).Berlekamp-Welch decoder with runtime of order \(O(n^3)\) [13] (see exposition in Ref. [14]), assuming that \(t \geq (n+k)/2\).Gao decoder using extended Euclidean algorithm [15].Fast-Fourier-transform decoder with runtime of order \(O(n \text{polylog}n)\) [16].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 [17]. Roth and Ruckenstein proposed a modified key equation that allows for correction of more than \(\left\lfloor (n-k)/2 \right\rfloor\) errors [18]. The Guruswami-Sudan algorithm improved the Sudan algorithm to \(1-\sqrt{R}\) [19]; see Ref. [20] for bounds. A further modification by Koetter and Vardy is used for soft-decision decoding [21] (see also Ref. [22]).

Realizations

RS Product Code (RSPC) was used in DVDs (see Ref. [23], Ch. 4).DSL technologies and their variants against impluse noise [24].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 [25].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 temetry channel coding standard issued by the Consultative Committee for Space Data Systems (see Ref. [23], Ch. 3).The ubiquity of RS codes has yielded off-the-shelf VLSI intergrated-circuit decoding hardware [26] (see also Ref. [23], Ch. 5 and 10).Automatic repeat request (ARQ) data transmission protocols (see Ref. [23], Ch. 7).Slow-frequency-hop spread-spectrum transmission (see Ref. [23], Chs. 8-9).Coded sharding designs in blockchains to increase efficiency [27].Private Information Retrieval [28].Used in QR-Codes to retrieve damaged barcodes [29].Wireless communication systems such as 3G, DVB, and WiMAX [30].Correcting pooled testing results for SARS-CoV-2 [31].

Notes

See Kaiserslautern database [32] for explicit codes.See corresponding MinT database entry [33].Popular summary in Quanta Magazine.

Parents

Child

Cousins

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

Your contribution is welcome!

on github.com (edit & pull request)

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/tree/main/codes/classical/q-ary_digits/ag/rs/reed_solomon.yml.