Cyclic Redundancy Check (CRC) Step-by-Step Calculator

Cyclic Redundancy Check (CRC)

CRC is an error-detecting code is based on binary / polynomial “division”, and the sequence of redundant bits is appended to the end of a data unit so that the resulting data unit becomes exactly divisible (remainder=0) by a second predetermined binary number.

The CRC code requires definition of a so-called “generator polynomial” as the “divisor”.

And takes the message binary-shifted to left and extend the bit length with the divisor bit length minus one -1 (a.k.a. message binary is right padded with the bit length minus one of the CRC polynomial minus one -1) as the “dividend”, and the “remainder” becomes the result of CRC bits.

The polynomial coefficients are calculated according to the finite-field arithmetic as the binary long division. However, binary long division uses binary subtraction and “CRC long division” uses XOR operation. The XOR and addition operation can always be performed bitwise-parallel.

Back in the days when question like this is kinda time-consuming, here is a calculator which generate the step-by-step solution for all these problems.

This tools will display the answer in <table> form, which is Excel friendly, and <pre> as plain text for better compatibility in text-only environment.

Examples:

Question 1:

In a CRC error-detecting scheme, choose the generator polynomial as x4 + x + 1 (10011). Encode the 11-bit sequence: 10010011011

or

Given a CRC generator x4 + x + 1 (10011), calculate the CRC code for the message 10010011011. Show the steps clearly and derive the solution.

Answer:

  10001010100 <-- the quotient result is different than the actual division, which using binary subtraction.
10011100100110110000 <-- (input right padded by 4 bits (bit length of the CRC polynomial minus one 5-1=4))
 ⊕10011 <-- (10010 XOR 10011=12) but not a binary subtraction (10010 − 10011=11 1111 as negative one -110)
 10110 <-- (10010 XOR 10011=1 (1 bit)(*XOR mean minus each bit individually with unsigned result), and move the next 4 bit to fit the bit length of the CRC polynomial, which is 1 with 0110=10110, the divisor moves over to align with the next 1 in the dividend)
 10011
 10111 <-- (10110 XOR 10011=101 (3 bit)but not a binary subtraction (10110 − 10011=11 as positive three 310)
 10011
 10000
 10011
 1100 <-- CRC bits
The red zeroes "0" are the bit sequence to which append a number N of 0’s , where N=The length of CRC polynomial minus 1.
e.g.: CRC polynomial "10011" have the length of 5 bits, N=5 - 1=4 bits. Therefore, we append 4 zeros at the end of the data/message.
Dividend (Polynomial): x10 + x7 + x4 + x3 + x + 1
Divided by: x4 + x + 1
Quotient / Result is: x10 + x6 + x4 + x2
Remainder is: x3 + x2
CRC bits: 1100
Data 100100110111100 is sent

Question 2:

Suppose the channel introduces an error pattern 100010000000000 (i.e., a flip from 1 to 0 or from 0 to 1 in position 1 and 5) from the data in Question 1. What is received? Can the error be detected?

Answer:

Error mask:
100010000000000
Data to be filtered (The Answer of Question 1):
100100110111100
Filtered Data (Flip the 1-bit to 0-bit, 0-bit to 1 bit):
000110110111100
  11001110
10011000110110111100
 10011
 10000
 10011
 11111
 10011
 11001
 10011
 10100
 10011
 1110
Binary form: 000110110111100
Divided by: 10011
Quotient / Result is :11001110
Remainder / CRC bits: 1110
The remainder after division by 10011 is 1110, which is nonzero. The errors are detected

  x7 + x6   + x3 + x2 + x 
x4   + x + 1 x11 + x10  + x8 + x7 x5 + x4 + x3 + x2  
 x11   + x8 + x7
 x10    
 x10   + x7 + x6
 x7 + x6 + x5 + x4 + x3
 x7   + x4 + x3
 x6 + x5   + x2
 x6   + x3 + x2
 x5  + x3  
 x5   + x2 + x
 x3 + x2 + x 
Dividend (Polynomial): x11 + x10 + x8 + x7 + x5 + x4 + x3 + x2
Divided by: x4 + x + 1
Quotient / Result is: x7 + x6 + x3 + x2 + x
Remainder is: x3 + x2 + x
CRC bits: 1110
The remainder after division by x4 + x + 1 (10011) is x3 + x2 + x (1110), which is nonzero. The errors are detected

 

Conclusion:

The string 000110110111100 is received, corresponding to x11 + x10 + x8 + x7 + x5 + x4 + x3 + x2 .The remainder after division by x4 + x + 1 is x3 + x2 + x (CRC bits:1110), which is nonzero. The errors are detected.

For actual arithmetic binary division, we minus the divisor instead of XOR the divisor. For more details, read: Unsigned Binary Long Division Step-by-Step Calculator

Unsigned binary long division

Question: Solve 01111100 ÷ 0010

Answer:


Binary form: 01111100
Divided by: 10
Quotient / Result is :111110
Remainder: 0

         111110
     ----------
0010 ) 01111100
        10
        --
         11
         10
         --
          11
          10
          --
           11
           10
           --
            10
            10
            --
              0