Error Detection: Parity, Checksums and CRCs

An error-detecting code is simply a few extra bits, computed from your data and sent along with it, so the receiver can tell whether anything got damaged on the way. The names are literal: a parity bit records whether the count of 1s is even or odd (parity means evenness), a checksum is a sum used as a check, and CRC stands for cyclic redundancy check. They're what let a network card or a car's computer reject a garbled message instead of acting on it. The CRC formula $T(x) = M(x)\,x^r + R(x)$ looks heavy, but it's three pieces: $M(x)$ (your message), $x^r$ (make room at the end for $r$ check bits) and $R(x)$ (the check bits that fill that room), chosen so the whole thing divides evenly by an agreed $G(x)$. It looks complex, but it's just long division with bits; bear with it.

Noise, cosmic rays and loose connectors flip bits. The fix is redundancy: the receiver recomputes the extra bits from the data it got, and if its answer doesn't match the ones that came along, something got damaged on the way.

XOR is addition mod 2: $1 \oplus 1 = 0$, with no carry. An even parity bit is the XOR of all the data bits, so the total number of 1s comes out even. The receiver XORs everything it got and expects 0. One flipped bit makes the count odd, so it's caught. Two flips cancel, so they're missed. In general, parity catches exactly the errors with an odd number of flipped bits.

How often does parity miss? This is where probability comes in. If each of $n$ bits flips independently with probability $p$, the number of flips is binomial. Adding the two expansions of $(q + p)^n$ and $(q - p)^n$, with $q = 1 - p$, cancels the odd terms and gives

Subtract the chance of no flips at all, $(1 - p)^n$, and what's left is the chance of an error parity can't see.

Checksums add up the bytes (mod 256, say) and send the sum. They catch more than one parity bit, but they're blind to bytes arriving in the wrong order, since addition is commutative.

CRCs: division mod 2. So what can we do that's stronger? The idea is the same as checking that a number is divisible by 9: if the sender makes the whole message a multiple of something, damage will almost always break that. Read a bit string as a polynomial with coefficients in $\{0, 1\}$: 1101 is $x^3 + x^2 + 1$. Adding is XOR, because $1 + 1 = 0$. Sender and receiver agree on a generator $G(x)$ of degree $r$. The sender appends $r$ zeros (multiplying by $x^r$), divides by $G$, and replaces the zeros with the remainder $R(x)$. Now the transmitted $T(x) = M(x)x^r + R(x)$ is a multiple of $G(x)$: subtracting the remainder from the dividend leaves a multiple, and subtracting is adding mod 2. The receiver divides by $G$ and expects remainder 0.

Write the damage as an error pattern $E(x)$, with 1s where bits flipped. The receiver sees $T + E$, and since $G$ already divides $T$, the error slips through only if $G(x)$ divides $E(x)$ too. That's what gives a CRC its guarantees:

• if $G$ has two or more terms, it never divides $x^i$, so every single-bit error is caught;
• if $x + 1$ divides $G$, every odd number of errors is caught, because $E(1) = 1$ for those while $G(1) = 0$;
• if $G$ has a constant term, every burst of errors spanning at most $r$ bits is caught.

In hardware a CRC is just a shift register with a few XOR gates (a linear-feedback shift register), so it keeps up with the wire. Ethernet frames end in a 32-bit CRC, CAN buses in cars use a 15-bit CRC, and USB uses 5- and 16-bit ones. In software it's a loop of shifts and XORs:

uint8_t crc8(const uint8_t *data, int n) {   // generator x^8 + x^2 + x + 1
    uint8_t crc = 0;
    for (int i = 0; i < n; i++) {
        crc ^= data[i];
        for (int k = 0; k < 8; k++)          // one step of long division
            crc = (crc & 0x80) ? (crc << 1) ^ 0x07 : crc << 1;
    }
    return crc;
}

Every Ethernet frame ends in a 32-bit CRC, CAN buses in cars check every frame with a 15-bit CRC, and firmware files in Intel HEX format carry a checksum on every line, so a corrupted update gets rejected instead of bricking the device.