Getting started with error correcting - polynomials!

Hello. This blog is a way for me to record my adventures in error correcting algorithms. I was inspired during an Abstract Algebra class when the professor noted in passing that to check if two n'th polynomials are equal, you only have to check n+1 points.

For instance, say you've got f(x) = (x+1)(x-1) and g(x) = x^2 - 1. If you wanted to determine equality visually, you'd have to multiply out f(x), or factor g(x), and compare them piece by piece. If all the pieces are the same, then the polynomials are the same. A different way is to evaluate f(-1), f(0), and f(1), then compare those values to g(-1), g(0), g(1). If all three values are equal then the polynomials are equal everywhere! (That works for any numbers, not just -1, 0, and 1.)

Well that got me thinking about polynomials. Of course! Just like any two points determine a line (degree 1), it's clear that any three points determine a quadratic, any four points determine a cubic, etc.

If you have a polynomial of degree 5, you can determine the coefficients either by looking at f(0), f(1), f(2), f(3), f(4), f(5), OR by looking at any other set of 6 points, such as f(1), f(2), f(3), f(4), f(5), f(6). See what happened there? We can lose f(0) and still get the same polynomial. After we've solved for the coefficients, we can evaluate f(0) and get back our original data.

Now scale that up to, say, a file on a computer. Imagine a polynomial where f(0) = the first byte in the file, f(1) = the second byte in the file, and so on. If we knew the polynomial, we could generate the entire file. The next step is to add redundancy so that if any of the data is lost, we can recover it. So if the file is n bytes long, and the file data is f(0), f(1), f(2), ..., f(n-1), then we add on a few more data points like f(n), f(n+1), f(n+2), and f(n+4). Now if you lose f(2), f(7), and f(400), you can recover them by determining f(x) from the points you do have and computing f(2), f(7), and f(400). Easy right?

The first thing we need to do is figure out how to determine f(x). Try it on your own and then check out my next post!