Detecting errors: parity, checksums and CRC

Electrical noise, radio interference and bad cables flip bits. The receiver cannot see the original, so the sender adds a few check bits computed from the data. The receiver computes them again: if they differ, the data was damaged and is thrown away (TCP then sends it again, as the Reliable delivery lesson shows).

Parity

The simplest check: one extra bit that makes the number of 1s even. It catches any single flipped bit, but two flips cancel out and go unnoticed.

The Internet checksum

IP, UDP and TCP headers carry a 16-bit checksum. Add up the data as 16-bit numbers; whenever a sum overflows 16 bits, wrap the carry around and add it back (one's complement addition). The checksum is the sum with every bit flipped. The receiver adds everything, checksum included, and must get all ones.

words = [0x4500, 0x0073, 0x0000, 0x4000, 0x4011, 0xC0A8, 0x0001, 0xC0A8, 0x00C7]

total = 0
for w in words:
    total += w
    if total > 0xFFFF:                 # a carry out of 16 bits...
        total = (total & 0xFFFF) + 1   # ...wraps around
checksum = total ^ 0xFFFF              # flip every bit
print("sum:", hex(total))
print("checksum:", hex(checksum))

check = total + checksum               # what the receiver computes
print("receiver gets all ones:", check == 0xFFFF)

It is cheap to compute in software, but weak: swapping two 16-bit words gives the same sum.

CRC: cyclic redundancy check

Ethernet, Wi-Fi, ZIP files and PNG images use a CRC. Sender and receiver agree on a generator, a bit pattern such as 10011. The sender appends zeros to the data and divides by the generator using XOR instead of subtraction (division "mod 2"); the remainder is the check value, sent after the data.

def remainder(bits, gen):
    bits = list(bits)
    for i in range(len(bits) - len(gen) + 1):
        if bits[i] == "1":                      # divide: XOR the generator in
            for j in range(len(gen)):
                bits[i + j] = "0" if bits[i + j] == gen[j] else "1"
    return "".join(bits[-(len(gen) - 1):])

data, gen = "1101011011", "10011"
r = remainder(data + "0000", gen)               # append r = 4 zeros
print("remainder:", r)
print("sent:", data + r)
print("receiver's remainder:", remainder(data + r, gen))

The receiver divides what arrived (the data followed by the remainder) by the same generator. A remainder of all zeros means no error was found.

With a well-chosen generator of r + 1 bits, a CRC catches every single error, every burst of errors up to r bits long, and almost everything else. Ethernet's CRC-32 is computed by the network card's hardware for every frame.

Mark lesson complete