Folded RS (FRS) code[1]


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}


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.Folded RS codes, concatenated with suitable inner codes, can be efficiently list-decoded up to the Blokh-Zyablov bound [2][6].


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


  • Linear \(q\)-ary code — Folding an RS code yields a code that is no longer linear over \(GF(q)\) but is linear over \(GF(q^m)\).




V. Y. Krachkovsky, “Reed-solomon codes for correcting phased error bursts”, IEEE Transactions on Information Theory 49, 2975 (2003) DOI
V. Guruswami and A. Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy”, (2007) arXiv:cs/0511072
Atri Rudra. List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington, 8 2007.
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) DOI
V. Guruswami, “Linear-Algebraic List Decoding of Folded Reed-Solomon Codes”, 2011 IEEE 26th Annual Conference on Computational Complexity (2011) arXiv:1106.0436 DOI
V. Guruswami and A. Rudra, “Better Binary List Decodable Codes Via Multilevel Concatenation”, IEEE Transactions on Information Theory 55, 19 (2009) DOI
V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft available at this URL (2012).
T. Yamakawa and M. Zhandry, “Verifiable Quantum Advantage without Structure”, (2022) arXiv:2204.02063
Page edit log

Your contribution is welcome!

on (edit & pull request)

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.
@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={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Folded RS (FRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.