Guruswami–Sudan list decoding algorithm

Input : A field $F$; n distinct pairs of elements $\{(x\_\{i\},y\_\{i\})\_\{i=1\}^n\}$ in $F\; \backslash times\; F$; and integers $d$ and $t$.

Output: A list of all functions $f:\; F\; \backslash to\; F$ satisfying

$f(x)$ is a polynomial in $x$ of degree at most $d$

{{NumBlk|:|$\backslash \#\backslash \{i|f(x\_\{i\})\; =\; y\_\{i\}\backslash \}\; \backslash ge\; t$|{{EquationRef|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\; \backslash ge\; (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\; =\; (\backslash sqrt\{2nd\})$. This bound is better than the unique decoding bound $1\; -\; \backslash left\; (\backslash frac\{R\}\; \{2\}\; \backslash right)$ for .

Definition 1 (weighted degree)

For weights $w\_x,w\_y\; \backslash in\; \backslash mathbb\{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)\; =\; \backslash sum\_\{ij\}\; q\_\{ij\}x^iy^j$ is the maximum, over the monomials with non-zero coefficients, of the $(w\_x,w\_y)$ – weighted degree of the monomial.

For example, $xy^2$ has $(1,3)$-degree 7

Algorithm:

Inputs: $n,d,t$; {$(x\_1,y\_1)\backslash cdots(x\_n,y\_n)$} /* Parameters l,m to be set later. */

Step 1: Find a non-zero bivariate polynomial $Q\; :\; F^2\; \backslash mapsto\; F$ satisfying

• $Q(x,y)$ has $(1,d)$-weighted degree at most $D=m+ld$
• For every $i\; \backslash in\; [n]$,

{{NumBlk|:|$Q(x\_i,y\_i)\; =\; 0$|{{EquationRef|2}}}}

Step 2. Factor 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\; \backslash in\; [n]$

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 $Q\; :\; F^2\; \backslash to\; F$ satisfying (2) exists, then one can find it in polynomial time.

Proof:

Note that a bivariate polynomial $Q(x,\; y\; )$ of $(1,\; d)$-weighted degree at most $D$ can be uniquely written as $Q(x,y)\; =\; \backslash sum\_\{j=0\}^l\; \backslash sum\_\{k=0\}^\{m+(l-j)d\}\; q\_\{kj\}\; x^k\; y^j$. Then one has to find the coefficients $q\_\{kj\}$ satisfying the constraints $\backslash sum\_\{j=0\}^l\; \backslash sum\_\{k=0\}^\{m+(l-j)d\}\; q\_\{kj\}\; x\_i^k\; y\_i^j\; =\; 0$, for every $i\; \backslash in\; [n]$. This is a linear set of equations in the unknowns {$q\_\{kj\}$}. One can find a solution using Gaussian elimination in polynomial time.

Claim 2:

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

Proof:

To ensure a non zero solution exists, the number of coefficients in $Q(x,y)$ should be greater than the number of constraints. Assume that the maximum degree $deg\_x(Q)$ of $x$ in $Q(x,y)$ is m and the maximum degree $deg\_y(Q)$ of $y$ in $Q(x,y)$ is $l$. Then the degree of $Q(x,y)$ will be at most $m+ld$. One has to see that the linear system is homogeneous. 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 a non-zero solution exists, one has to make sure that number of unknowns in the linear system to be $(m+1)(l+1)+d\; \backslash begin\{pmatrix\}l\; +\; 1\backslash \backslash 2\backslash end\{pmatrix\}\; >\; n$, so that one 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:

Consider a function $p(x)\; =\; Q(x,f(x))$. This is a polynomial in $x$, and argue that it has degree at most $m+ld$. Consider any monomial $q\_\{jk\}x^k\; y^j$ of $Q(x)$. Since $Q$ has $(1,d)$-weighted degree at most $m+ld$, one can say that $k+jd\; \backslash le\; m+ld$. Thus the term $q\_\{kj\}x^kf(x)^j$ is a polynomial in $x$ of degree at most $k+jd\; \backslash le\; m+ld$. Thus $p(x)$ has degree at most $m+ld$

Next argue that $p(x)$ is identically zero. Since $Q(x\_i,f(x\_i))$ is zero whenever $y\_i\; =\; f(x\_i)$, one can say 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))\; \backslash equiv\; 0$

Finding optimal values for $m$ and $l$.

Note that

For a given value $l$, one can compute the smallest $m$ for which the second condition holds

By interchanging the second condition one can get $m$ to be at most $(n+1-d\; \backslash begin\{pmatrix\}l\; +\; 1\backslash \backslash 2\backslash end\{pmatrix\})/2\; -\; 1$

Substituting this value into first condition one can get $t$ to be at least $\backslash frac\{n+1\}\{l+1\}\; +\; \backslash frac\{dl\}\{2\}$

Next minimize the above equation of unknown parameter $l$. One can do that by taking derivative of the equation and equating that to zero

By doing that one will get, $l\; =\; \backslash sqrt\{\backslash frac\{2(n+1)\}\{d\}\}\; -1$

Substituting back the $l$ value into $m$ and $t$ one will get

$m\; \backslash ge\; \backslash sqrt\{\backslash frac\{(n+1)d\}\{2\}\}\; -\; \backslash sqrt\{\backslash frac\; \{(n+1)d\}\{2\}\}\; +\; \backslash frac\{d\}\{2\}\; -\; 1\; =\; \backslash frac\{d\}\{2\}\; -1$

$t\; >\; \backslash sqrt\{\backslash frac\{2(n+1)d^2\}\{d\}\}\; -\; \backslash frac\; \{d\}\{2\}\; -1$

$t\; >\; \backslash sqrt\{2(n+1)d\}\; -\; \backslash frac\; \{d\}\{2\}\; -1$

Consider a $(n,k)$ Reed–Solomon code over the finite field $\backslash mathbb\{F\}\; =\; GF(q)$ with evaluation set $(\backslash alpha\_1,\backslash alpha\_2,\backslash ldots,\backslash alpha\_n)$ and a positive integer $r$, the Guruswami-Sudan List Decoder accepts a vector $\backslash beta\; =\; (\backslash beta\_1,\backslash beta\_2,\backslash ldots,\backslash beta\_n)$ $\backslash in$ $\backslash mathbb\{F\}^n$ as input, and outputs a list of polynomials of degree $\backslash le\; 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.

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 $\backslash le\; r$, where the x-degree of $f(x)$ is defined as the maximum degree of any x term in $f(x)$

$\backslash qquad$ $deg\_x\; f(x)$ $=$ $\backslash max\_\{i\; \backslash in\; I\}\; \backslash \{i\backslash \}$

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, $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, $Q(x,y)$ has a zero of multiplicity 1 at (0,0).

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

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

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

Similarly, if $Q(x,y)\; =\; [(y\; -\; \backslash beta)\; -\; 4(x\; -\; \backslash alpha)^2)]\; [(y\; -\; \backslash beta)\; +\; 6(x\; -\; \backslash alpha)^2)]$

Then, $Q(x,y)$ has a zero of multiplicity 2 at $(\backslash alpha,\backslash beta)$.

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

Let the transmitted codeword be $(\; f(\backslash alpha\_1),\; f(\backslash alpha\_2),\backslash ldots,f(\backslash alpha\_n))$,$(\backslash alpha\_1,\backslash alpha\_2,\backslash ldots,\backslash alpha\_n)$ be the support set of the transmitted codeword & the received word be $(\backslash beta\_1,\backslash beta\_2,\backslash ldots,\backslash beta\_n)$

The algorithm is as follows:

• Interpolation step

For a received vector $(\backslash beta\_1,\backslash beta\_2,\backslash ldots,\backslash 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 $(\backslash alpha\_i,\backslash beta\_i)$ where $1\; \backslash le\; i\; \backslash le\; n$

: $Q(\backslash alpha\_i,\backslash beta\_i)\; =\; 0\; \backslash ,$

• Factorization step

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

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

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

Lemma:

Interpolation step implies $\backslash begin\{pmatrix\}r\; +\; 1\backslash \backslash 2\backslash end\{pmatrix\}$ constraints on the coefficients of $a\_i$

Let $Q(x,y)\; =\; \backslash sum\_\{i\; =\; 0,\; j\; =\; 0\}\; ^\{i\; =\; m,\; j\; =\; p\}\; a\_\{i,j\}\; x^i\; y^j$

where $\backslash deg\_x\; Q(x,y)\; =\; m$ and $\backslash deg\_y\; Q(x,y)\; =\; p$

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

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

Proof of Equation 1:

: $Q(x\; +\; \backslash alpha,y\; +\; \backslash beta)\; =\; \backslash sum\_\{i,j\}\; a\_\{i,j\}\; (x\; +\; \backslash alpha)^i\; (y\; +\; \backslash beta)^j$

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

: $Q(x\; +\; \backslash alpha,y\; +\; \backslash beta)\; =\; \backslash sum\_\{u,v\}\; x^u\; y^v\; \backslash Bigg\; (\; \backslash sum\_\{i,j\}\; \backslash begin\{pmatrix\}i\backslash \backslash u\backslash end\{pmatrix\}\; \backslash begin\{pmatrix\}i\backslash \backslash v\; \backslash end\{pmatrix\}\; a\_\{i,j\}\; \backslash alpha^\{i-u\}\; \backslash beta^\{j-v\}\; \backslash Bigg\; )$

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

Proof of Lemma:

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

: $Q\_\{u,v\}$ $(\backslash alpha,\backslash beta)$ $\backslash equiv$ $0$ such that $0\; \backslash le\; u\; +\; v\; \backslash le\; r\; -\; 1$

: $u$ can take $r\; -\; v$ values as $0\; \backslash le\; v\; \backslash le\; r-1$. Thus, the total number of constraints is

$\backslash sum\_\{v\; =\; 0\}^\{r-1\}\; \{r\; -\; v\}$ $=$ $\backslash begin\{pmatrix\}r\; +\; 1\backslash \backslash 2\backslash end\{pmatrix\}$

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

Proposition:

$Q(x,\; p(x))\; \backslash 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)$, $Q(x,y)$ can be represented as

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

where, $L(x,y)$ is the quotient obtained when $Q(x,y)$ is divided by $y\; -\; p(x)$

$R(x)$ is the remainder

Now, if $y$ is replaced by $p(x)$,

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

Theorem:

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

Proof:

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

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

Given, $p(\backslash alpha)$ $=$ $\backslash beta$

$(p(x)\; -\; \backslash beta)$ mod $(x\; -\; \backslash alpha)$ $=$ $0$

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

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

As proved above,

$t\; \backslash cdot\; r\; >\; D$

$t\; >\; \backslash frac\{D\}\; \{r\}$

$\backslash frac\{D(D+2)\}\; \{2(k-1)\}\; >\; n\backslash begin\{pmatrix\}r\; +\; 1\backslash \backslash 2\backslash end\{pmatrix\}$

where LHS is the upper bound on the number of coefficients of $Q(x,y)$ and RHS is the earlier proved Lemma.

: $D\; =\; \backslash sqrt\{knr(r-1)\}\; \backslash ,$

Therefore, $t\; =\; \backslash left\; \backslash lceil\{\backslash sqrt\{kn\; (1\; -\; \backslash frac\{1\}\{r\})\}\}\; \backslash right\; \backslash rceil$

Substitute $r\; =\; 2kn$,

: $t\; >\; \backslash left\; \backslash lceil\; \{\backslash sqrt\{kn\; -\; \backslash frac\{1\}\{2\}\}\}\; \backslash right\; \backslash rceil\; >\; \backslash left\; \backslash lceil\; \{\backslash sqrt\{kn\}\}\; \backslash right\; \backslash rceil$

Hence proved, that Guruswami–Sudan List Decoding Algorithm can list decode Reed-Solomon codes up to $1\; -\; \backslash sqrt\{R\}$ errors.

• 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.

{{DEFAULTSORT:Guruswami-Sudan list decoding algorithm}}

Category:Coding theory