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.