Folded Reed–Solomon code

Krachkovsky with an algorithm that presented Reed–Solomon codes with many random "phased burst" errors.

[1] The list-decoding algorithm for folded RS codes corrects beyond the

bound for Reed–Solomon codes achieved by the Guruswami–Sudan algorithm for such phased burst errors.

Prior to Folded Reed–Solomon codes being devised, the best Error-Correction Radius achieved was

Folded Reed–Solomon Codes improve on these previous constructions, and can be list decoded in polynomial time for a fraction

Then bundling is performed in groups of 3 elements, to give a codeword of length

Something to be observed here is that the folding operation demonstrated does not change the rate

According to the asymptotic version of the singleton bound, it is known that the relative distance

are tasks of almost the same computational intensity: one can unfold the received word of the folded Reed–Solomon code, treat it as a received word of the original Reed–Solomon code, and run the Reed–Solomon list decoding algorithm on it.

This propagation of errors is indicated by the blue color in the graphical description.

for the set of evaluation points If we compare the folded RS code to a PV code of order 2 for the set of evaluation points we can see that in PV encoding of

Thus, the PV and folded RS codes have same information but only the rate of FRS is bigger by a factor of

One can use this idea to construct a folded RS codes of rate

In the third step the actual list of close-by codewords are known by pruning the solution subspace which takes

In the Interpolation step it will try to find the candidate message polynomial

-folded Reed–Solomon code as shown below We interpolate the nonzero polynomial by using a carefully chosen degree parameter

presents an algebraic condition that must be satisfied for those message polynomials

, we have Further we can get the decoding bound We notice that the fractional agreement is During this step, our task focus on how to find all polynomials

This fact is the key point that gives rise to an efficient algorithm - we can solve the linear system.

This lemma shows us the upper bound of the dimension for the solution space.

for the parameter choices that achieve a list decoding radius of

But the actual list of close-by codewords is only a small set within that subspace.

Things get better if we change the code by carefully choosing a subset of all possible degree

polynomials as messages, the list size shows to be much smaller while only losing a little bit in the rate.

By converting the problem of decoding a folded Reed–Solomon code into two linear systems, one linear system that is used for the interpolation step and another linear system to find the candidate solution subspace, the complexity of the decoding problem is successfully reduced to quadratic.

However, in the worst case, the bound of list size of the output is pretty bad.

It was mentioned in Step 2 that if one carefully chooses only a subset of all possible degree

, which satisfies below two conditions: This is to make sure that the rate will be at most reduced by factor of

Dvir and Lovett improved the result based on the work of Guruswami, which can reduce the list size to a constant.

If we don't consider the Step 3, this algorithm can run in quadratic time.