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 nonzero elements of \(GF(q)\) with \(q>n\). An RS code encodes \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(\alpha_1),\cdots,f_\mu(\alpha_n)\}\), with polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \end{align} In other words, each codeword \(\mu\) is a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\).

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.

Decoding

Berlekamp-Massey decoder [3][4].Gorenstein-Peterson-Zierler decoder [5].Berlekamp-Welch decoder [6], assuming that \(t \geq (n+k)/2\).Gao decoder using extended Euclidean algorithm [7].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 evaulation of \(Q(\alpha_i,y_i)\) and homogenous linear equation(interpolation). Once this is done, list roots of \(y\) that agree at \(\geq t\) points. The Sudan list decoding algorithm corrects up to \(1-\sqrt{2R}\) proportion of errors [8]. The Sudan–Guruswami algorithm improves that to \(1-\sqrt{R}\) [9].

Realizations

Cross-interleaved RS code (CIRC) is adopted in Compact Discs (CDs) and RS Product Code (RSPC) in DVDs; see Ch. 4 of Ref. [10].In DSL technologies and its variants against impluse noise [11].RS codes as outer codes concatenated with convolutional codes are used indirectly in solar exploration programs; see Ch. 3 of Ref. [10].Coded sharding designs in blockchains to increase efficiency [12].Private Information Retrieval [13].Used in QR-Codes to retrieve damaged barcodes [14].Wireless communication systems such as 3G, DVB, and WiMAX [15].Correcting pooled testing results for SARS-CoV-2 [16].

Notes

\([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=\mathcal{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 [17][18] and generalized in Ref. [19], the additive FFT solves this problem by evaluating the polynomial at \(n-1\) roots of unity when \(n\) is power of 2.Although using iFFT has its counterpart iNNT for finite fields, the decoding is usually standard polynomial interpolation in \(k=\mathcal{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 \(\mathcal{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.

Parents

Children

Cousins

Zoo code information

Internal code ID: reed_solomon

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} }
Permanent link:
https://errorcorrectionzoo.org/c/reed_solomon

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. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969). DOI
[4]
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
[5]
R.E. Blahut, Theory and practice of error-control codes, Addison-Wesley 1983.
[6]
E. R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 1986.
[7]
S. Gao, “A New Algorithm for Decoding Reed-Solomon Codes”, Communications, Information and Network Security 55 (2003). DOI
[8]
M. Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound”, Journal of Complexity 13, 180 (1997). DOI
[9]
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
[10]
S. B. Wicker and V. K. Bhargava, Reed-solomon Codes and Their Applications (IEEE, 1999). DOI
[11]
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
[12]
Songze Li et al., “PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously”. 1809.10361
[13]
B. Sasidharan and E. Viterbo, “Private Data Access in Blockchain Systems Employing Coded Sharding”, 2021 IEEE International Symposium on Information Theory (ISIT) (2021). DOI
[14]
International Organization for Standardization, Information Technology: Automatic Identification and Data Capture Techniques-QR Code 2005 Bar Code Symbology Specification, 2nd ed., IEC18004 (ISO, 2006).
[15]
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
[16]
N. Shental et al., “Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers”, Science Advances 6, (2020). DOI
[17]
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
[18]
D. G. Cantor, “On arithmetical algorithms over finite fields”, Journal of Combinatorial Theory, Series A 50, 285 (1989). DOI
[19]
J. von zur Gathen and J. Gerhard, Modern Computer Algebra (Cambridge University Press, 2009). DOI
[20]
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
[21]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[22]
T. Halonen, J. Romero, and J. Melero, editors , GSM, GPRS and EDGE Performance (Wiley, 2003). DOI
[23]
R. Koetter and F. R. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, IEEE Transactions on Information Theory 54, 3579 (2008). DOI
[24]
A. Mazumdar, A. Barg, and G. Zemor, “Constructions of rank modulation codes”, 2011 IEEE International Symposium on Information Theory Proceedings (2011). DOI

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/reed_solomon.yml.