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].
Parent
- Linear \(q\)-ary code — IRS codes are linear over \(GF(q)\) but not necessarily over \(GF(q^t)\).
Children
- Cross-interleaved RS (CIRS) code
- Parvaresh-Vardy (PV) code — PV codes are IRS codes with specific algebraic relations between the codeword polynomials that allow for efficient list decoding.
- Reed-Solomon (RS) code — 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