[Jump to code hierarchy]

Interleaved RS (IRS) code

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].

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

Your contribution is welcome!

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

edit on this site

Zoo Code ID: interleaved_reed_solomon

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

Cite as:

“Interleaved RS (IRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/interleaved_reed_solomon

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