CRC (Cyclic Redundancy Check)

Why do we need error detection?

Bits travel as electrical signals, light or radio waves, and noise can flip a 0 into a 1. A single flipped bit can turn a payment of ₹100 into ₹228. The receiver needs a cheap way to ask: did this frame arrive exactly as it was sent?

A simple parity bit (an extra bit that makes the number of 1s even) catches one flipped bit but misses two. CRC adds a few more check bits, chosen so cleverly that it catches almost every error that happens in practice. That is why every Ethernet frame, Wi-Fi packet, ZIP file and PNG image carries one.

The idea: division with XOR

Treat the bits as the coefficients of a polynomial: 1101 means x³ + x² + 1. Sender and receiver agree on a generator polynomial G of degree r.

1. Append r zeros to the data (this multiplies it by xʳ).
2. Divide by the generator using mod-2 arithmetic: subtraction is just XOR, so there are no borrows and no carries.
3. The remainder (r bits) is the CRC. Replace the appended zeros with it and send the frame.

Because the remainder was “added back”, the frame that is sent is exactly divisible by G.

Step by step: data 100100, generator 1101

The generator has degree 3, so we append 3 zeros: 100100000. Then, from the left, whenever the leading bit is 1 we XOR the generator underneath it:

Step	Leading bit	Working bits after the step
start	–	100100000
1	1 → XOR 1101	010000000
2	1 → XOR 1101	001010000
3	1 → XOR 1101	000111000
4	1 → XOR 1101	000001100
5	0 → skip	000001100
6	1 → XOR 1101	000000001

The remainder is the last 3 bits, 001. The sender transmits 100100 001.

At the receiver

The receiver divides the whole received frame by the same generator (no zeros appended this time).

• Remainder 0 → the frame is accepted.
• Remainder not 0 → an error happened. The frame is dropped and sent again.

Flip any single bit of 100100001 and the remainder is no longer zero. Try it in the 3D model.

What does CRC catch?

With a well-chosen generator of degree r, a CRC detects:

• every single-bit error,
• every burst of errors no longer than r bits,
• every odd number of flipped bits (if the generator has x + 1 as a factor),
• almost every longer burst: only about 1 in 2ʳ slips through.

With CRC-32 (r = 32), used by Ethernet, that is about one undetected burst in four billion.

Name	Generator (degree)	Used in
CRC-8	x⁸ + x² + x + 1	small sensors, ATM headers
CRC-16	x¹⁶ + x¹⁵ + x² + 1	Modbus, USB
CRC-32	degree 32	Ethernet, Wi-Fi, ZIP, PNG, gzip

Code

def crc_remainder(data: str, gen: str) -> str:
    r = len(gen) - 1
    bits = list(data + "0" * r)              # append r zeros
    for i in range(len(data)):
        if bits[i] == "1":                   # leading 1: XOR the generator
            for j, g in enumerate(gen):
                bits[i + j] = "0" if bits[i + j] == g else "1"
    return "".join(bits[-r:])

def crc_check(frame: str, gen: str) -> bool:
    r = len(gen) - 1
    bits = list(frame)
    for i in range(len(frame) - r):
        if bits[i] == "1":
            for j, g in enumerate(gen):
                bits[i + j] = "0" if bits[i + j] == g else "1"
    return "1" not in bits[-r:]              # remainder must be 0

crc = crc_remainder("100100", "1101")
print(crc)                                   # 001
print(crc_check("100100" + crc, "1101"))     # True
print(crc_check("101100001", "1101"))        # False: one bit was flipped

import zlib
print(hex(zlib.crc32(b"hello")))             # 0x3610a686, the real CRC-32

Real implementations process a whole byte at a time using a 256-entry lookup table, and many CPUs even have a CRC instruction.

CRC vs other checks

	Parity bit	Checksum (sum of words)	CRC	Hamming code
Extra bits	1	16	r (8–32)	~log₂ n
Detects	Odd number of flips	Many errors	Almost all errors	1–2 flips
Corrects	❌	❌	❌	✅ single-bit errors
Used in	Memory, serial ports	IP, TCP, UDP headers	Ethernet, Wi-Fi, files	ECC memory

Common mistakes

• Forgetting to append the r zeros at the sender, or appending them again at the receiver.
• Subtracting with borrows. In CRC arithmetic, subtraction and addition are both XOR.
• Getting the degree wrong. A generator of length 5 (like 10011) has degree 4, so the CRC has 4 bits.
• XORing when the leading bit is 0. Then you “subtract” zero and simply move one place right.