CRC Step by Step
Binary long division with XOR instead of subtraction — and why the remainder catches every burst error.
Skip to the animationA cyclic redundancy check treats a frame as a binary polynomial, divides it by an agreed generator, and sends the remainder — so the receiver can detect corruption by checking the result divides exactly.
The procedure
- 1Agree a generator of n bits. The checksum will be n − 1 bits.
- 2Append n − 1 zeros to the message, reserving room for it.
- 3Divide by the generator using XOR instead of subtraction — no carries, no borrows.
- 4The remainder is the CRC. Replace the appended zeros with it.
- 5The receiver divides the whole received frame by the same generator. Remainder zero means no error detected.
The transmitted frame is exactly divisible by the generator by construction. That is why the receiver's test is so cheap — it never computes what the checksum should have been, it just checks divisibility.
The vocabulary
- Protocol data unit
- What the thing is called at each layer: segment at transport, packet at network, frame at link. Different names for the same bytes with different amounts of header wrapped round them.
- Encapsulation
- A layer treats everything it receives from above as opaque payload and prepends its own header. It never looks inside, which is precisely what makes layers replaceable.
- Peer layers
- A layer only ever meaningfully talks to the same layer at the other end. TCP at one end reads the header TCP at the other end wrote, and nothing in between touches it.
- Propagation vs transmission delay
- Propagation is how long a bit takes to travel the distance — set by physics. Transmission is how long it takes to push all the bits out — set by bandwidth. Only the second improves when you buy a faster link.
- Round-trip time (RTT)
- Send to reply. Every acknowledgement-based protocol is ultimately paced by this, which is why the interesting question is always how much you can send before one arrives.
What it guarantees
A well-chosen generator gives guarantees rather than probabilities:
- All single-bit errors.
- All double-bit errors, for a suitable generator.
- All errors affecting an odd number of bits — obtained by making
x + 1a factor of the generator. - All burst errors shorter than the checksum. Longer bursts slip through with probability about 2⁻ⁿ.
Bursts are what actually happen. Interference corrupts a run of adjacent bits rather than scattered ones, so catching every burst up to 32 bits is worth far more than the raw error count suggests.
Why it beat the alternatives
| Scheme | Detects | Cost |
|---|---|---|
| Parity bit | any odd number of bit errors | one bit |
| Internet checksum | most errors; misses some reorderings | 16 bits, easy in software |
| CRC-32 | all bursts ≤ 32 bits, and more | 32 bits, trivial in hardware |
The hardware is a shift register with XOR taps at the generator's 1 bits — a handful of gates processing one bit per clock. Strong guarantees plus nearly free implementation is why CRC-32 is in Ethernet, Wi-Fi, and almost every storage format.
CRC detects errors; it does not correct them. A bad frame is discarded, and recovery is the retransmission protocol's job. Error-correcting codes such as Hamming are a different trade, spending far more bits to avoid the retransmission.
The numbers you will be asked for
- Checksum length
generator bits − 1
A 33-bit generator polynomial gives the 32-bit CRC-32.
- Transmitted frame
(message × 2ⁿ⁻¹) + remainder
Shift left by appending zeros, then fill them with the remainder. The result divides exactly.
- Undetected error probability
≈ 2⁻ⁿ
For a random long burst, with an n-bit CRC. About 1 in 4 billion for CRC-32.
Advantages and disadvantages
Advantages
- Detects all burst errors shorter than the checksum — the errors that actually occur.
- A shift register and a few XOR gates; one bit per clock cycle.
- Far stronger than a parity bit or a simple checksum for the same effort.
Disadvantages
- Detection only — a corrupted frame must be retransmitted.
- Not a cryptographic hash; an attacker can trivially forge data with a matching CRC.
- The guarantee depends entirely on choosing a good generator polynomial.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.