Mathematics of CRC - Polynomial Arithmetic Modulo 2

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:

    Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.
    Ralph Waldo Emerson (1803–1882)