Yes, I still use the same hard disk platter as a drink coaster. But I need more ISA cards in my collection.


I've used the #lazyweb tag on hellsite for a long time. Since I can do more long form writing here, I figure I can crowdfund answers to my questions here as well! It sure beats posting on Stack Exchange :D!

Why Is CRC Polynomial Division Defined As It Is?

CRC defines polynomial division by discarding carried/borrowed terms during the subtracting/adding phase of polynomial division. This has very convenient properties, such as making addition and subtraction the same thing:

E.g. in CRC-based polynomial addition/subtraction:

(x^5 + x^2 + x^1) + (x^5 + x^3 + x^2) = (x^5 - x^5) + (0 - x^3) + (x^2 - x^2) + (0 - x^1) = x^3 + x^1

In "standard" polynomial addition/subtraction:

(x^5 + x^2 + x^1) + (x^5 + x^3 + x^2) = (x^5 + x^5) + (0 + x^3) + (x^2 + x^2) + (0 + x^1) = 2x^5 + x^3 + 2x*2 + x^1 

Is that the main reason to define CRC division in terms of "addition == subtraction"? If we instead defined CRC polynomial division as the "standard" polynomial addition/subtraction, do we still get the nice properties of CRC division as normally defined, such as "two polynomials that differ by a single term can be distinguished solely by doing the division one degree at a time and then looking at the remainder"?


You must log in to comment.

in reply to @cr1901's post:

Another way to describe that is "polynomials over integers mod 2". For the most part, math that works on the real numbers works on the finite set of integers mod p where p is prime (you have multiplication and addition with the usual commutative, associative, distributive properties, and inverses and stuff, with the bonus that (nonzero) integers have multiplicative inverses that are also integers). I think terms like "field" and "ring" describe the kind of structure these have in common.

Also for the most part, math on polynomials works similarly to math on numbers, and math on polynomials mod a "primitive polynomial" (one that can't be factored into smaller ones) works like math on numbers mod a prime, much like math on regular polynomials over real numbers works like math on real numbers.

The CRC-update operation is really "multiply the register by x^8 and add the incoming byte", and the whole CRC operation is "treat the incoming bits as coefficients of a polynomial; compute the residue mod the generator polynomial from the spec".

Disclaimer: I had one abstract algebra course last century. I have done CRC and CRC-like things since then.

The main reason to use these sorts of operations seems to be "it works easily on a computer and does the job". If you used coefficients mod a larger prime, or just regular integers as coefficients, that would preserve more information about the data being CRC'd and add more redundancy, but the result would be larger and so harder to transmit.