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}Rate
FRS codes achieve relaxed generalized Singleton bounds [2].Decoding
Guruswami and Rudra [3,4] achieved list-decoding up to \(1-\frac{k}{n}-\epsilon\) fraction of errors using the Parvaresh-Vardy algorithm [5]; see Ref. [6] for a randomized construction.List-decoding works up to the Johnson bound using the Guruswami-Sudan algorithm [7].Folded RS codes, concatenated with suitable inner codes, can be efficiently list-decoded up to the Blokh-Zyablov bound [3,8].Notes
See the book [9] for an introduction to FRS codes.A class of FRS codes can be used in the Yamakawa-Zhandry quantum algorithm [10].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
Primary Hierarchy
Parents
FRS codes are polynomial ideal codes whose corresponding polynomial is a product of the polynomials of the RS codes that are being folded [7].
Folded RS (FRS) code
Children
An FRS code with no extra grouping (\(m=1\)) reduces to an RS code.
References
- [1]
- V. Y. Krachkovsky, “Reed-solomon codes for correcting phased error bursts”, IEEE Transactions on Information Theory 49, 2975 (2003) DOI
- [2]
- Y. Chen and Z. Zhang, “Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds”, (2025) arXiv:2408.15925
- [3]
- V. Guruswami and A. Rudra, “Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy”, (2007) arXiv:cs/0511072
- [4]
- Atri Rudra. List Decoding and Property Testing of Error Correcting Codes. PhD thesis, University of Washington, 8 2007.
- [5]
- 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
- [6]
- 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
- [7]
- S. Bhandari, P. Harsha, M. Kumar, and M. Sudan, “Ideal-Theoretic Explanation of Capacity-Achieving Decoding”, (2021) arXiv:2103.07930 DOI
- [8]
- V. Guruswami and A. Rudra, “Better Binary List Decodable Codes Via Multilevel Concatenation”, IEEE Transactions on Information Theory 55, 19 (2009) DOI
- [9]
- V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft available at this URL (2012).
- [10]
- T. Yamakawa and M. Zhandry, “Verifiable Quantum Advantage without Structure”, Journal of the ACM 71, 1 (2024) arXiv:2204.02063 DOI
Page edit log
- Victor V. Albert (2022-09-16) — most recent
- Victor V. Albert (2022-03-21)
Cite as:
“Folded RS (FRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/folded_reed_solomon