Efficient Decoding for Reed–Solomon

We will see a (non-local) efficient decoding algorithm for Reed-Solomon codes.

Let $\mathbb F$ be the $q$-element field and let $f\colon \mathbb F\to \mathbb F$ be a function (a corrupted evaluation of a degree-$d$ polynomial). The goal is to find a degree-$d$ polynomial $P\in \mathbb F[x]_{d}$ that agrees with $f$ as often as possible.

Theorem: If less than $(q-d)/2$ positions are corrupted, we can decode $P$ in time $\mathrm{poly}(q)$.

Proof:

First, suppose that there exists a degree-$d$ polynomial $P$ that perfectly agrees with $f$. How can we find such a polynomial? One way to find $P$ is to set up the following linear system (in the coefficients of $P$) and solve it using Gaussian elimination, $$P(\alpha_1)=f(\alpha_1),$$ $$\ldots$$ $$P(\alpha_{q})=f(\alpha_{q}).$$ (Here, $\alpha_1,\ldots,\alpha_{q}$ is an enumeration of the elements of $\mathbb F$.)

Next, suppose that $f$ is corrupted in $\tau$ positions. We will try to reduce to the case without errors! For sake of analysis, let $E\in\mathbb F[x]_\tau$ be the degree-$\tau$ polynomial that vanishes on the corrupted positions, i.e., $$E = \prod_{\alpha\colon f(\alpha)\neq P(\alpha)} (x-\alpha).$$

Now, the polynomials $N=F\cdot E$ and $E$ satisfy the equation $N(\alpha)=f(\alpha)\cdot E(\alpha)$ for every $\alpha\in \mathbb F$. (We zeroed out the errors!)

Via Gaussian elimination, we can find non-zero polynomials $N'\in \mathbb F[x]_{\tau+d}$ and $E'\in \mathbb F[x]_\tau$ that satisfy the following linear constraints (on their coefficients), $$N'(\alpha_1) = f(\alpha_1)\cdot E'(\alpha_1),$$ $$\ldots$$ $$N'(\alpha_q) = f(\alpha_q)\cdot E'(\alpha_{q}),$$

Finally, we want to show that $P=N'/E'$ (in that case, we can compute $P$ easily from $N'$ and $E'$). In other words, we want to show that $P\cdot E'-N'$ is the zero polynomial. On the one hand, the degree of this polynomial is at most $\tau+d$. On the other hand, the polynomial has at least $q-\tau$ roots (on for each uncorrupted position of $f$). Hence, if $q-\tau > \tau + d$, the polynomial is indeed the zero polynomial

End of Proof.