Log in

No account? Create an account

Interesting fact about CRC

I lectured about the CRC error-checking code in my networks class today. I went slow, because it makes peoples heads explode if I don't.

When I started teaching CRC, I wanted to make sure I understood it well enough myself and so I worked a lot of problems involving bit polynomials (by which I mean polynomials with coefficients and arithmetic rules from GF(2)). I enjoyed it so much that I just kept playing with them, and proved some interesting things about them.

One of these interesting things is that if you multiply any bit polynomial by x+1, the result will have an even number of terms. I also established the converse, that any polynomial with an even number of terms is divisible by x+1.

The latter is easier to prove than the former.

First, it can be proven that
xn+1 = (x+1)(xn-1+xn-2+...1)
I will, as the textbook authors say, leave this as an exercise.

From this it follows that any two term polynomial xm+xn is divisible by
x+1. It's equal to x(m-n)( xn+1). We have seen that the second term of the product  is divisible by x+1.

Since a polynomial with an even number of terms is simply a sum of two term polynomials, it is necessarily divisible by x+1.

A polynomial with an even number of terms is equivalent to a bit string with an even number of ones. When you divide it by x+1, the remainder is 0. This is the same result you get when you do a parity check.

A similar argument can be made that a polynomial with an odd number of terms gives the same result as a parity check.

Thus, CRC with a generator polynomial of x+1 is equivalent to a parity check,

I shared this with my class as I wrapped up my lecture on CRC.

But I didn't give a proof. That would have made their heads explode
Tags: ,