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{split} 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{split}\right)~. \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].

Realizations

The cross-interleaved RS (CIRC), an IRS code using two shortened RS codes and two forms of interleaving, was used for compact discs (CDs) [3] (see Ref. [4], Sec. 5.6 and Ref. [5], Ch. 4).

Parent

Children

  • 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 ACM symposium on Theory of computing - STOC '03 (2003). DOI
[3]
Odaka K., Sako Y., Iwamoto I., Doi T.; Vries L.B.; SONY: Error correctable data transmission method (Patent US4413340) filing date May 21, 1980.
[4]
W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes (Cambridge University Press, 2003). DOI
[5]
S. B. Wicker and V. K. Bhargava, Reed-solomon Codes and Their Applications (IEEE, 1999). DOI

Zoo code information

Internal code ID: interleaved_reed_solomon

Your contribution is welcome!

on github.com (edit & pull request)

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