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:
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—Gottlob Frege (1848–1925)