Visual walkthrough — Data link layer — framing, error detection (CRC computation), MAC
We use the running numbers from the parent: message , generator .
Step 0 — What is a "bit string as a polynomial"?
WHAT. Before any division, we must agree on the trick that makes it all work: a string of bits is secretly a polynomial.
WHY this tool and not plain numbers? A plain binary number carries carries when you add (e.g. ). Carries ripple and make the algebra messy. If instead we treat each bit as the coefficient of a power of , then "adding" two bit strings never carries — each power of lives in its own lane. That clean, carry-free world is exactly what lets us reason about which errors survive. (This is the world of Polynomials over GF(2).)
PICTURE. Each slot of the bit string is a bucket labelled by a power of . The bit is just "is this bucket full (1) or empty (0)?"
Step 1 — What "addition" means here: XOR, no carries
WHAT. We define the only arithmetic CRC uses. Coefficients are bits, and .
WHY. We want a system where adding a thing to itself gives zero — because that self-cancellation is the entire punchline of Step 5. The system where is called ("the field with two elements"). In it, addition and subtraction are the same operation, and that operation is exactly the logic gate XOR (1 if the bits differ, 0 if they match).
PICTURE. Two rows of buckets XOR'd column by column: matching buckets empty out, differing buckets fill.
Step 2 — Name the players: , ,
WHAT. We fix precise names so no symbol appears unexplained later.
WHY. Every later equation is a story about these four objects — the message, the generator, the generator's degree, and the empty slots we will reserve.
PICTURE. A cast list: the message strip (length ), the generator strip (length ), and the degree measured as "how many buckets does span, minus one."
Step 3 — "Make room": multiply by (append zeros)
WHAT. We shift the message left by places, i.e. we tack zeros onto the end: .
WHY this exact tool? We need empty low-order slots to hold the check bits we haven't computed yet. Multiplying a polynomial by raises every power by — geometrically, it slides every full bucket places to the left, freeing up buckets on the right. That is precisely "reserve space for the remainder."
PICTURE. The message buckets slide left; fresh empty buckets open on the right (highlighted in red).
Step 4 — Divide by using XOR long division
WHAT. We do polynomial long division of by , but every "subtract" is an XOR. We get a quotient and a remainder with .
WHY division? Division is the only operation that answers the question "what is the smallest thing I can add to to make it a multiple of ?" The remainder is literally the gap between and the nearest lower multiple of . Find that gap and you know what to add.
HOW each step reads (the rule). Look at the current leading bit:
- Leading bit
1→ the number is "big enough," so XOR underneath and cross off the top bit. - Leading bit
0→ too small to subtract , so we write a0in the quotient and just bring the next bit down.
PICTURE. The full division ladder from the parent, drawn so each XOR row lines up under the bit it cancels.
Step 5 — Append and watch it cancel itself (the punchline)
WHAT. We drop into the reserved slots: transmitted frame .
WHY it becomes divisible — the self-cancellation. From Step 4, . The transmitted frame is Substitute the division result: So is exactly — a clean multiple, remainder . The magic isn't magic: appending fills the very gap the division measured, and in adding a second time erases it.
PICTURE. Two copies of the red remainder stack in the same slots and XOR to all-zeros; what's left, , is a perfect stack of -blocks.
Step 6 — The receiver's side (and the edge case )
WHAT. The receiver divides the whole received frame by and reads the remainder.
WHY. By Step 5 a clean frame gives remainder . Any error pattern turns the received frame into , whose remainder is . So:
- remainder → accept (no detectable error);
- remainder → definite error; discard/retransmit (CRC detects, it does not repair — repair is the job of a Hamming Code).
Degenerate case — what if came out already? Then was already a multiple of ; we append 000 and transmit . Nothing breaks — appending the zero remainder is consistent with the same formula with . The reserved slots still exist; they just happen to hold zeros.
PICTURE. Two receivers side by side: clean frame → remainder 000 → green check; one flipped bit → remainder ≠000 → red cross.
The one-picture summary
The whole derivation on one strip: shift (open slots) → divide (measure the gap ) → append () → the second copy of from cancels it → remainder .
Recall Feynman retelling (explain the whole walkthrough to a 12-year-old)
Think of your message as a row of coins on a shelf. First you slide all the coins a few spaces left to open some empty slots on the right — that's multiplying by . Then you play a subtraction game called division: keep XOR-ing the generator pattern under the leftmost coin until you can't anymore. Whatever tiny leftover you're stuck with is the remainder — the exact gap between your number and the nearest neat multiple of . Now the clever bit: you drop that same leftover into the empty slots. Since in this world adding the same thing twice makes it vanish (), the leftover in the division and the leftover you added cancel each other, and what remains is a perfect stack of -blocks — divisible with nothing left over. The receiver just redoes the division: leftover zero means "looks clean," any leftover means "a coin got bumped in transit."