How CRC Works: Polynomial Division in GF(2), Step by Step

In everyday life

Have you ever downloaded a ZIP file, tried to open it, and been told "the file is corrupted"? A ZIP file stores a check value for each file inside it. The value is computed from that file's contents. The software that opens the ZIP computes the same value again. If the two values don't match, it decides the file is broken. That value is a CRC.

Data is carried and stored as rows of 0s and 1s. Along the way, a 0 can flip to a 1, or a 1 to a 0. Causes include electrical noise on a cable, weak radio signals, and particles from space striking memory (soft errors).

All of these are rare, but they can never be brought to zero. Say only one bit in a trillion goes wrong. If you send a billion bits per second, you still get an error about every 17 minutes. So the receiver needs a way to check the data.

The basic idea: attach a check value

The barcode on a product in a store usually has 13 digits. This is the EAN-13 barcode (called JAN in Japan). Its last digit is a check digit, made from the other 12 digits by a fixed calculation. The checkout scanner does the same calculation and checks that it matches the last digit. If it doesn't, the scanner reads the code again.

Compute a short value from the data and send it along. The receiver computes it again and compares. This is the basic idea behind finding errors. CRC uses the same idea; only the calculation is different.

The simplest check: parity

For a row of 0s and 1s, the simplest method is to count the 1s. You add one extra bit, 0 or 1, at the end, so that the number of 1s is even. This extra bit is called a parity bit.

For example, 1011001 has four 1s (an even number), so you add a 0 and send 10110010. If one bit flips on the way, the number of 1s becomes odd, and you notice the error.

But if two bits flip at once, the count stays even, and the error is missed. Noise often lasts for a while, so several neighboring bits tend to go bad together. Such a clump of errors is called a burst error. If an even number of bits flip, parity misses it.

A check by addition: the checksum

Another method splits the data into chunks, such as 16 bits each, adds them all up, and attaches the total. This is called a checksum. It is used in the internet's IP and TCP (RFC 1071).

But addition gives the same answer in any order. So a checksum misses errors where two chunks swap places. It also misses one chunk going up by 1 while another goes down by 1. CRC uses a cleverer calculation that also tells bit positions apart.

Where CRC is used

CRC is widely used in everyday networks and files. The number after the name is the size of the check value in bits.

Ethernet splits data into units called "frames." It adds a 4-byte (32-bit) CRC at the end of each frame. This part is called the FCS (frame check sequence).

The receiving device throws away any frame whose FCS does not match. Ethernet itself does not resend it. The missing data is resent by a mechanism called TCP. On Wi-Fi, the receiver sends a reply when a frame arrives correctly. If no reply comes back, the sender sends the frame again (see "How Does Wi-Fi Work?").

How it works 1: math with only 0 and 1, and no carries

CRC math happens in a "world of only 0 and 1," which differs a little from everyday arithmetic. Addition in this world follows just three rules.

• 0+0=0
• 0+1=1, 1+0=1
• 1+1=0 (no carry)

In ordinary binary, 1+1=10 with a carry. Here, the carry is thrown away. The rule becomes "1 if the two differ, 0 if they are the same," which is exactly XOR. It is an adder circuit (the half adder) with its carry output removed.

Subtraction follows the same rule. 0−1 means "the number that gives 0 when you add 1." Since 1+1=0, that number is 1. So in this world, subtraction and addition are both XOR. Each digit is calculated without looking at its neighbors, so the circuit is very simple.

Mathematicians call this world of only 0 and 1 GF(2). GF stands for Galois field, named after Galois, a 19th-century mathematician. For this article, just remember it as "binary math without carries."

How it works 2: reading a row of bits as a polynomial

Next, we rewrite a row of 0s and 1s as a polynomial. A polynomial is an expression that adds up powers of x, like x²+3x+1. In CRC, each digit gets a name tag, "x to some power." If the digit is 1, you write that term; if it is 0, you leave it out.

For example, the digits of 1011 are, from the left, the x³, x², x¹ and x⁰ places. So 1011 becomes x³+x+1 (x⁰ is written as 1). You never plug a number in for x. The power of x just marks where a digit sits.

Writing data as a polynomial lets us use properties of polynomials that mathematicians have long studied. Thanks to them, we can prove which kinds of errors are always caught.

The polynomial used as the divisor in CRC is called the generator polynomial. Ethernet's CRC-32 uses x³²+x²⁶+x²³+…+x+1, which has degree 32. Specifications drop the top term, x³². They write the remaining 32 digits in hexadecimal as 04C11DB7. (Hexadecimal writes each group of four binary digits as one character.)

How it works 3: finding a CRC by hand

Let's find a CRC by hand with a small example. The data to send is the 4 bits 1101. The generator polynomial is x³+x+1, that is, 1011. The divisor has 4 digits, so the remainder has 3, which gives a 3-bit CRC.

1. Append three 0s to the data, one for each CRC bit: 1101000 (this makes room for the CRC)
2. Write the divisor 1011 under the leftmost 1, lined up on the left, and XOR
3. Line up 1011 again under the leftmost 1 that remains, and XOR. Skip any 0 digits
4. Repeat until the divisor would stick out past the right end. The 3 digits left on the right are the remainder, and that is the CRC

In this example, four XORs give the remainder 001. The sender attaches this remainder after the data and sends 1101001.

Unlike ordinary long division, you never need to ask "is it bigger than the divisor?" If the leftmost digit is 1, you XOR; if it is 0, you move on to the next digit. This simplicity is why CRC is fast.

The receiver divides all 7 received bits by the same 1011. If there are no errors, the remainder is 000. That is because attaching the remainder made the whole row divide exactly. Suppose the third bit from the left flips, so 1111001 arrives. The remainder is then 110, and the error is caught.

Real standards add a few more rules. For example, Ethernet's CRC-32 starts the calculation from all 1s and flips every bit at the end. Starting from 1s lets it also catch errors that add or drop 0s at the front.

The CRC calculator also shows this division step by step. Set the variant to CRC-8, the width to 3, the generator polynomial to 3 and the data format to hex bytes. Then enter 0D. (0D is 00001101 in binary. The leading 0s do not change the remainder.)

How it works 4: computing it with a circuit

Inside a device, a small dedicated circuit computes the CRC while the data streams in. It is a chain of circuits that each remember 1 bit. At each tick of a timing signal (the clock), every bit moves one place along the chain. This circuit is called a shift register.

For a 3-bit CRC, line up three 1-bit boxes, A, B and C, and put XORs in two places. Data enters from the right, one bit at a time. At each clock tick, it moves one place to the left. The bit that spills out of C, at the left end, is wired back to the right. There it feeds into the two XORs.

Bits flip at the two XORs only when the spilled bit is 1. This is the same step as "if the leftmost digit is 1, XOR with 1011" in the hand calculation. This wiring feeds an output back toward the input. It is called a linear feedback shift register (LFSR). Feed in 1101 and then three 0s, and the contents of the boxes change like this.

The boxes end up holding 001, the same as the remainder found by hand. CRC-32 simply has 32 boxes. It also has more XORs, placed to match the terms of its generator polynomial.

Errors CRC always catches

The strength of CRC is that you can say "this kind of error is always caught." Suppose the generator polynomial has both a top term and an x⁰ term (+1). Then the following holds. Peterson and Brown showed these properties in a 1961 paper.

• An error in a single bit is always caught, wherever it happens
• A burst error no longer than the CRC is always caught, however many bits inside it flip (within 32 bits for CRC-32)
• Longer errors are almost always caught too. If every error pattern is equally likely, a 32-bit CRC misses about 1 in 4.3 billion (1 in 2 to the 32nd power)

For each data length, how many flipped bits are always caught depends on the choice of generator polynomial. In 2002, Koopman at Carnegie Mellon University checked every 32-bit generator polynomial. Ethernet's CRC-32 catches every error of up to 3 bits in a frame of the maximum length. But he also found that stronger polynomials exist.

CRC misses an error only when the error pattern (which bits flipped) divides exactly by the generator polynomial. Take the 1101001 from before. Say the 1st, 3rd and 4th bits from the left all flip. The error pattern is then 1011000. This divides exactly by 1011, so the remainder stays 000 and nobody notices. The error spans 4 bits, so it is outside what a 3-bit CRC guarantees. In practice, 16-bit or 32-bit CRCs are used.

What CRC cannot do

It cannot fix errors

CRC can tell you that an error exists. But it usually cannot tell you where. Once an error is found, there are only two options. Throw the data away and ask for it again, or report that it is broken.

To fix errors, you add more check bits, arranged so that you can tell which bit flipped. This is called an error-correcting code (ECC). The Hamming code, published by Hamming in 1950, adds 3 bits to 4 bits of data and can fix a 1-bit error. ECC memory for servers adds 8 bits to every 64 bits. It fixes 1-bit errors and detects 2-bit errors.

A code that can fix more errors is the Reed–Solomon code, published by Reed and Solomon in 1960. It is used in CDs and QR codes. That is why a QR code can still be read when part of it is dirty. Like CRC, it uses polynomial math.

Codes that fix errors need more check bits and heavier calculation. When data can be resent, it is often more efficient to find errors with a light CRC and resend. Where resending is impossible, such as broadcasting or links with space probes, codes that fix errors are used. This is called forward error correction (FEC).

It cannot spot deliberate tampering

How CRC is calculated is public in the standards, and it uses no secret key. Someone who changes the data can simply compute a new CRC and attach it. CRC catches accidental errors, not malicious changes.

This really happened. WEP, an early encryption method for wireless LAN, used CRC-32 to check the contents. In 2001, Borisov and colleagues showed how to change the contents without breaking the encryption. They could make the CRC match as well. Both WEP's encryption and CRC are computed with XOR alone. So flipping certain bits changes the CRC in a way anyone can calculate.

To detect tampering, use message authentication codes or digital signatures, which rely on secret keys (see "What Is Encryption?"). The hash functions used in cryptography are also designed so that, in practice, no one can make different data with the same value. With CRC, making such data is easy.

Parity vs checksum vs CRC vs ECC

Common misconceptions

By the numbers

Learn more

• Glossary entries: CRC (cyclic redundancy check) / parity bit / Hamming code / bit error rate (BER)
• Try the numbers: the CRC calculator / the Hamming code calculator / the bitwise operations calculator (try XOR)
• Related articles: "How Is Data Sent Over the Internet?" / "How Are Passwords Cracked?"