Folded RS (FRS) code[1] 

Description

A linear \([n/m,k]_{q^m}\) code that is a modification of an \([n,k]_q\) RS code such that evaluations are grouped to yield a code with smaller length. In this case, the evaluation points are all powers of a generating field element \(\gamma\), \(\alpha_i=\gamma^i\). Each codeword \(\mu\) of an \(m\)-folded RS code is a string of \(n/m\) symbols, with each symbol being a string of values of a polynomial \(f_\mu\) at consecutive powers of \(\gamma\), \begin{align} \begin{split} \mu\to&\Big(\left(f_{\mu}(\alpha^{0}),\cdots,f_{\mu}(\alpha^{m-1})\right),\left(f_{\mu}(\alpha^{m}),\cdots,f_{\mu}(\alpha^{2m-1})\right)\cdots\\&\cdots,\left(f_{\mu}(\alpha^{n-m}),\cdots,f_{\mu}(\alpha^{n-1})\right)\Big)~. \end{split} \tag*{(1)}\end{align}

Decoding

Guruswami and Rudra [2,3] achieved list-decoding up to \(1-\frac{k}{n}-\epsilon\) fraction of errors using the Parvaresh-Vardy algorithm [4]; see Ref. [5] for a randomized construction.List-decoding works up to the Johnson bound using the Guruswami-Sudan algorithm [6].Folded RS codes, concatenated with suitable inner codes, can be efficiently list-decoded up to the Blokh-Zyablov bound [2,7].

Notes

See the book [8] for an introduction to FRS codes.A class of FRS codes can be used in the Yamakawa-Zhandry quantum algorithm [9].

Parent

  • Group-algebra code — FRS codes are polynomial ideal codes whose corresponding polynomial is a product of the polynomials of the RS codes that are being folded [6].

Child

Cousins

  • Parvaresh-Vardy (PV) code — The specific relations imposed on the polynomials of PV codes allow for them to be expressed in a similar way as FRS codes, but with more redundancy. Folded RS codes can be list-decoded up to a higher fraction of errors.
  • Folded quantum RS (FQRS) code

References

[1]
V. Y. Krachkovsky, “Reed-solomon codes for correcting phased error bursts”, IEEE Transactions on Information Theory 49, 2975 (2003) DOI
[2]
V. Guruswami and A. Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy”, (2007) arXiv:cs/0511072
[3]
Atri Rudra. List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington, 8 2007.
[4]
F. Parvaresh and A. Vardy, “Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 285 DOI
[5]
V. Guruswami, “Linear-Algebraic List Decoding of Folded Reed-Solomon Codes”, 2011 IEEE 26th Annual Conference on Computational Complexity 77 (2011) arXiv:1106.0436 DOI
[6]
S. Bhandari et al., “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, (2021) arXiv:2103.07930 DOI
[7]
V. Guruswami and A. Rudra, “Better Binary List Decodable Codes Via Multilevel Concatenation”, IEEE Transactions on Information Theory 55, 19 (2009) DOI
[8]
V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft available at this URL (2012).
[9]
T. Yamakawa and M. Zhandry, “Verifiable Quantum Advantage without Structure”, Journal of the ACM 71, 1 (2024) arXiv:2204.02063 DOI
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: folded_reed_solomon

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

Cite as:

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

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