Description
A modification of RS codes where multiple polynomials are used to define each codeword. Each codeword \(\mu\) of a \(t\)-interleaved RS code is a string of values of the corresponding set \(\{f_\mu^{(1)},f_\mu^{(2)},\cdots,f_\mu^{(t)}\}\) of \(t\) polynomials at the points \(\alpha_i\). The vector codewords can be arranged in an array whose rows are ordinary RS codes for each polynomial \(f^{j}\), yielding the encoding \begin{align} \mu\to\left( \begin{array}{cccc} f_{\mu}^{(1)}\left(\alpha_{1}\right) & f_{\mu}^{(1)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(1)}\left(\alpha_{n}\right)\\ f_{\mu}^{(2)}\left(\alpha_{1}\right) & f_{\mu}^{(2)}\left(\alpha_{2}\right) & & f_{\mu}^{(2)}\left(\alpha_{n}\right)\\ \vdots & & \ddots & \vdots\\ f_{\mu}^{(t)}\left(\alpha_{1}\right) & f_{\mu}^{(t)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(t)}\left(\alpha_{n}\right) \end{array}\right)~. \tag*{(1)}\end{align}Decoding
Decoder that corrects up to \(1-\frac{2k+n}{3n}\) fraction of random errors [1].Decoder that corrects up to \(1-(\frac{k}{n})^{2/3}\) fraction of random errors [2].Member of code lists
Primary Hierarchy
Parents
IRS codes are linear over \(GF(q)\) but not necessarily over \(GF(q^t)\).
Interleaved RS (IRS) code
Children
PV codes are IRS codes with specific algebraic relations between the codeword polynomials that allow for efficient list decoding.
An IRS code utilizing one polynomial \(f\) reduces to an RS code.
References
- [1]
- D. Bleichenbacher, A. Kiayias, and M. Yung, “Decoding interleaved Reed–Solomon codes over noisy channels”, Theoretical Computer Science 379, 348 (2007) DOI
- [2]
- D. Coppersmith and M. Sudan, “Reconstructing curves in three (and higher) dimensional space from noisy data”, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing 136 (2003) DOI
Page edit log
- Victor V. Albert (2022-07-14) — most recent
Cite as:
“Interleaved RS (IRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/interleaved_reed_solomon