### 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

x

I will, as the textbook authors say, leave this as an exercise.

From this it follows that any two term polynomial x

x+1. It's equal to x

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

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

x

^{n}+1 = (x+1)(x^{n-1}+x^{n-2}+...1)I will, as the textbook authors say, leave this as an exercise.

From this it follows that any two term polynomial x

^{m}+x^{n}is divisible byx+1. It's equal to x

^{(m-n)}( x^{n}+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

## Comments