Guruswami–Sudan list decoding algorithm
In coding theory, list decoding is an alternative to unique decoding of error-correcting codes in the presence of many errors.  If a code has relative distance , then it is possible in principle to recover an encoded message when up to  fraction of the codeword symbols are corrupted. But when error rate is greater than , this will not in general be possible.  List decoding overcomes that issue by allowing the decoder to output a short list of messages that might have been encoded.  List decoding can correct more than  fraction of errors.

There are many polynomial-time algorithms for list decoding.  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  errors.

Here is a plot of the rate R and distance  for different algorithms.

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg

Algorithm 1 (Sudan's list decoding algorithm)

Problem statement

Input : A field ; n distinct pairs of elements  in ; and integers  and .

Output: A list of all functions  satisfying

 is a polynomial in  of degree at most 

To understand Sudan's Algorithm better, one may want to first know another algorithm which can be considered as the earlier version or the fundamental version of the algorithms for list decoding RS codes - the Berlekamp–Welch algorithm.
Welch and Berlekamp initially came with an algorithm which can solve the problem in polynomial time with best threshold on  to be . 
The mechanism of Sudan's Algorithm is almost the same as the algorithm of Berlekamp–Welch Algorithm,  except in the step 1, one wants to compute a bivariate polynomial of bounded  degree. Sudan's list decoding algorithm for Reed–Solomon code which is an improvement on Berlekamp and Welch algorithm, can solve the problem with . This bound is better than the unique decoding bound  for .

Algorithm

Definition 1 (weighted degree)

For weights , the  – weighted degree of monomial  is . The  – weighted degree of a polynomial  is the maximum, over the monomials with non-zero coefficients, of the  – weighted degree of the monomial.

For example,  has -degree 7

Algorithm:

Inputs: ; {} /* Parameters l,m to be set later. */

Step 1: Find a non-zero bivariate polynomial  satisfying
  has -weighted degree at most 
 For every ,

Step 2. Factor Q into irreducible factors.

Step 3. Output all the polynomials  such that  is a factor of Q and  for at least t values of

Analysis 

One has to prove that the above algorithm runs in polynomial time and outputs the correct result. That can be done by proving following set of claims.

Claim 1:

If a function  satisfying (2) exists, then one can find it in polynomial time.

Proof:

Note that a bivariate polynomial  of -weighted degree at most  can be uniquely written as . Then one has to find the coefficients  satisfying the constraints , for every . This is a linear set of equations in the unknowns {}. One can find a solution using Gaussian elimination in polynomial time.

Claim 2:

If  then there exists a function  satisfying (2)

Proof:

To ensure a non zero solution exists, the number of coefficients in  should be greater than the number of constraints. Assume that the maximum degree  of  in  is m and the maximum degree  of  in  is . Then the degree of  will be at most .  One has to see that the linear system is homogeneous. The setting  satisfies all linear constraints. 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 , so that one can have a non zero . Since this value is greater than n, there are more variables than constraints and therefore a non-zero solution exists.

Claim 3:

If  is a function satisfying (2) and  is function satisfying (1) and , then  divides 

Proof:

Consider a function . This is a polynomial in , and argue that it has degree at most . Consider any monomial  of . Since  has -weighted degree at most , one can say that . Thus the term  is a polynomial in   of degree at most  . Thus  has degree at most 

Next argue that  is identically zero. Since  is zero whenever , one can say that  is zero for strictly greater than  points. Thus has more zeroes than its degree and hence is identically zero, implying 

Finding optimal values for  and .
Note that  and 
For a given value  , one can compute the smallest  for which the second condition holds
By interchanging the second condition one can get  to be at most 
Substituting this value into first condition one can get  to be at least 
Next minimize the above equation of unknown parameter . One can do that by taking derivative of the equation and equating that to zero
By doing that one will get, 
Substituting back the  value into  and  one will get

Algorithm 2 (Guruswami–Sudan list decoding algorithm)

Definition

Consider a  Reed–Solomon code over the finite field  with evaluation set  and a positive integer , the Guruswami-Sudan List Decoder accepts a vector      as input, and outputs a list of polynomials of degree  which are in 1 to 1 correspondence with codewords.

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.

Multiplicity

A bi-variate polynomial  has a zero of multiplicity  at  means that  has no term of degree , where the x-degree of  is defined as the maximum degree of any x term in 
     

For example: 
Let .

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg

Hence,  has a zero of multiplicity 1 at (0,0).

Let .

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg

Hence,  has a zero of multiplicity 1 at (0,0).

Let 

https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg

Hence,  has a zero of multiplicity 2 at (0,0).

Similarly, if 
Then,  has a zero of multiplicity 2 at .

General definition of multiplicity
 has  roots at  if   has a zero of multiplicity  at  when .

Algorithm
Let the transmitted codeword be , be the support set of the transmitted codeword & the received word be 

The algorithm is as follows:

• Interpolation step

For a received vector , construct a non-zero bi-variate polynomial  with weighted degree of at most  such that  has a zero of multiplicity  at each of the points  where 

 

• Factorization step

Find all the factors of  of the form  and  for at least  values of 

where  &  is a polynomial of degree 

Recall that polynomials of degree  are in 1 to 1 correspondence with codewords. Hence, this step outputs the list of codewords.

Analysis

Interpolation step

Lemma:
Interpolation step implies  constraints on the coefficients of 

Let 
where  and 

Then,        ........................(Equation 1)

where          

Proof of Equation 1:

 

.................Using binomial expansion

 

  

Proof of Lemma:

The polynomial  has a zero of multiplicity  at  if

     such that 

  can take  values as . Thus, the total number of constraints is
  

Thus,  number of selections can be made for  and each selection implies constraints on the coefficients of

Factorization step

Proposition:

 if  is a factor of 

Proof:

Since,  is a factor of ,  can be represented as

  

where,  is the quotient obtained when  is divided by 
 is the remainder

Now, if  is replaced by , 
  , only if   

Theorem:

If , then  is a factor of 

Proof:

      ...........................From Equation 2

      

Given,   
 mod   

Hence,   mod   

Thus,  is a factor of .

As proved above,

where LHS is the upper bound on the number of coefficients of  and RHS is the earlier proved Lemma.

 

Therefore, 

Substitute ,

 

Hence proved, that Guruswami–Sudan List Decoding Algorithm can list decode Reed-Solomon codes up to  errors.

References
https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/
 https://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf
http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes/
 R. J. McEliece. The Guruswami-Sudan Decoding Algorithm for Reed-Solomon Codes.
 M Sudan. Decoding of Reed Solomon codes beyond the error-correction bound.

Coding theory