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.

Enter the message 01011101010110.
Enter the generator 11011.
Pressing the Step button repeatedly will transfer bits from the message to the transmitted buffer.
After all the message bits have been transferred, continue to press Step a further 5 times.

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.

Press the check symbol beside Polynomial division. A window will appear with the generator sequence as a divisor in a long division sum.
As you press the Step button, the bits of the message will appear in the dividend.
When Step is pressed for the 6th time, the quotient starts to appear as a 1 bit.
The dividend is exclusive ored with the divisor and one extra bit is brought down from the dividend to give 11001.
This can be divided by 11011 so the next step adds a 1 bit to the quotient, exclusive ors the 11001 with 11011 to give 0010 and a 0 bit is brought down from the dividend giving 00100.
Because the leading bit is 0, the divisor does not divide it, and a 00000 is exclusive ored with it, a 0 added to the quotient and the next 1 bit brought down.
The algorithm continues, exclusive oring the partial dividend with the divisor whenever the leading bit of the dividend is 1, and with 00000 when it is 0.
When the original dividend is exhausted 0000 is added to the dividend.
The algorithm continues, and when all the dividend and the 4 extra bits are exhausted, the remainder 0001 has been calculated.

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.

Press the Exchange button, and the transmitted register is moved to the message register.
Press the Check check box, and the calculation will now assume that the contents of the message register is for checking, and will not add extra 0 bits to the end of the message.
As you press Step you will notice that when you reach the extra 4 bits corresponding to the remainder, where previously a 1 would have appeared in the remainder, a zero will now appear because a 1 has been inserted in the dividend.
When you have finished, 0 will be left in the remainder line of the division.

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.

Press Reset to restart the calculation.
Press the Shift register check box.
Perform the calculation again, noting how the contents of the shift register match the partial dividends in the polynomial division window.