Folded RS (FRS) code[1]
Description
A code obtained from an RS code by bundling consecutive symbols into larger alphabet symbols. This preserves the algebraic structure of the parent RS code while lowering the block length over an extension alphabet, and it is a key ingredient in capacity-approaching list-decoding constructions.
An \([n/m,k]_{q^m}\) FRS code is obtained from an \([n,k]_q\) RS code by grouping consecutive evaluations, thereby reducing the block length over a larger alphabet. In this case, the evaluation points are powers of a field element \(\gamma\), namely \(\gamma^0,\gamma^1,\ldots,\gamma^{n-1}\). Each codeword \(\mu\) of an \(m\)-folded RS code is a string of \(n/m\) symbols, with each symbol being a block of values of a polynomial \(f_\mu\) at consecutive powers of \(\gamma\), \begin{align} \begin{split} \mu\to&\Big(\left(f_{\mu}(\gamma^{0}),\cdots,f_{\mu}(\gamma^{m-1})\right),\left(f_{\mu}(\gamma^{m}),\cdots,f_{\mu}(\gamma^{2m-1})\right)\cdots\\&\cdots,\left(f_{\mu}(\gamma^{n-m}),\cdots,f_{\mu}(\gamma^{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
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”, LIPIcs, Volume 207, APPROX/RANDOM 2021 207, 56:1 (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