Application: Error-correcting codes

A remarkable application of polynomials (and more generally, algebraic techniques in computer science) is in the construction of error-correcting codes. In this area, the goal is to encode a message so that it can be recovered when the message is corrupted (e.g., after sending the message through a communication channel). We consider two types of message corruptions: (i) erasure error, when parts of the message may be erased, and (ii) arbitrary error, when parts of the content can be corrupted and changed. The second type is much harder to handle because we would not know which parts of the message are correct and which are corrupted.

Protection against erasure errors

Suppose $x$ is the message to be sent. We can break the message $x$ into many parts (blocks) $(x_1,\ldots, x_n)$ where each $x_i$ can be seen as a number in ${\mathbb F}_q$ (well, just choose $q$ to be a large enough prime). Suppose we want to support the recovery of the message up to $k$ erasure errors. We would then need to create some redundancies to the content, and there is a natural way to do so using polynomials.

• There is a unique polynomial $f \in {\mathbb F}_q[x]$ of degree $(n-1)$ such that $f(1) = x_1, f(2) = x_2,\ldots, f(n) = x_n$. This polynomial contains all the information about message $x$.

• Create additional $k$ blocks by $x_{n+1} = f(n+1), x_{n+2}= f(n+2)$ until $x_{n+k} = f(n+k)$. We transmit the message $(x_1,\ldots, x_{n+k})$ which contains $(n+k)$ blocks. Notice that this is only possible if $q > n+k$.

Theorem 47

Let $I \subseteq [n+k]$ be a subset of size at least $n$ so that the blocks $\{x_i\}_{i \in I}$ are not erased. Then polynomial $f$ can be interpolated from these.

Proof:

From Theorem 44, there is a unique polynomial $p$ so that $p(i) = x_i$ for all $i \in I$. We claim that $p$ and $f$ are the same polynomial: Assume for a contradiction that they are not. Then $p-f$ is a polynomial of degree at most $(n-1)$ and that $(p-f)(x_i) = p(x_i) - f(x_i) = 0$ for all $i \in I$ (so it has at least $n$ roots) a contradiction.

Protection against arbitrary errors

Notice that the previous idea is to encode the message $x = (x_1,\ldots, x_n)$ by introducing redundancies into a "codeword" $C(x) = (x_1,\ldots, x_{n+k})$, which is longer than the original message. The nice thing is that by introducing $k$ additional blocks, we can handle the error up to $k$ erasures (and this is the best we can do!).

Now, suppose the error is arbitrary. What does it mean for us? In the erasure case, the message $(4,1,2,8)$ could get partially erased into $(4,-,2,8)$, so we know exactly that there is a missing block and (as explained before) it is possible to recover. But an arbitrary error could change the content of the message into $(4,10,2,8)$, and the receiver of the message has no way of knowing which part of the message is corrupted. Interestingly, it would turn out that we do not need to know it!!

The following description corresponds to the famous Reed-Solomon code.

• On message $x= (x_1,\ldots, x_n)$, let $f \in {\mathbb F}_q[x]$ of degree $(n-1)$ where $f(i) = x_i$ for all $i \in [n]$ (we know such $f$ is unique).

• Create additional points $x_{n+1}, \ldots, x_{n+2k}$ so that $x_i = f(i)$ for all $i\in[n+2k]\setminus[n]$. The code $C(x) = (x_1,\ldots, x_{n+2k})$ is sent across the communication channel. (notice that now we have $(n+2k)$ blocks instead of $(n+k)$).

We will prove some properties of this encoding. For messages $a=(a_1,\ldots, a_m)$ and $b=(b_1,\ldots, b_m)$, define $\Delta(a,b)$ as the number of coordinates $i \in [m]$ where $a_i \neq b_i$ (this is called the Hamming distance between $a$ and $b$).

Lemma 17 (Distance of Reed-Solomon codes)

For messages of the same length $n$, $x \neq y$, the distance between codewords $\Delta(C(x),C(y))$ is at least $(2k+1)$.

Proof:

Let $f_x$ and $f_y$ be the degree-$(n-1)$ polynomials for $x$ and $y$ respectively. Since they are distinct (do you see why?), we have that $(f_x- f_y)$ is nonzero and of degree at most $(n-1)$. Therefore, the codewords of $C(x)$ and $C(y)$ can agree on at most $(n-1)$ coordinates (blocks) (do you see why?). This implies the Hamming distance is at least $(n+2k) - (n-1) = 2k+1$.

Theoretically speaking, the distance property allows us to say that if $C(x)$ is corrupted at $k$ blocks into $C'$, we are still guaranteed that $C(x)$ is still the codeword closest to $C'$ (in Hamming distance), so if we look for message $y$ that minimizes $\Delta(C', C(y))$, then we would manage to find the original message as $x = \arg \min_{y} \Delta(C', C(y))$.

Indeed, the decoding algorithm by Berlekamp and Welsh exploits this property to efficiently recover the corrupted message (up to $k$ blocks). The details about this algorithm are beyond the scope of this course, but we invite you to search them if you are interested.