CRC calculator, with the division step by step

A CRC (cyclic redundancy check) is the remainder of dividing a message by a generator polynomial in arithmetic where adding and subtracting are both XOR. Below, work through that division bit by bit, or get the CRC-8, CRC-16 and CRC-32 of any text or hex bytes under the standard presets.

How the CRC division works

Write the generator as bits, one per power of x: x^4 + x + 1 is 10011. Its degree r, here 4, is the length of the CRC.

• Append r zeros to the message: 1101011111 becomes 11010111110000.
• Wherever the leftmost remaining 1 is, XOR the generator in underneath it, and repeat until fewer than r + 1 bits are left after the last 1.
• The last r bits are the remainder, here 0010. Send the message followed by it: 11010111110010.
• The receiver divides that whole codeword by the same generator. A remainder of 0000 means no error was detected.

There are no carries and no borrows: mod-2 arithmetic is just XOR, which is why the division is so cheap in hardware. The calculator's arithmetic is tested against an independent polynomial remainder on 2,000 random messages, and every single flipped bit in those codewords is caught.

CRCs in hardware

A CRC needs no divider circuit. A shift register of r flip-flops with an XOR gate wherever the generator has a 1 (a linear feedback shift register) takes the message one bit per clock and holds the remainder at the end (a free-running one is the LFSR pseudo-random generator). That is why Ethernet, USB and disk controllers compute CRCs at full line speed. The same idea of adding redundant bits drives the Hamming code and parity, which can locate or flag errors; a CRC only detects them, but catches far more. The error detection and correction lesson compares them.

The standard CRCs

Real protocols fix more than the polynomial. Each preset follows the CRC RevEng catalogue, whose model adds four parameters: the register's starting value (Init), whether input bytes and the result are bit-reversed (RefIn, RefOut) and a final XOR (XorOut). The catalogue lists a check value for each, the CRC of the ASCII text 123456789, and every preset in this calculator reproduces its check value.

Frequently asked

How do you calculate a CRC?

Treat the message bits as a polynomial, append as many zeros as the degree of the generator polynomial, and divide by the generator using XOR instead of subtraction. The remainder is the CRC, and the sender transmits the message followed by it. The step-by-step mode above shows every XOR.

What is the CRC of 1101011111 with generator 10011?

0010. The generator 10011 is x^4 + x + 1, so four zeros are appended and the division leaves the 4-bit remainder 0010. The transmitted codeword is 11010111110010, and dividing it by 10011 leaves 0000.

How does the receiver check a CRC?

It divides the whole received codeword, message and CRC together, by the same generator. A remainder of all zeros means no error was detected; anything else means the data was corrupted.

What errors does a CRC detect?

With a generator of at least two terms it detects every single-bit error, and with a +1 term it detects every burst of errors no longer than the CRC itself. Longer or scattered errors slip through only rarely, about once in 2^r for an r-bit CRC.

What is the difference between CRC-32 and CRC-32C?

They use different generator polynomials: CRC-32 (CRC-32/ISO-HDLC, used by ZIP and PNG) uses 0x04C11DB7, and CRC-32C (Castagnoli, CRC-32/ISCSI) uses 0x1EDC6F41. Both reflect the bits and start and end with 0xFFFFFFFF, so the check value of 123456789 is CBF43926 for CRC-32 and E3069283 for CRC-32C.

What do init, RefIn, RefOut and XorOut mean?

They are the parameters of the standard CRC model. Init is the starting value of the register, so leading zero bytes still change the result; RefIn and RefOut reverse the bit order of each input byte and of the result, to match links that send the lowest bit first; XorOut is XORed into the final value. Two CRCs with the same polynomial but different parameters give different results.

Why are there so many CRC-16 variants?

Different standards picked different polynomials and parameters long ago. CRC-16/MODBUS and CRC-16/ARC share the polynomial 0x8005 but start from FFFF and 0000; CRC-16/XMODEM, CRC-16/KERMIT and CRC-16/IBM-3740 (often called CCITT-FALSE) all use 0x1021. Use the one your protocol names, and check it with 123456789.