Guruswami–Sudan list decoding algorithm

Introduction

In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. Using unique decoder we can correct upto $\delta /2$ fraction of errors. But when error rate is greater than $\delta /2$ , unique decoder will not able to output the correct result. To overcome that issue, we go for list decoding. List decoding can correct more than $\delta /2$ fraction of errors.

There are many efficient algorithms that can perform List decoding. In this article, we will first look at list decoding algorithm for Reed–Solomon (RS) codes by Sudan which can correct upto $1-{\sqrt {2R}}$ errors. Later on, we will discuss Guruswami-Sudan list decoding algorithm, an improved version of Sudan's list decoding algorithm which can correct upto $1-{\sqrt {R}}$ errors.

Here is the plot between rate R and distance $\delta$ 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 $\mathbb {F}$ ; n distinct pairs of elements ${(x_{i},y_{i})_{i=1}^{n}}$ from $F\times F$ ; and integers $d$ and $t$ .

Output: A list of all functions $f:F\mapsto F$ satisfying

$f(x)$ is a polynomial in $x$ of degree at most d with | { $i|f(x_{i})=y_{i}$ } | $\geq t$ ------ (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 $t$ to be $t\geq (n+d+1)/2$ . 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 $(1,k)$ degree. Sudan's list decoding algorithm for Reed-Solomon code which is an improvement on Berlekamp and Welch algorithm, can solve the problem with $t=({\sqrt {2nd}})$ .This bound is better than the unique decoding bound $1-\left({\frac {R}{2}}\right)$ for $R<0.07$ .

We now present Sudan's algorithm for solving the problem.

Algorithm

Definition 1 (weighted degree)

For weights $w_{x},w_{y},\epsilon Z^{+}$ , the $(w_{x},w_{y})$ - weighted degree of monomial $q_{ij}x^{i}y^{j}$ is $iw_{x}+jw_{y}$ . The $(w_{x},w_{y})$ - weighted degree of a polynomial $Q(x,y)=\sum _{ij}q_{ij}x^{i}y^{j}$ is the maximum, over the monomials with non-zero coefficients, of the $(w_{x},w_{y})$ - weighted degree of the monomial.

Eg : $3xy$ is a monomial in variables $x,y$ with a coefficient of 3.

Algorithm:

Inputs: $n,d,t$ ; { $(x_{1},y_{1})....(x_{n},y_{n})$ } /* Parameters l,m to be set later. */

Step 1: Find any function $Q:F^{2}\mapsto F$ satisfying $Q(x,y)$ has (1,d)- weighted degree at most $m+ld$ , ---- (2) for every $i$ $\in$ n, $Q(x,y)=0,$ $Q$ is not identically zero.

Step 2. Factor the polynomial Q into irreducible factors.

Step 3. Output all the polynomials $f$ such that $(y-f(x))$ is a factor of Q and $f(x_{i})=y_{i}$ for at least t values of $i$ $\in$ n

Analysis

No we have to prove that the above algorithm runs in polynomial time and outputs the correct result. For that we will prove following set of claims.

Claim 1:

If a function $Q:F^{2}\mapsto F$ satisfying (2) exists, then we can find it in polynomial time.

Proof:

Note that a bivariate polynomial $Q(x,y)$ of $(1,k)$ degree at most $D$ can be represented as follows: Let $Q(x,y)=\sum _{j=0}^{l}\sum _{k=0}^{m+(l-j)d}q_{kj}x^{k}y^{j}$ . Then we have to find the coefficients $q_{kj}$ satisfying the constraints $\sum _{j=0}^{l}\sum _{k=0}^{m+(l-j)d}q_{kj}x^{k}y^{j}=0$ , for every $i\epsilon [n]$ . This is a linear set of equations in the unknowns { $q_{kj}$ }. We can find a solution using Gaussian Elimination in polynomial time.

Claim 2:

If $(m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n$ then there exists a function $Q(x,y)$ satisfying (2)

Proof:

To ensure that we have non zero solution, the number of variables in $Q(x,y)$ should be greater than the number of constraints. Lets assume that maximum degree $deg_{X}(Q)$ of $X$ in $Q(x,y)$ be m and maximum degree $deg_{Y}(Q)$ of $Y$ in $Q(x,y)$ be l. Then the degree of $Q(x,y)$ will be atmost $m+ld$ . We have to see that the linear system is homogenous. The setting $q_{jk}=0$ satisfies all linear constraints. However this does not satisfy (2), since the solution can be identically zero. To ensure that non-zero solutions exists, we have to make sure that number of unknowns in the linear system to be $(m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n$ , so that we can have a non zero $Q(x,y)$ . Since this value is greater than n, there are more variables than constraints and therefore a non-zero solution exists.

Claim 3:

If $Q(x,y)$ is a function satisfying (2) and $f(x)$ is function satisfying (1) and $t>m+ld$ , then $(y-f(x))$ divides $Q(x,y)$

Proof:

Lets consider a function $p(x)=Q(x,f(x))$ . This is a polynomial in $x$ , we will argue that it has degree at most $m+ld$ . Consider any monomial $q_{jk}x^{k}y^{j}ofQ(x)$ . Since $Qhas(1,d)$ - weighted degree at most $m+ld$ , we have that $k+jd\leq m+ld$ . Thus the term $q_{kj}x^{k}f(x)^{j}$ is a polynomial in $x$ of degree at most $k+jd\leq m+ld$ . Thus $p(x)$ has degree at most $m+ld$

Now we argue that $p(x)$ is identically zero. Since $Q(x_{i},f(x_{i}))$ is zero whenever $y_{i}=f(x_{i})$ , we have that $p(x_{i})$ is zero for strictly greater than $m+ld$ points. Thus $p$ has more zeroes than its degree and hence is identically zero, implying $Q(x,f(x))\equiv 0$

Now we will optimal values for $m$ and $l$ . Note that we want $m+ld<t$ and $(m+1)(l+1)+d{\begin{pmatrix}l+1\\2\end{pmatrix}}>n$ For a given value $l$ , we can compute the smallest $m$ for which the second condition holds By interchanging the second condition we get $m$ to be at most $(n+1-d{\begin{pmatrix}l+1\\2\end{pmatrix}})/2-1$ Substituting this value into first condition we get $t$ to be at least ${\frac {n+1}{l+1}}+{\frac {dl}{2}}$ We can now minimize the above equation of unknown parameter $l$ . We can do that by taking derivative of the equation and equating that to zero By doing that we get, $l={\sqrt {\frac {2(n+1)}{d}}}-1$ Substituting back the $l$ value into $m$ and $t$ we get $m\geq {\sqrt {\frac {(n+1)d}{2}}}-{\sqrt {\frac {(n+1)d}{2}}}+{\frac {d}{2}}-1={\frac {d}{2}}-1$ $t>{\sqrt {\frac {2(n+1)d^{2}}{d}}}-{\frac {d}{2}}-1$ $t>{\sqrt {2(n+1)d}}-{\frac {d}{2}}-1$

Algorithm 2 (Guruswami-Sudan List decoding Algorithm)

Definition

Consider a $(n,k)$ Reed-Solomon code over the finite field $\mathbb {F} =GF(q)$ with evaluation set $(\alpha _{1},\alpha _{2},....,\alpha _{n})$ and a positive integer $r$ , the Guruswami-Sudan List Decoder accepts a vector $\beta =(\beta _{1},\beta _{2},....,\beta _{n})$ $\in$ $\mathbb {F} ^{n}$ as input, and outputs a list of polynomials of degree $\leq k$ which are in 1 to 1 correspondence with codewords.

The idea is to add more restrictions on the bi-variate polynomial $Q(x,y)$ which results in the increment of constraints along with the number of roots.

Multiplicity

A bi-variate polynomial $Q(x,y)$ has a zero of multiplicity $r$ at $(0,0)$ means that $Q(x,y)$ has no term of degree $\leq r$ .

where the x-degree of $f(x)$ is defined as the maximum degree of any x term in $f(x)$ $\qquad$ $deg_{x}f(x)$ $=$ $\max _{i\in I}\{i\}$

For example: Let $Q(x,y)$ $=$ $y-4x^{2}$ .

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

Hence, we can say that $Q(x,y)$ has a zero of multiplicity 1 at (0,0).

Let $Q(x,y)$ $=$ $y+6x^{2}$ .

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

Hence, we can say that $Q(x,y)$ has a zero of multiplicity 1 at (0,0).

Let $Q(x,y)$ $=$ $(y-4x^{2})(y+6x^{2})$ $Q(x,y)$ $=$ $y^{2}+6x^{2}y-4x^{2}y-24x^{4}$

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

Hence, we can say that $Q(x,y)$ has a zero of multiplicity 2 at (0,0).

Similarly, if $Q(x,y)$ $=$ $[(y-\beta )-4(x-\alpha )^{2})][(y-\beta )+6(x-\alpha )^{2})]$ Then, $Q(x,y)$ has a zero of multiplicity 2 at $(\alpha ,\beta )$ .

General Definition of Multiplicity:

$Q(x,y)$ has $r$ roots at $(\alpha ,\beta )$ if $Q(x,y)$ has a zero of multiplicity $r$ at $(\alpha ,\beta )$ when $(\alpha ,\beta )\neq (0,0)$ .

Algorithm

Let the transmitted codeword be $(f(\alpha _{1}),f(\alpha _{2}),....,f(\alpha _{n}))$ , $(\alpha _{1},\alpha _{2},....,\alpha _{n})$ be the support set of the transmitted codeword & the received word be $(\beta _{1},\beta _{2},....,\beta _{n})$

The algorithm is as follows:

• Interpolation step

For a received vector $(\beta _{1},\beta _{2},....,\beta _{n})$ , construct a non-zero bi-variate polynomial $Q(x,y)$ with $(1,k)-$ weighted degree of at most $d$ such that $Q$ has a zero of multiplicity $r$ at each of the points $(\alpha _{i},\beta _{i})$ where $1\leq i\leq n$

$Q(\alpha _{i},\beta _{i})=0$

• Factorization step

Find all the factors of $Q(x,y)$ of the form $y-p(x)$ and $p(\alpha _{i})=\beta _{i}$ for at least $t$ values of $i$

where $0\leq i\leq n$ & $p(x)$ is a polynomial of degree $\leq k$

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

Analysis

Interpolation step

Lemma: Interpolation step implies ${\begin{pmatrix}r+1\\2\end{pmatrix}}$ constraints on the coefficients of $a_{i}$

Let $Q(x,y)$ $=$ $\sum _{i=0,j=0}^{i=m,j=p}$ $a_{i,j}$ $x^{i}$ $y^{j}$ where $\deg _{x}Q(x,y)$ $=$ $m$ & $\deg _{y}Q(x,y)$ $=$ $p$

Then, $Q(x+\alpha ,y+\beta )$ $=$ $\sum _{u=0,v=0}^{r}$ $Q_{u,v}$ $(\alpha ,\beta )$ $x^{u}$ $y^{v}$ ........................(Equation 1)

where $Q_{u,v}$ $(x,y)$ $=$ $\sum _{i=0,j=0}^{i=m,j=p}$ ${\begin{pmatrix}i\\u\end{pmatrix}}$ ${\begin{pmatrix}j\\v\end{pmatrix}}$ $a_{i,j}$ $x^{i-u}$ $y^{j-v}$

Proof of Equation 1:

$Q(x+\alpha ,y+\beta )$ $=$ $\sum _{i,j}$ $a_{i,j}$ $(x+\alpha )^{i}$ $(y+\beta )^{j}$

$Q(x+\alpha ,y+\beta )$ $=$ $\sum _{i,j}$ $a_{i,j}$ ${\Bigg (}\sum _{u}$ ${\begin{pmatrix}i\\u\end{pmatrix}}$ $x^{u}$ $\alpha ^{i-u}{\Bigg )}$ ${\Bigg (}\sum _{v}$ ${\begin{pmatrix}i\\v\end{pmatrix}}$ $y^{v}$ $\beta ^{j-v}{\Bigg )}$ .................Using binomial expansion

$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 )}$

$Q(x+\alpha ,y+\beta )$ $=$ $\sum _{u,v}$ $Q_{u,v}$ $(\alpha ,\beta )$ $x^{u}$ $y^{v}$

Proof of Lemma:

The polynomial $Q(x,y)$ has a zero of multiplicity $r$ at $(\alpha ,\beta )$ if

$Q_{u,v}$ $(\alpha ,\beta )$ $\equiv$ $0$ such that $0\leq u+v\leq r-1$

$u$ can take $r-v$ values as $0\leq v\leq r-1$ . Thus, the total number of constraints is $\sum _{v=0}^{r-1}{r-v}$ $=$ ${\begin{pmatrix}r+1\\2\end{pmatrix}}$

Thus, ${\begin{pmatrix}r+1\\2\end{pmatrix}}$ number of selections can be made for $(u,v)$ and each selection implies constraints on the coefficients of $a_{i}$

Factorization step

Proposition:

$Q(x,p(x))$ $\equiv$ $0$ if $y-p(x)$ is a factor of $Q(x,y)$

Proof:

Since, $y-p(x)$ is a factor of $Q(x,y)$ , we can write

$Q(x,y)$ $=$ $L(x,y)(y-p(x))$ $+$ $R(x)$

where, $L(x,y)$ is the quotient we obtained when $Q(x,y)$ is divided by $y-p(x)$ $R(x)$ is the remainder

Now, replacing $y$ by $p(x)$ , we get,

Hence, $Q(x,p(x))$ $\equiv$ $0$ , only if $R(x)$ $\equiv$ $0$

Theorem:

If $p(\alpha )$ $=$ $\beta$ , then $(x-\alpha )^{r}$ is a factor of $Q(x,p(x))$

Proof:

$Q(x,y)$ $=$ $\sum _{u,v}$ $Q_{u,v}$ $(\alpha ,\beta )$ $(x-\alpha )^{u}$ $(y-\beta )^{v}$ ...........................From Equation 2

$Q(x,p(x))$ $=$ $\sum _{u,v}$ $Q_{u,v}$ $(\alpha ,\beta )$ $(x-\alpha )^{u}$ $(p(x)-\beta )^{v}$

Given, $p(\alpha )$ $=$ $\beta$ $(p(x)-\beta )$ mod $(x-\alpha )$ $=$ $0$

Hence, $(x-\alpha )^{u}$ $(p(x)-\beta )^{v}$ mod $(x-\alpha )^{u+v}$ $=$ $0$

Thus, $(x-\alpha )^{r}$ is a factor of $Q(x,p(x))$ .

As we know,

$t\cdot r>D$ $t>{\frac {D}{r}}$

${\frac {D(D+2)}{2(k-1)}}$ $>$ $n{\begin{pmatrix}r+1\\2\end{pmatrix}}$ where LHS is the upper bound on the number of coefficients of $Q(x,y)$ and RHS is the earlier proved Lemma.