Computation of CRC - Example

Example

For a discussion of polynomial division modulo two, see Mathematics of CRC.

As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character "W", which is binary 01010111₂, decimal 87₁₀, or hexadecimal 57₁₆. For illustration, we will use the CRC-8-ATM (HEC) polynomial . Writing the first bit transmitted (the coefficient of the highest power of ) on the left, this corresponds to the 9-bit string "100000111".

The byte value 57₁₆ can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial . Msbit-first, this is = 01010111, while lsbit-first, it is = 11101010. These can then be multiplied by to produce two 16-bit message polynomials .

Computing the remainder then consists of subtracting multiples of the generator polynomial . This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions borrow "from infinity" instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.

Most-significant bit first

Least-significant bit first

0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0

1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0

Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero; at the end, a group which is unchanged from the original; and a shaded group in the middle which is "interesting". The "interesting" group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group becomes one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left.

In the msbit-first example, the remainder polynomial is . Converting to a hexadecimal number using the convention that the highest power of x is the msbit; this is A2₁₆. In the lsbit-first, the remainder is . Converting to hexadecimal using the convention that the highest power of x is the lsbit, this is 19₁₆.