A wire is not a promise. When your network card pushes a frame onto a copper pair, a fibre, or a burst of radio, it is really just wiggling a physical quantity — a voltage, a light level, an electromagnetic field — and hoping the far end reads the same wiggles back. But the physical world is noisy. A nearby motor spikes the voltage, a splice reflects the light, a microwave oven splashes energy across the 2.4 GHz band, a cosmic ray clips a sample. The receiver samples at the wrong instant and reads a 1 where you sent a 0. The bit has flipped, and nothing about the bit itself announces that it is now wrong.

The link layer's job is to hand the layer above it frames it can trust, so it must somehow notice when the wire has lied. It cannot re-examine the physics — by the time the bytes arrive, the noise is long gone. Its only tool is redundancy: send a few extra bits, computed from the data, so that a corrupted frame becomes arithmetically inconsistent and gives itself away. This page walks up three rungs of that ladder — parity, the Internet checksum, and the cyclic redundancy check (CRC) — each one catching errors the rung below it lets slip.

Rung 1 — parity: one bit of conscience

The cheapest scheme adds a single parity bit. Count the 1s in your data; set the parity bit so the total number of 1s is even (that is even parity; odd parity is the mirror image). The receiver recounts. If the parity no longer matches, at least one bit flipped in flight.

For the byte 1011001 there are four 1s — already even — so the even-parity bit is 0, and we transmit 10110010. Flip any single bit and the count becomes odd; the receiver notices. But flip two bits and the count is even again — the error is invisible. Single parity detects all odd numbers of bit errors and misses all even numbers, and it can never tell you which bit was wrong. It is a smoke alarm with no map.

Two-dimensional parity is a clever upgrade. Lay the data out as a grid of rows and columns, and compute a parity bit for every row and every column. Now a single flipped bit breaks the parity of exactly one row and exactly one column — their intersection pinpoints the culprit, and you can correct it by flipping it back. This is the germinal idea behind error-correcting codes: enough structured redundancy to locate a fault, not merely sense it.

Rung 2 — the Internet checksum: add it all up

Parity treats the frame as a bag of bits. The Internet checksum — used by IP, UDP and TCP — instead treats it as a sequence of numbers and adds them together. Chop the data into 16-bit words, sum them using one's-complement arithmetic (any carry out of the top bit is wrapped around and added back into the bottom), then send the complement (bitwise NOT) of that running sum as the checksum field.

The magic is at the receiver: it adds up all the words including the checksum. If nothing was corrupted, the data sum and its own complement cancel, and the result is a word of all ones — \texttt{0xFFFF}. Any other result means the frame is damaged. In symbols, with words w_1,\dots,w_n and checksum c=\overline{\bigoplus_{i} w_i} (⊕ here being the wrap-around one's-complement sum), a clean frame satisfies:

Why one's complement and not an ordinary sum? Because it is endian-agnostic and can be computed incrementally, but mostly because it is fast and simple — it was designed in an era when every router cycle counted, and it can be updated as a packet's header fields change hop by hop without recomputing from scratch. The trade is bluntness: it is far weaker than a CRC, as we are about to see.

Run it: the intact frame folds to \texttt{0xFFFF}, and a single flipped bit breaks it. But the checksum has a soft underbelly — swap two 16-bit words and the sum is identical, because addition doesn't care about order. Reordering, and certain paired errors that cancel, sail straight through. That is the price of cheapness.

Rung 3 — CRC: division, not addition

The cyclic redundancy check is the workhorse of the link layer — Ethernet, Wi-Fi, disk sectors, ZIP files, and countless buses all lean on it. Its trick is to stop adding and start dividing. Interpret a string of bits as the coefficients of a polynomial over the finite field \mathrm{GF}(2) — the integers mod 2, where the only elements are 0 and 1 and, crucially, addition and subtraction are both just XOR (no carries, ever). The bitstring 1101 is the polynomial x^3 + x^2 + 1.

Sender and receiver agree on a fixed generator polynomial G(x) of degree r. To protect a message M(x), you append r zero bits (i.e. form x^r M(x)), divide by G(x) using polynomial long division in \mathrm{GF}(2), and keep the remainder R(x). Those r remainder bits are the CRC. What you actually transmit is x^r M(x) - R(x), which — because subtraction is XOR — is exactly the message with the CRC bits filling the zeros you appended:

By construction T(x) is exactly divisible by G(x). So the receiver simply divides the whole received frame by G(x): a zero remainder means intact, and any non-zero remainder means the frame was mangled. No addition tables, no wrap-around — just repeated XOR-and-shift.

Notice the receiver runs the same division routine on the whole frame; the intact case yields all zeros, the corrupted case does not. This is the entire algorithm — a shift register that XORs in the generator whenever a 1 falls off the top, which is why CRCs are trivial to build in hardware and run at line rate.

Why CRC catches every burst up to its degree

CRCs earn their keep because real link errors are rarely lonely single bits — noise comes in bursts, a contiguous run of corrupted bits from a scratch, a spark, or a fade. A CRC with a well-chosen degree-r generator gives a guarantee here, not a probability.

An error is a pattern E(x) XOR-ed onto the frame; the receiver misses it only if E(x) is divisible by G(x). A burst of length L is E(x) = x^k \cdot B(x), where B(x) has degree L-1 and the leading factor x^k just shifts it into place. If G(x) has a non-zero constant term, it shares no factor of x, so it can only divide B(x) — but when L \le r, B(x) has lower degree than G(x) and cannot be a multiple of it (except the all-zero non-error). Hence:

That is a remarkable amount of protection for r extra bits, and it is why the choice of generator polynomial is a small branch of engineering folklore. Ethernet's CRC-32, CRC-16 in many buses, and CRC-8 in tiny sensors are all published, hard-won constants selected for exactly these divisibility properties.

Putting the three side by side

The pattern up the ladder is: spend a few more redundant bits and a little more arithmetic, and buy a much stronger guarantee. The link layer picks the rung that matches the medium — a pristine fibre needs less than a fading radio link — but on modern Ethernet and Wi-Fi, the choice is overwhelmingly CRC.