Folded Reed–Solomon code

Updated 2026-07-01

In coding theory, folded Reed–Solomon codes (FRS codes) are a family of error-correcting codes derived from Reed–Solomon (RS) codes by grouping consecutive symbols of an RS codeword into larger alphabet symbols. They were introduced by V. Y. Krachkovsky in 2003 in the context of correcting phased burst errors, and the term "folded Reed–Solomon codes" was coined in that work. The codes were later shown by Venkatesan Guruswami and Atri Rudra in 2006 to achieve the list-decoding capacity, meaning they can be efficiently list-decoded up to a fraction (1 − R − ε) of errors for any rate R and any ε > 0, which is information-theoretically optimal.

Definition

Let F_q be a finite field of size q, and let γ be a primitive element of F_q^*. Consider a Reed–Solomon code of length n = q − 1 and dimension k, where codewords are evaluations of polynomials f(X) of degree at most k − 1 at the points 1, γ, γ², …, γⁿ⁻¹. For a folding parameter m ≥ 1 that divides n, the m-folded Reed–Solomon code, denoted FRS_F,γ,m,k, is a code of block length N = n/m over the alphabet F_q^m. The encoding of a polynomial f(X) is given by grouping m consecutive evaluations:

f ↦ ⟨ [f(1), f(γ), …, f(γ^m−1)], [f(γ^m), f(γ^m+1), …, f(γ^2m−1)], …, [f(γ^n−m), f(γ^n−m+1), …, f(γⁿ⁻¹)] ⟩.

The folding operation does not change the rate R = k/n of the original Reed–Solomon code. The relative distance of the folded RS code meets the Singleton bound and is at least 1 − R.

Relationship to Parvaresh–Vardy codes

Folded Reed–Solomon codes are a special case of Parvaresh–Vardy (PV) codes. When the folding parameter m is used, the FRS code can be viewed as a compressed form of a PV code of order m. The key insight is that the FRS code has the same information as the corresponding PV code but with a higher rate, leading to a better trade-off between rate and list-decoding radius.

List-decoding

The main significance of folded Reed–Solomon codes is that they can be list-decoded in polynomial time up to a fraction 1 − R − ε of errors for any ε > 0, achieving the list-decoding capacity. This was a breakthrough result by Guruswami and Rudra (2006), which provided the first explicit construction of codes achieving list-decoding capacity for all rates.

Linear-algebraic list-decoding algorithm

Guruswami (2011) presented a linear-algebraic list-decoding algorithm for folded RS codes that runs in n^Ω(1/ε²) time and achieves a decoding radius of 1 − R − ε with a list size of n^O(1/ε²). The algorithm consists of three steps:

Interpolation step: A nonzero multivariate polynomial Q(X, Y₁, …, Y_s) = A₀(X) + A₁(X)Y₁ + … + A_s(X)Y_s is interpolated through the received word using a Welch–Berlekamp-style approach. This is done by solving a homogeneous linear system.
Root-finding step: All polynomials f(X) of degree at most k − 1 satisfying Q(X, f(X), f(γX), …, f(γ^s−1X)) = 0 are found. The solutions form an affine subspace of dimension at most s − 1.
Prune step: The solution subspace is pruned to obtain the actual list of close-by codewords. Using subspace-evasive subsets (Dvir and Lovett, 2011), the list size can be reduced to a constant.

Constant list sizes

Kopparty, Ron-Zewi, Saraf, and Wootters (2018) showed that folded Reed–Solomon codes achieve list-decoding capacity with constant list sizes independent of the block length, improving upon the earlier polynomial list-size bounds.

Parameters

For a folded Reed–Solomon code FRS_q^(m)[n, k] with block length N = n/m and rate R = k/n, the following holds for all integers s with 1 ≤ s ≤ m: given a received word, one can find a subspace of dimension at most s − 1 that contains all message polynomials whose FRS encoding differs from the received word in at most a fraction (s/(s+1))·(1 − mR/(m − s + 1)) of the N codeword positions.

By choosing s = 1/ε and m = 1/ε², the decoding radius approaches 1 − R − ε with alphabet size q^O(1/ε²) and list size q^O(1/ε).

Applications

Folded Reed–Solomon codes have been used in various contexts, including:

As outer codes in concatenated code constructions to obtain binary codes list-decodable up to the Zyablov bound.
In the Yamakawa–Zhandry quantum algorithm for verifiable quantum advantage.
As building blocks for locally list-recoverable codes and capacity-achieving locally list-decodable codes.

References

Krachkovsky, V. Y. (2003). "Reed–Solomon codes for correcting phased error bursts". IEEE Transactions on Information Theory. 49 (11): 2975–2984.
Guruswami, V.; Rudra, A. (2006). "Explicit capacity-achieving list-decodable codes". Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). pp. 1–10.
Guruswami, V. (2011). "Linear-Algebraic List Decoding of Folded Reed-Solomon Codes". 2011 IEEE 26th Annual Conference on Computational Complexity. pp. 77–85.
Dvir, Z.; Lovett, S. (2011). "Subspace evasive sets". arXiv:1110.5696 [cs.CC].
Kopparty, S.; Ron-Zewi, N.; Saraf, S.; Wootters, M. (2018). "Improved Decoding of Folded Reed-Solomon and Multiplicity Codes". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS).