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)
[edit]
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
![{\displaystyle \#\{i|f(x_{i})=y_{i}\}\geq t}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a3b9a3ab06a1f280131d3ce1da250efadb7c47c1) | | (1) |
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
.
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 ![{\displaystyle D=m+ld}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/cfb62d17a62868d4725e016ca21e5dcba1f3c8b9)
- For every
,
![{\displaystyle Q(x_{i},y_{i})=0}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a0fe03c5dff4460fc4c1045af25615c640c6448f) | | (2) |
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
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)
[edit]
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.
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
[edit]
has
roots at
if
has a zero of multiplicity
at
when
.
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
![{\displaystyle Q(\alpha _{i},\beta _{i})=0\,}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e131b981ec9bebb7bd433cafc183b3fe1f1f585a)
• 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.
Lemma:
Interpolation step implies
constraints on the coefficients of
Let
where
and
Then,
........................(Equation 1)
where
Proof of Equation 1:
![{\displaystyle Q(x+\alpha ,y+\beta )=\sum _{i,j}a_{i,j}(x+\alpha )^{i}(y+\beta )^{j}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/bd62cba4abbd806f9b9243a506a524f1d5bb98b5)
.................Using binomial expansion
![{\displaystyle Q(x+\alpha ,y+\beta )=\sum _{u,v}x^{u}y^{v}{\Bigg (}\sum _{i,j}{\begin{pmatrix}i\\u\end{pmatrix}}{\begin{pmatrix}i\\v\end{pmatrix}}a_{i,j}\alpha ^{i-u}\beta ^{j-v}{\Bigg )}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3f0bb49c1f8f987f6a1d89235b6cff99a7dc1b09)
![{\displaystyle Q_{u,v}(\alpha ,\beta )x^{u}y^{v}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/03d7700aedb00dd9c5289da4b424589b7f9a898d)
Proof of Lemma:
The polynomial
has a zero of multiplicity
at
if
such that ![{\displaystyle 0\leq u+v\leq r-1}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/7b87f4f12382baf2a0044d72d8092d960fc15d7d)
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
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.
![{\displaystyle D={\sqrt {knr(r-1)}}\,}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e830dadf5aa6168de2ec03fc50e7ba551602fd2f)
Therefore,
Substitute
,
![{\displaystyle t>\left\lceil {\sqrt {kn-{\frac {1}{2}}}}\right\rceil >\left\lceil {\sqrt {kn}}\right\rceil }](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/7f5fa75f85310524f921295673685c0da93389bc)
Hence proved, that Guruswami–Sudan List Decoding Algorithm can list decode Reed-Solomon codes up to
errors.