Cyclic Redundancy Check - Computation of CRC

Computation of CRC

To compute an n-bit binary CRC, line the bits representing the input in a row, and position the (n+1)-bit pattern representing the CRC's divisor (called a "polynomial") underneath the left-hand end of the row.

Start with the message to be encoded:

11010011101100

This is first padded with zeroes corresponding to the bit length n of the CRC. Here is the first calculation for computing a 3-bit CRC:

11010011101100 000 <--- input right padded by 3 bits 1011 <--- divisor (4 bits) = x³+x+1 ------------------ 01100011101100 000 <--- result

If the input bit above the leftmost divisor bit is 0, do nothing. If the input bit above the leftmost divisor bit is 1, the divisor is XORed into the input (in other words, the input bit above each 1-bit in the divisor is toggled). The divisor is then shifted one bit to the right, and the process is repeated until the divisor reaches the right-hand end of the input row. Here is the entire calculation:

11010011101100 000 <--- input right padded by 3 bits 1011 <--- divisor 01100011101100 000 <--- result 1011 <--- divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 1011 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <---remainder (3 bits)

Since the leftmost divisor bit zeroed every input bit it touched, when this process ends the only bits in the input row that can be nonzero are the n bits at the right-hand end of the row. These n bits are the remainder of the division step, and will also be the value of the CRC function (unless the chosen CRC specification calls for some postprocessing).

The validity of a received message can easily be verified by performing the above calculation again, this time with the check value added instead of zeroes. The remainder should equal zero if there are no detectable errors.

11010011101100 100 <--- input with check value 1011 <--- divisor 01100011101100 100 <--- result 1011 <--- divisor ... 00111011101100 100 ...... 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 0 <--- remainder