Polynomial Arithmetic Modulo 2
Since the coefficients are constrained to a single bit, any math operation on CRC polynomials must map the coefficients of the result to either zero or one. For example in addition:
Note that becomes zero in the above equation because addition of coefficients is performed modulo 2:
Multiplication is similar:
We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing by . We would find that
In other words,
The division yields a quotient of x² + 1 with a remainder of -1, which, since it is odd, has a last bit of 1.
In the above equations, represents the original message bits 111, is the generator polynomial, and the remainder (equivalently, ) is the CRC. The degree of the generator polynomial is 1, so we first multiplied the message by to get .
Read more about this topic: Mathematics Of CRC
Famous quotes containing the word arithmetic:
“Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build my arithmetic.... It is all the more serious since, with the loss of my rule V, not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic seem to vanish.”
—Gottlob Frege (1848–1925)