In coding theory, list decoding is an alternative to unique decoding of error-correcting codes in the presence of many errors.
fraction of the codeword symbols are corrupted.
List decoding overcomes that issue by allowing the decoder to output a short list of messages that might have been encoded.
In this article, we first present an algorithm for Reed–Solomon (RS) codes which corrects up to
errors and is due to Madhu Sudan.
Subsequently, we describe the improved Guruswami–Sudan list decoding algorithm, which can correct up to
Welch and Berlekamp initially came with an algorithm which can solve the problem in polynomial time with best threshold on
Sudan's list decoding algorithm for Reed–Solomon code which is an improvement on Berlekamp and Welch algorithm, can solve the problem with
is the maximum, over the monomials with non-zero coefficients, of the
*/ Step 1: Find a non-zero bivariate polynomial
One has to prove that the above algorithm runs in polynomial time and outputs the correct result.
satisfying (2) exists, then one can find it in polynomial time.
Proof: Note that a bivariate polynomial
One can find a solution using Gaussian elimination in polynomial time.
satisfying (2) Proof: To ensure a non zero solution exists, the number of coefficients in
However this does not satisfy (2), since the solution can be identically zero.
To ensure that a non-zero solution exists, one has to make sure that number of unknowns in the linear system to be
Since this value is greater than n, there are more variables than constraints and therefore a non-zero solution exists.
, the Guruswami-Sudan List Decoder accepts a vector
as input, and outputs a list of polynomials of degree
The idea is to add more restrictions on the bi-variate polynomial
which results in the increment of constraints along with the number of roots.
is defined as the maximum degree of any x term in
be the support set of the transmitted codeword & the received word be
The algorithm is as follows: • Interpolation step For a received vector
Hence, this step outputs the list of codewords.
Lemma: Interpolation step implies
and each selection implies constraints on the coefficients of
where LHS is the upper bound on the number of coefficients of
and RHS is the earlier proved Lemma.