AHMED ZBYR

AHMED ZBYR

Biker, EV Enthusiast

Every time an Ethernet cable delivers a web page, a Wi-Fi router receives a packet, your SSD reads a file, or you unzip a .zip archive, your computer asks one vital question:

“Did any 1s or 0s get accidentally flipped along the way?”

To answer that question in nanoseconds, almost every piece of hardware and software on Earth uses a 1961 invention by W. Wesley Peterson called a CRC (Cyclic Redundancy Check).

If you look up CRC in an engineering textbook, you are immediately hit with terms like “Galois Field GF(2) polynomial ring division.” You don’t need any of that jargon. At its core, a CRC is just long division where you keep the remainder—with one clever twist that makes it lightning-fast for computers.

In this post, we will start with a simple everyday number game and build up step-by-step until you can calculate a real binary CRC by hand.

Level 1: The Core Problem (Why Simple Addition Fails)

Imagine Alice wants to send the three-digit number 427 to Bob over a crackly walkie-talkie. How can Bob be sure he heard 427 and not 437 or 247?

Let’s look at three ways Alice and Bob could try to protect the message:

Attempt 1: The Odd/Even Check (Parity Bit)

Alice tells Bob: “The number is 427, and by the way, it’s an odd number.”

  • What it catches: If 427 gets garbled into 428 (even), Bob knows something went wrong.
  • Why it fails: If 427 gets garbled into 437 or 247, both are still odd! Bob never notices the error.

Attempt 2: Adding Up the Digits (Simple Checksum)

Alice adds the digits together (4 + 2 + 7 = 13) and sends 427 along with the sum 13.

  • What it catches: If 427 turns into 437, Bob adds 4 + 3 + 7 = 14 ≠ 13 and catches the mistake!
  • Why it still fails:
    1. Swapped Digits: What if 427 gets scrambled into 247? 2 + 4 + 7 is still 13!
    2. Canceling Errors: What if the first digit goes up by 1 and the last digit goes down by 1 (526)? 5 + 2 + 6 is still 13!

Simple addition doesn’t care about the order of the digits. We need an operation where changing or swapping any digit scrambles the result completely.

Attempt 3: The Division Remainder Trick (The Heart of CRC!)

What arithmetic operation cares deeply about the exact order of every digit? Long Division!

Suppose Alice and Bob agree beforehand on a secret prime divisor—say, 19.

  1. Alice wants to send 427.
  2. She divides 427 ÷ 19: 
    427 = (19 × 22) + 9   --> Remainder is 09
  3. Alice sends 427 along with the remainder 09.
  4. Now see what happens when errors strike on the walkie-talkie:
    • Normal arrival (427): 427 ÷ 19 gives remainder 09. Matches!
    • Single digit error (437): 437 ÷ 19 gives remainder 00 ≠ 09. Caught!
    • Swapped digits (247): 247 ÷ 19 gives remainder 00 ≠ 09. Caught!
    • Canceling digits (526): 526 ÷ 19 gives remainder 13 ≠ 09. Caught!

That is the entire big idea of a CRC:

A CRC is simply the remainder left over after dividing your data by a fixed agreed-upon number!

flowchart LR
    A["Original Data"] --> B["Divide by Agreed Key (Divisor)"]
    B --> C["Keep the Remainder (The CRC)"]
    C --> D["Send Data + CRC Together"]
    D --> E["Receiver Divides by Same Key"]
    E --> F{"Is Remainder 0?"}
    F -->|Yes| G["Data is 100% Intact!"]
    F -->|No| H["Corruption Detected -> Request Resend"]

Level 2: The Binary Twist (XOR Instead of Subtraction)

In grade-school long division, at each step you subtract to find the remainder.

However, in computer hardware, normal subtraction has a frustrating bottleneck: borrowing. If you subtract 10000000 − 00000001, the borrow ripples all the way from the rightmost bit to the leftmost bit, slowing down the circuit.

So W. Wesley Peterson asked a brilliant question: What if we do long division in binary without any borrowing at all?

Instead of normal subtraction, CRC uses XOR (Exclusive OR)—which simply asks bit-by-bit: “Are these two bits different?”

Bit A Bit B A XOR B (Are they different?)
0 0 0 (No, they are the same)
1 1 0 (No, they are the same)
1 0 1 (Yes, they are different!)
0 1 1 (Yes, they are different!)

Because XOR never borrows from the column next door, every column is completely independent. And instead of checking “Is the number bigger than the divisor?”, in XOR division you only check one thing: “Does the current slice start with a 1?” If it starts with a 1, you XOR it with your key!

Level 3: Let’s Calculate a Real Binary CRC by Hand!

Let’s walk through a real, complete 3-bit CRC example together. Once you trace these 6 steps, you will understand how every CRC on Earth works.

The Setup

  • Data Alice wants to send (6 bits): 110101
  • Agreed Divisor Key (4 bits): 1011
  • CRC Size: Always 1 bit shorter than the key (4 − 1 = 3 bits).

Step 1: Pad 3 Zeros onto the End of the Data

Because our CRC remainder will be 3 bits long, Alice temporarily attaches three zeros (000) to the end of her message 110101:

Padded Data: 110101000

Step 2: Divide 110101000 by 1011 Using XOR

At each step, look at the leftmost bit:

  • If the leftmost bit is 1, line up the key 1011 underneath and XOR them.
  • Drop the leading 0 and bring down the next bit from the message until only 3 bits remain!
Key: 1011  |  Padded Message: 1 1 0 1 0 1 0 0 0
---------------------------------------------------
Step 1:       1 1 0 1          <-- Starts with 1, so XOR with 1011
          XOR 1 0 1 1
              -------
                1 1 0 0        <-- Result is 110, bring down next bit (0)
Step 2:   XOR   1 0 1 1        <-- Starts with 1, so XOR with 1011
                -------
                  1 1 1 1      <-- Result is 111, bring down next bit (1)
Step 3:     XOR   1 0 1 1      <-- Starts with 1, so XOR with 1011
                  -------
                    1 0 0 0    <-- Result is 100, bring down next bit (0)
Step 4:       XOR   1 0 1 1    <-- Starts with 1, so XOR with 1011
                    -------
                      0 1 1 0  <-- Starts with 0! Skip XOR (or XOR with 0000)
                                   and bring down the final bit (0):
                        1 1 0 0
Step 6:           XOR   1 0 1 1 <-- Starts with 1, so XOR with 1011
                        -------
                          1 1 1 <-- 3-BIT CRC REMAINDER!

Our 3-bit CRC remainder is 111!

Step 3: Replace the 000 Padding with the CRC (111)

Alice replaces the three temporary zeros (000) at the end of her message with the CRC (111) and transmits the 9-bit frame to Bob:

Original Data : 110101
CRC Remainder :       111
-------------------------
Sent to Bob   : 110101111

Step 4: How Bob Checks the Message (The Zero-Remainder Magic!)

Why did Alice replace 000 with 111? Because in XOR arithmetic, 111 XOR 111 = 000!

When Bob receives 110101111, he runs the exact same division by 1011. Watch what happens at the very last step when no errors occurred:

Key: 1011  |  Received Frame: 1 1 0 1 0 1 1 1 1
---------------------------------------------------
              1 1 0 1
          XOR 1 0 1 1
              -------
                1 1 0 0
          XOR   1 0 1 1
                -------
                  1 1 1 1
            XOR   1 0 1 1
                  -------
                    1 0 0 1    <-- Brought down the first '1' of the CRC
              XOR   1 0 1 1
                    -------
                      0 1 0 1  <-- Starts with 0, bring down next '1' of CRC:
                        1 0 1 1
                  XOR   1 0 1 1 <-- Final step: 1011 XOR 1011!
                        -------
                          0 0 0 <-- REMAINDER IS ALL ZEROS!
  • Remainder = 000: Bob knows immediately that the message arrived cleanly!
  • What if a noisy wire flipped the 3rd bit (110101111 → 111101111)? If you run the exact same division on 111101111, the final remainder comes out to 011 (not 000)—instantly alerting Bob’s network card to discard the corrupted packet!

Level 4: Why Do Specs Write Keys as Polynomials (x³ + x + 1)?

If you ever read an Ethernet or USB specification, you won’t see the key written as 1011. Instead, you will see it written as a Generator Polynomial like:

G(x) = x³ + x + 1

Don’t let the x fool you—it is just a compact way of writing which bit positions are 1s and which are 0s!

Look at our 4-bit key 1011 from right to left (x⁰ to x³):

Bit Position x³ (8s place) x² (4s place) x¹ (2s place) x⁰ (1s place)
Our Key (1011) 1 0 1 1
Polynomial Term 1·x³ 0·x² 1·x 1

Drop the 0·x² term and you get x³ + x + 1. That’s it! When engineers talk about “CRC-32 (x³² + x²⁶ + x²³ + ⋯ + 1),” they are just listing which bits are set to 1 in a 33-bit binary divisor.

What Can a Good CRC Key Guarantee to Catch?

Mathematicians carefully pick the divisor key so that it has maximum error-catching power. For example, a standard CRC-32 check (which adds just 4 bytes to the end of a network packet) mathematically guarantees catching:

  • 100% of all single-bit errors (any 1 bit flipped anywhere in the packet).
  • 100% of all double-bit errors (any 2 bits flipped anywhere in the packet).
  • 100% of any odd number of bit flips (3, 5, 7, … bits flipped).
  • 100% of all burst errors up to 32 bits long (where a static shock or radio glitch wipes out up to 32 consecutive bits in a row).
  • 99.99999998% (1 − 2⁻³²) of all longer random noise patterns!

Level 5: Try It Yourself in 15 Lines of Python

Here is a tiny, self-contained Python script that runs our exact hand-calculated 3-bit CRC (110101 ÷ 1011) and also shows Python’s built-in industrial CRC-32:

import zlib

def simple_crc(bits: str, key: str) -> str:
    """Computes the binary XOR division remainder for any bit string."""
    crc_len = len(key) - 1
    work = list(bits + ("0" * crc_len))

    for i in range(len(bits)):
        if work[i] == "1":  # Only XOR when the leading bit is 1
            for j in range(len(key)):
                work[i + j] = "0" if work[i + j] == key[j] else "1"

    return "".join(work[-crc_len:])

# 1. Verify our hand-worked example (Data: 110101, Key: 1011)
data = "110101"
key = "1011"
crc = simple_crc(data, key)
print(f"Data: {data} | Key: {key} -> 3-bit CRC: {crc}")

# 2. Bob verifies the transmitted frame (Data + CRC = 110101111)
transmitted = data + crc
print(f"Bob's Remainder (Clean)    : {simple_crc(transmitted, key)}")

# 3. Flip bit #3 to simulate noise on the wire (110101111 -> 111101111)
corrupted = "111101111"
print(f"Bob's Remainder (Corrupted): {simple_crc(corrupted, key)}  <-- Caught!")

# 4. Real-world CRC-32 (used in Ethernet, Wi-Fi, ZIP, and PNG files)
real_crc32 = zlib.crc32(b"Hello World")
print(f"Standard CRC-32 of 'Hello World': { hex(real_crc32) }")

Output:

Data: 110101 | Key: 1011 -> 3-bit CRC: 111
Bob's Remainder (Clean)    : 000
Bob's Remainder (Corrupted): 011  <-- Caught!
Standard CRC-32 of 'Hello World': 0x4a17b156

Where CRC Is Used in the Real World (And One Important Warning!)

Standard Name Size Where You Use It Every Day
CRC-8 1 Byte (8 bits) Bluetooth headers, ATM cells, 1-Wire temperature sensors.
CRC-16 2 Bytes (16 bits) USB packets, Modbus industrial controllers, Bluetooth data payloads.
CRC-32 (IEEE 802.3) 4 Bytes (32 bits) Ethernet packets, Wi-Fi frames, .zip, .gz, and .png image files.
CRC-32C (Castagnoli) 4 Bytes (32 bits) PostgreSQL (data_checksums), iSCSI, Btrfs / ext4 filesystems. Modern Intel/AMD (SSE4.2) and ARM CPUs have a dedicated hardware instruction specifically for CRC-32C!

⚠️ Crucial Warning: CRC Is for Accidents, Not Hackers!

A very common beginner mistake in software engineering is using CRC-32 to verify that a downloaded file wasn’t tampered with by a hacker.

  • CRC (CRC-32) is designed to catch accidental physical noise (cosmic rays, scratchy cables, Wi-Fi interference). Because CRC is just linear XOR division, a hacker who modifies a file can trivially calculate which 32 bits to flip so the file produces the exact same CRC-32 remainder!
  • Cryptographic Hashes (SHA-256, BLAKE3) are designed to stop intelligent attackers, making it computationally impossible to forge a matching hash.

Use CRC when your enemy is physics; use SHA-256 when your enemy is a hacker.

References & Further Reading

  1. W. Wesley Peterson & D. T. Brown (1961): “Cyclic Codes for Error Detection”, Proceedings of the IRE, Vol. 49, Issue 1, pp. 228–235. The original paper introducing Cyclic Redundancy Checks.
  2. Ross N. Williams (1993): “A Painless Guide to CRC Error Detection Algorithms” — The classic, universally cited step-by-step developer guide to bit-by-bit and table-driven CRC implementations.
  3. Philip Koopman (Carnegie Mellon University): Best CRC Polynomials Catalog — Comprehensive research benchmarking which CRC polynomials catch the highest number of multi-bit errors across different packet lengths.

You May Also Enjoy