Decoding Reed-Solomon Codes

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 18, April 2 Scribe: Fred Block

Let n=q be a prime power. We fix an order of the elements in ${\mathbb F}_{q}$ as

$$a_1, a_2, \dots, a_n.$$

Then an [n, k, n-k+1] Reed-Solomon code consists of codewords of the form

$$c=(c_1,\dots,c_n), \ \ \ \mbox{where} \ c_i=f(a_i), \,1\leq i \leq n,$$

for some $f(x)\in {\mathbb F}_{q}[x]$ with $\deg(f(x)) \leq k-1$.

Suppose $c=(c_1,\dots,c_n)$ was sent but received as

$$r=(c_1,\dots,c_n)+(e_1,\dots,e_n)$$

where $e=(e_1,\dots,e_n)$ is the error vector. The received vector will be written as $r=(b_1,\dots,b_n).$How do we recover c from r?

Consider the collection of points

$$(a_1,b_1),\dots,(a_n,b_n) \in {\mathbb F}_{q}^2$$

and the vanishing ideal

$${\mathbf I}=\{g\in {\mathbb F}_{q}[x,y]:\,g(a_i,b_i)=0,\, 1\leq i \leq n \}.$$ (25)

As a special case, consider $e=(e_1,\dots,e_n)=0$. It is easy to check that

$$g_0=\prod_{i=1}^n(x-a_i)=x^n-x \in {\mathbf I}$$ (26)

and

$$g_1=y-f(x) \in {\mathbf I}.$$

In fact, g₀ and g₁ form a Gröbner basis for I under lexicographical order with y>x. (Note that ${\mathbb F}_{q}[x,y]/\left<g_0,g_1\right> \cong {\mathbb F}_{q}[x]/\left<g_0\right>$.) Here g₁ has degree k-1, which is ``small'' compared to n. This hints that a ``small'' element in a Gröbner basis for I may give us some information about f(x) (or the codeword c).

Lemma 18.1   For any $r=(b_1,\dots,b_n) \in {\mathbb F}_{q}^n$, define g₀ as in (27) and

g₁=y-u(x)

where $u(x)\in {\mathbb F}_{q}[x]$ satisfies

$$u(a_i)=b_i, \, 1\leq i \leq n.$$

Then $\{g_0,g_1\}$ is a Gröbner basis for the vanishing ideal I under lexicographical order with y>x.

Proof. Given by some student project?

Suppose r=c+e as before. Assume that the Hamming weight of eis t. That is, there are t errors, say at locations $i_1, \dots,i_t$. Let

$$w(x)=\prod_{j=1}^{t}(x-a_{i_j})$$

be the error locator polynomial. Then w(a_i)=0 if and only if $b_i \ne f(a_i)$ (i.e. $e_i \ne 0$), $1 \leq i \leq n$. Hence

$$g_3(x,y)=(y-f(x))w(x) \in {\mathbf I}$$

as $g_3(a_i,b_i)=0, \, 1 \leq i \leq n$. The polynomial g₃ is of the form

$$g(x,y)=u_1(x)y-u_0(x), \ \ \ \mbox{where}\ \deg(u_1(x)) \leq t, \deg(u_0(x)) \leq k-1+t.$$ (27)

Pictorially, g has the shape shown in Figure 1.

  

Figure 1: The Newton polytope of g.

Theorem 18.2 (Berlekamp and Welch)   Let I be the vanishing ideal in (26) where $r=(b_1, \cdots, b_n)$comes from a code word defined by $f(x)\in {\mathbb F}_{q}[x]$ with $\deg(f(x)) \leq k-1$. Suppose t<(n-k+1)/2. Then, for any $g \in {\mathbf I}$ that has the form (28), we have

$$f(x)=\frac{u_0(x)}{u_1(x)}.$$

Such a polynomial g(x,y) can be found in polynomial time, so Reed-Solomon codes can be decoded in polynomial time (for t<(n-k+1)/2).

Proof. Since $g \in {\mathbf I}$, we have

$$u_1(a_i)b_i=u_0(a_i), \, 1 \leq i \leq n.$$

Also, we know

$$(b_i-f(a_i))w(a_i)=0, \, 1 \leq i \leq n,$$

i.e.

$$b_i w(a_i)=f(a_i)w(a_i), \, 1 \leq i \leq n.$$

Then

$$\begin{eqnarray*}w(a_i)f(a_i)u_1(a_i) & = & b_i w(a_i) u_1(a_i) = w(a_i) u_o(a_i), \,1 \leq i \leq n. \end{eqnarray*}$$

Hence the polynomial

h(x)=w(x)(u₀(x)-f(x)u₁(x))

vanishes at $a_i, \, 1 \leq i \leq n$. But $\deg(h(x))\leq t + (k-1+t) < n$ if t<(n-k+1)/2. So h(x) must be identically zero. That is,

w(x)(u₀(x)-f(x)u₁(x))=0.

Hence u₀(x)=f(x)u₁(x). The theorem follows. $\Box$

What can be done if t>(n-k+1)/2?