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
- Reed-Solomon (RS) code — An FRS code with no extra grouping (\(m=1\)) reduces to an RS code.
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 Reed-Solomon (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) DOI
- [5]
- V. Guruswami, “Linear-Algebraic List Decoding of Folded Reed-Solomon Codes”, 2011 IEEE 26th Annual Conference on Computational Complexity (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”, (2022) arXiv:2204.02063
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