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.

If everything goes well, the receiver can read the message correctly. But, they may misread one or more of the numbers. Or, one of the numbers may get smeared and become illegible while the note is exchanging hands. What to do? The basic idea is to add some redundancy to the message. We seek to extend the message from \(k\) numbers to \(n\) numbers, \(n>k\), in such a way that the receiver can recover from a few such mishaps. A useful way of doing this is to:

• Agree in advance on a sequence of \(n\) values for \(x\)-coordinates \(x_1,\ldots,x_n\).
• View the message \(y_1,y_2,\ldots,y_k\) as a sequence of \(k\) points $$(x_1,y_1), (x_2,y_2),\ldots, (x_k,y_k).$$
• Find the unique polynomial \(f(x)\) of degree \(<k\) passing through all these \(k\) points.
• Extend the message to \(y_1,y_2,\ldots,y_n\) in such a way that \(y_i=f(x_i)\) for all \(i=1,2,\ldots,n\). Note that the actual ‘payload’ message consists of the \(k\) first numbers, the remaining \(r=n-k\) are the redundant numbers.

Toy Example #1 – recovery from an illegible number

In the Figures below I always use \(x_1=1,x_2=2,\ldots,x_n=n\) for simplicity. Let us consider as an example the case \(k=2, n=3\), so our polynomials will always have degree \(\le1\), and their graphs are thus lines. Let us further select the message to be \((y_1,y_2)=(3,4)\). In this case the polynomial \(f(x)=x+2\) as \(f(1)=y_1\) and \(f(2)=y_2\). As \(f(3)=5\) the extended message is then \((y_1,y_2,y_3)=(3,4,5)\). In the figure below the payload part of the message is formed by the \(y\)-coordinates of the black dots and the \(y\)-coordinates of the red dot(s) are there for redundancy. I also include the entire graph of \(f(x)\) to make what follows clearer.

How does this minimum amount of redundancy help? Consider the scenario when the second numbers was, indeed, smeared and the receiver could only read the sequence as \((3,?,5)\). Now, our scheme allows the receiver to deduce that the missing number must be equal to \(4\). This is because they know that the points \((1,3), (2,?)\) and \((3,5)\) must all be on the same line.  With the knowledge that two points determine a line, the value of \(y_2=4\). What the receiver sees is shown in the Figure below.

Observe that it is immaterial here which of the three numbers was garbled. The receiver knows two points on the line, and can thus recover the polynomial \(f(x)\) and hence also the message.

Toy example #2 – spotting an error, and correcting it

However, adding a single redundant number does not protect us from other kinds of errors. Suppose that one of the numbers is misread, and the receiver reads \((y_1,y_2,y_3)=(3,2,5)\) instead of the correct sequence above. Now they cannot cope. The receiver can notice that the three points are not collinear, so they know that something went wrong. But, they have no way of knowing which of the three numbers is incorrect. Any pair of points gives a line all right, but now the received version of the message matches equally well with three distinct lines — all passing through two out of three points. The picture is as follows.

How can we cope with such errors? The solution is to add more redundancy. Let’s try \(k=2, n=4, r=4-2=2\) with two redundant numbers. Let’s again use the message \((y_1,y_2)=(3,4)\). This time we add a fourth point \((x_4,y_4)=(4,f(4))=(4,6)\), so the extended message (payload + redundancy) is now \((3,4,5,6)\). The picture is as follows.

If, again, one of the numbers is read incorrectly, then this time we can tell which one is incorrect, because the other three points are collinear.

Theorem 3. Given four points \(P_1,P_2,P_3,P_4\) on the plane there can be at most a single line containing at least three of those points.

Proof. Assume contrariwise that there are two lines, \(L_1\) and \(L_2\), both passing through at least three of the points. Because at most one of the four points is not on \(L_1\), and similarly at most one of the points is not on \(L_2\), we see that the lines \(L_1\) and \(L_2\) share at least \(4-1-1=2\) of the points. But there is a unique line through those two points, so \(L_1=L_2\). Q.E.D.

If in our toy example the receiver again makes a mistake with the second number and reads \((y_1,y_2,y_3,y_4)=(3,2,5,6)\), it will be easy for them to tell from the following picture, which point is the odd one out. Even without the plot of \(y=f(x)\) that I added to make things easier for you.

Coping with many problems in a single message

Ok, let us generalize. Assume that the payload consists of \(k\) numbers, and that we tag \(r=n-k\) redundant numbers to it so the entire transmitted list has \(n\) numbers. What kind of problems does this scheme protect us against? Above we encountered two kinds of problems. An erasure happens when the receiver cannot make out the written number. Observe that the receiver still knows the \(x\)-coordinate of that point (those were agreed in advance) — only the \(y\)-coordinate is missing. Another type of problem was an error, an incorrectly read number. From the toy examples we already got the feeling that, of these two, an error is more difficult to cope with. We needed two redundant numbers to correct a single error, but a single redundant number was enough to cope with an erasure.

Assume that we want to cater for the possibility of \(t\) errors and \(e\) erasures in a single transmission. How many redundant numbers do we need to cope with that? Altogether, the message gives us \(n=k+r\) points. The erasures mean that we only have \(n-e\) points remaining, and must manage with them. The goal is that these should somehow determine a unique polynomial of degree \(<k\). The solution is provided by the following generalization of Theorem 3.

Theorem 4. Given \(k+2t\) points with distinct \(x\)-coordinates on the plane there can be at most a single polynomial of degree \(<k\) whose graph passes through all but at most \(t\) of the points.

Proof. I am feeling a bit naughty and leaving this as an exercise. Use Theorem 2 in the same way that I used the fact “two points determine a unique line” in the proof of Theorem 3.

Corollary. When we append \(r\) redundant numbers to a payload of \(k\) according to this scheme we can cope with a combination of \(e\) erasures and \(t\) errors, if $$r\ge 2t+e.$$

So we see that adding redundancy makes the scheme more robust against the prescribed types of problems created by the channel. Of course, the added redundancy comes with a cost. A redundant number consumes the same amount of channel resources as a payload number (space on a CD or that piece of paper). There the user of this kind of a system needs to consider the probabilities of both errors and erasures, and then settle on a certain quality of service such that the inequality of Corollary is satisfied with a high enough probability.

Snakes in the paradise – need more algebra

There is one serious concern that I need to mention and address. Above I have loosely used the concept of a number without specifying what I meant by that. The figures undoubtedly left you with the impression that the numbers are usual real numbers. Unfortunately that won’t do. The basic reason is that to write down a real number with full precision takes infinitely many bits. But the messages on e.g. CDs consist of bytes. Programmers are used to viewing the value of a byte as an integer \(b\) in the range \(0\le b\le 255\). Even if we restrict the payload numbers to this range we cannot guarantee that the redundant numbers to be tagged would also oblige. Consider the following example of \(k=7, r=4\) and the payload \((y_1,\ldots,y_7)=(3, 7, 0, 1, 9, 6, 8)\). Here’s what the Lagrange interpolation polynomial looks like with these inputs.

Where are the red dots indicating the redundant numbers? Well, you can guess from the plot that the polynomial \(f(x)\) (it is of degree six) will increase very rapidly after the last payload. Indeed, this sextic polynomial gives the values \(f(8)=164, f(9)=903, f(10)=3129\) and \(f(11)=8464\) as the redundant numbers. So we face a serious overflow problem. Here’s a rescaled version of the plot.

Underflow is also possible as the redundant numbers may very well be negative. One might also worry that even though the payload consists of integers the redundant numbers might not. After all, Lagrange’s interpolation formula introduces divisions. Actually, as in the above overflow example, this never happens. But this is an artefact of the way we set up things. I leave this as an exercise for the interested reader.

Exercise. Let \(f(x)\in\mathbb{Q}[x]\) be the Lagrange interpolation polynomial (of degree \(<k\)) passing through the points \((1,y_1), (2,y_2), \ldots, (k,y_k)\), where all the numbers \(y_i, i=1,2,\ldots,k\) are integers. Show that \(f(n)\) is then an integer for all \(n\in\mathbb{Z}\).

But, we absolutely don’t want to use more than a single byte to present the redundant numbers. Or, more precisely, we insist that a redundant number should use the same amount of memory as a number in the payload part (a byte, a word,…). People familiar with elementary number theory may already feel the urge to reinterpret byte as a residue class modulo \(256\), i.e. as an element of the residue class ring \(R=\mathbb{Z}_{256}\). Unfortunately the algebra breaks down if we do that. To wit, already Theorem 1 fails dramatically. As an example, consider the linear polynomial \(f(x)=16x\). Even though it is linear, it has no less than sixteen distinct zeros in the ring \(R\), namely the residue classes of the form \(\overline{16m}\) for \(m=0,1,\ldots,15\). When you learn a bit more about the structures in abstract algebra you realize that the problem is that the ring \(R\) is not a field. But there is a field with 256 elements that fits the bill exactly! Its construction requires familiarity with polynomial rings and their quotient rings, and I don’t want to reproduce scores of pages from a first textbook on abstract algebra. To a reader who knows what is going on I will tell that

$$\mathbb{F}_{256}\cong\mathbb{F}_2[x]/\langle x^8+x^4+x^3+x^2+1\rangle$$

is a popular way of describing this field. A consequence of this is that the total length (payload + redundancy) of the messages in bytes cannot exceed \(256\). This is because at that point we run out of \(x\)-coordinates!

Links to more information

Coding theory is a topic straddling mathematics and communication engineering. It deals (among other things) in the design of schemes, like the one outlined here, aiming at coping with errors produced into messages by the channel. Two American coding theorists, Irving S. Reed and Gustave Solomon were the first to figure out this way of using the algebra of finite fields. One of their inventions was to choose the sequence of \(x\)-coordinates in a clever way that makes the calculation of the redundant numbers very easy (they can skip the time consuming use of Lagrange’s interpolation formula entirely). The resulting codes are called Reed–Solomon codes (or just RS-codes) in their honor. The Wikipedia-article on RS-codes  describes the algebra very differently, but in the end it is equivalent. That description reflects the more efficient calculation of the redundant part. I chose to present the codes in this way because it makes it easier to understand why these codes can cope with the prescribed types of errors.

Practical issues

I will close my contribution with a few remarks about certain practical aspects. The receiver faces the task of figuring out the correct polynomial. In the toy example of four points we could just take any pair of points (there are only six pairs), and check whether the line determined by them passes through a third point. But if we use a RS-code capable of correcting five errors with parameters \(k=240, r=10\), then the receiver following an analogous approach would need to generate \(\binom{250}{10}=219005316087032475\) Lagrange interpolation polynomials of degree \(239\), and check if one gives a good enough match. Not efficient at all! Thankfully, much more efficient algorithms have been developed by several other coding theorists.

The other remark I want to make has to do with compact disks. There, Reed-Solomon codes are used in the following way that produces good protection against typical scratching of the disk surface. The data on a CD is split into blocks like the one shown below.

Here each dot represents a single byte (actually, there is another error correcting code involved in reading a single byte from the disk that one is working at the level of individual bits and does not concern us here). The rows and columns in such a matrix are all encoded using an appropriate RS-code. The black dots are payload bytes. The encoding is done as follows. First, we add to each column four redundant bytes (green). Then we also add four redundant bytes to all the rows — in the payload part (red) as well as in the redundant part (blue). The bytes of a single row are close to each other on the CD, so the CD-player can read them quickly. It attempts to correct eventual errors. Usually it succeeds, but if that row is in a scratchy area, it fails, and then marks the entire row as unreliable data (i.e. an erasure). But different rows are more spaced out on the CD surface, so there is a high hope that only few rows from a given a matrix are lost in this fashion. If at most four of the rows are marked as erasures the column by column RS-code can recover the lost data. For the CD-player to be able to retrieve such matrices from the disk fast the entire matrix is on the same track (at the same distance from the disk center). Thus, a circular scratch may wipe out enough of the matrix, and the scheme will fail.

A happy thought: algebraic tools triumph in solving problems arising in communication.