CRC Visualization | Cyclic Redundancy Check by XOR Long Division

The idea: send a remainder along with the data

Bits get damaged on the way: electrical noise on a cable, a scratch on a disk, a bad memory cell. A cyclic redundancy check (CRC) lets the receiver notice. The sender divides the message by a fixed generator and sends the remainder, the CRC, after the message. The receiver divides the whole frame by the same generator. Remainder 0 means the frame is accepted; anything else means it was damaged.

The sender appends four zeros to the message 1101011011, divides by 10011 and gets remainder 1110, which replaces the zeros to form the frame 11010110111110. The frame crosses a link where noise may flip bits. The receiver divides it by 10011: remainder 0000 means accept, a non-zero remainder means drop. — The frame is built to be an exact multiple of G, so a non-zero remainder at the receiver can only come from an error.

Bits as a polynomial

Read a string of bits as a polynomial whose coefficients are 0 or 1. Bit k, counted from 0 on the right, is the coefficient of x^k. So 1101011011 is M(x) = x⁹ + x⁸ + x⁶ + x⁴ + x³ + x + 1. The arithmetic is mod 2: 1 + 1 = 0, there are no carries and no borrows, and adding and subtracting are the same operation, XOR. That makes the long division simple enough for a few gates.

The generator used on the page is G(x) = x⁴ + x + 1, or 10011. Its degree r = 4 is the number of check bits. Multiplying by x⁴ shifts the message 4 places left, which is the same as appending 4 zero bits.

The division, step by step

The sender divides M(x)·x^r by G(x) (Demo: sender computes the CRC):

Write the message followed by r zeros.
Find the leading 1. Write G under it and XOR, column by column. The leading bit becomes 0.
Bring the next bits down until the window starts with a 1 again. A leading 0 means "G goes 0 times": nothing to XOR.
Stop when no 1 is left in a message position. The last r bits are the remainder R(x), the CRC.

For 1101011011 and 10011 it takes 4 XOR steps and the remainder is 1110. The sender puts it in place of the zeros and transmits 11010110111110. Only the remainder matters; the quotient is thrown away. The same long division with ordinary numbers is on Polynomial Long Division.

Why the receiver gets 0

Division gives M(x)·x^r = Q(x)·G(x) + R(x). In mod-2 arithmetic adding R(x) is the same as subtracting it, so the transmitted frame T(x) = M(x)·x^r + R(x) = Q(x)·G(x) is an exact multiple of G. The receiver divides the whole frame, CRC included, and gets remainder 0 (Demo: clean link, remainder 0). Then it drops the last r bits to get the message back.

If noise flips some bits, the receiver gets T(x) + E(x), where the error pattern E(x) has a 1 at every flipped bit. Its remainder is the remainder of E(x) alone, because T(x) contributes nothing. So the question "is the error caught?" is just "does G divide E?" (Demo: one flipped bit is caught). The receiver does not learn which bit is wrong. It drops the frame, and a higher layer (TCP, or the application) sends it again.

What a CRC catches, and what it misses

error	caught when	with x⁴ + x + 1
one flipped bit	G has at least two terms	always
a burst of length ≤ `r`	G has the term 1 (x⁰)	always for bursts of up to 4 bits (Demo: burst of 4 flipped bits is caught)
two flipped bits	G does not divide x^k + 1 for any gap `k` in the frame	frames up to 15 bits, since x⁴ + x + 1 is primitive (period 15)
any odd number of flips	(x + 1) is a factor of G	no: G is irreducible, so some 3-bit errors slip through
a longer burst	missed with probability about 2^−r	1 in 16

An error is missed exactly when E(x) is a multiple of G(x). Flipping bits 9, 6 and 5 gives E(x) = x⁹ + x⁶ + x⁵ = G(x)·x⁵. The receiver's remainder is 0 and it accepts a wrong frame (Demo: undetected, error is a multiple of G). That is why real CRCs use many check bits: with r = 32 a random error slips through about once in four billion frames.

Real CRCs

name	generator	used in
CRC-8	x⁸ + x² + x + 1 (`0x07`)	ATM cell header, SMBus
CRC-16-CCITT	x¹⁶ + x¹² + x⁵ + 1 (`0x1021`)	HDLC, X.25, Bluetooth, SD cards
CRC-32	degree 32, `0x04C11DB7`	the Ethernet FCS, zip, gzip, PNG chunks
CRC-32C (Castagnoli)	degree 32, `0x1EDC6F41`	iSCSI, SCTP, ext4 and Btrfs metadata; x86 has a `crc32` instruction for it

CRC-32 is everywhere. Every Ethernet frame ends with a 4-byte frame check sequence (FCS): a CRC-32 over the header and payload. A switch or NIC that sees a bad FCS drops the frame silently. zip and gzip store the CRC-32 of the uncompressed data to check that unpacking worked, and every PNG chunk ends with a CRC-32 of its type and data. Real CRC-32 adds a few details the page leaves out: the register starts at 0xFFFFFFFF instead of 0 (so leading zero bytes are not invisible), bits are processed least significant first, and the result is inverted at the end. With those rules, the CRC-32 of the ASCII string 123456789 is 0xCBF43926, the standard test value.

In hardware: a shift register

Nobody writes the long division out. A linear feedback shift register (LFSR) with r flip-flops does it one bit per clock tick. Each tick shifts the register by one place. The bit that falls out the top, XORed with the incoming message bit, is fed back into the positions where G has a term. After the last message bit, the register holds the CRC. This form needs no appended zeros. Software does the same thing a byte at a time with a 256-entry table, or with a CPU instruction.

Four register cells x0, x1, x2, x3 in a row. The x3 output is XORed with the incoming message bit; that feedback bit goes into x0 and is XORed in before x1. Feeding the message 1101011011 one bit at a time gives the register states 0011, 0101, 1010, 0100, 1000, 0000, 0011, 0110, 1111 and finally 1110. — Four flip-flops and two XOR gates compute the same CRC, 1110, one bit per clock tick.

Not a cryptographic hash

A CRC catches accidents, not attacks. It has no key, and it is linear: the CRC of A ⊕ B is the CRC of A XOR the CRC of B (for messages of the same length). Anyone who changes the data can recompute the CRC, or change 4 chosen bytes to make the CRC-32 come out as any value they like. The WEP Wi-Fi standard used CRC-32 as its integrity check, and attackers could flip bits in encrypted packets and fix the CRC to match. To detect deliberate changes, use a cryptographic hash in an HMAC or a digital signature (see Encryption vs Hashing). A CRC is also not an encoding: Base64 changes how bytes look so they fit in text, while a CRC only adds a few check bits after them.

See also: unlike a CRC, a cryptographic hash is non-linear; Inside AES-128 and SHA-256 shows SHA-256's rounds and how one flipped bit changes about half of the digest.

Error-correcting codes such as Hamming and Reed–Solomon can also fix the bits they find.

See also: a CRC only detects errors; Hamming Code adds parity bits whose failed checks name the flipped bit so it can be corrected.

Error-correcting codes such as Hamming and Reed-Solomon can rebuild lost data instead of only detecting damage.

What the page leaves out

The page uses messages of at most 10 bits and generators of degree 3, 4 and 8. It shows the plain textbook CRC with the register starting at 0. It leaves out the initial value, bit reflection and final XOR of real CRC-32, table-driven and slicing-by-8 software, carry-less multiplication (PCLMULQDQ) for fast CRCs, and error-correcting codes such as Hamming and Reed–Solomon that can also fix the bits they find.