Cyclic Redundancy Check Polynomials Tutorial

Cyclic redundancy check polynomials are the theory which lie behind the checksum algorithm used in most modern communication systems.
A generator is chosen (using theory which will not be detailed here). This is a sequence of bits, of which the first and last are 1. This sequence is used with the bits of the message to calculate a check sequence which has 1 fewer bits than the generator. The check sequence is appended to the original message. At the receiver, the same calculation is performed on the message and check sequence combined. If the result is 0 no transmission error is assumed to have occurred.
Try it now using the tutorial applet above.

You will observe that the bits 1111 have been added to the end of the transmitted buffer.

Now press the Clear button and try the message 10111101001101 and the sequence 0001 will be added.
How are these sequences calculated?

Division Algorithm

The sequence added is the remainder after the message bits are divided by the generator, treating the bits as the coefficients of a polynomial. Exclusive or is the operation that represents both addition and subtraction in this type of arithmetic.

If the buffers still contain the information they had after the second example above, you can press Reset to return them to the original state.

Checking

At the receiver, the message and the remainder are divided, and the remainder should come out as 0. Try this now with the data currently in the registers.

Shift Register Implementation

Although the operation fo the division algorithm looks complex, it only involves shifting and exclusive or operations. This can be conveniently arranged using a shift register. The output from the shift register is exclusive ored with the bits at positions in the shift register corresponding to the bit positions that are 1 in the generator.