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

{{{0}}}{{{1}}}{{{2}}}
`{{{3}}}`

{{{4}}}{{{5}}}{{{6}}}
`{{{7}}}`

# Error! Please wait for a while and try again.

{{message}}

### 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.

 1 0 0 0 1 0 1 0 1 0 0 <-- the quotient result is different than the actual division, which using binary subtraction. 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 <-- (input right padded by 4 bits (bit length of the CRC polynomial minus one 5-1=4)) ⊕ 1 0 0 1 1 <-- (10010 XOR 10011=12) but not a binary subtraction (10010 − 10011=11 1111 as negative one -110) 1 0 1 1 0 <-- (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) 1 0 0 1 1 1 0 1 1 1 <-- (10110 XOR 10011=101 (3 bit)but not a binary subtraction (10110 − 10011=11 as positive three 310) 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 1 0 0 <-- 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?

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

 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0
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.