# Posts Tagged ‘Coding Theory’

## Two points determine a line, three a quadratic — what has that got to do with CDs?

In this post I describe how simple facts about polynomials are applied in correcting errors, for example scratches on compact disks. The same technique is used in many other places, e.g. in the 2-dimensional QuickResponse bar codes.

## Elements

The two facts from algebra that we need are:

**Theorem 1**. A polynomial of degree \(n\) has at most \(n\) zeros.

**Theorem 2.** If \((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\) are \(n\) points on the \(xy\)-plane such that \(x_i\neq x_j\) whenever \(i\neq j\),
then there is a unique polynomial \(f(x)\) of degree \(<n\) such that \(f(x_i)=y_i\) for all \(i\).

So, if \(n=2\), we want the polynomial \(f(x)\) to be linear. In that case, the graph \(y=f(x)\) will be the line passing through the points
\((x_1,y_1)\) and \((x_2,y_2)\). Similarly, when \(n=3\) we want the polynomial to be (at most) quadratic, and we want its graph to pass through the given three points. Finding the coefficients of such a quadratic is not too arduous an exercise in linear systems of equations.
For general \(n\) there is a known formula for the polynomial \(f(x)\) called *Lagrange’s interpolation polynomial* . The uniqueness
of such a polynomial follows from Theorem 1. If \(f_1(x)\) and \(f_2(x)\) were two different polynomials of degree \(<n\) passing through
all these \(n\) points, then their difference \(f_1(x)-f_2(x)\) is also of degree \(<n\) and vanishes at all the points \(x_i, i=1,2,\ldots,n\),
which is impossible by Theorem 1.

## Extending a message using a polynomial

The applications I discuss are about communication. We have two parties, a transmitter and a receiver. The transmitter wants to send
a message to the receiver. We assume that they have in advance agreed upon a method of coding the messages to sequences of numbers
\(y_1,y_2,\ldots,y_k\) for some natural number \(k\). The simplest way of communicating would be for the transmitter to simply write this
list of numbers to a *channel* that the receiver can later read. The channel could be something like a note that you pass to a classmate
or it could be compact disk, where the transmitter just writes the numbers. It could be something fancier like a radio frequency band, or an
optical fiber, but we ignore the physical nature of the channel here.