Parity, checksums and Hamming codes

Noise on a link flips bits, and the receiver cannot see which ones. Every error-detecting code answers the same way: the sender adds a few redundant bits computed from the data, so that most damage leaves the data and those bits disagreeing. A parity bit makes the number of 1s even. A checksum adds the data up, and the 16-bit Internet checksum that IPv4, UDP and TCP use adds it in 16-bit words. A Hamming code adds several parity bits arranged so that the receiver can tell which bit flipped, and flip it back. This lesson builds all four in Python, measures which errors each one misses by trying every error pattern, and shows the rule, minimum Hamming distance, that says in advance how many errors a code can detect and how many it can correct.

Parity: one bit that counts the 1s

With even parity, the sender adds one bit chosen so that the total number of 1s is even; the receiver counts the 1s again and rejects the data if the count is odd. (Odd parity, the same idea with an odd count, is also used.) One flipped bit makes the count odd, and so does any odd number of flipped bits. Two flipped bits, or any even number, leave it even:

"""One even-parity bit on the 7-bit code of the letter K: one flipped bit is caught, two are not."""


def even_parity(bits):
    """The bit that makes the number of 1s even."""
    return sum(bits) % 2


k = [1, 0, 0, 1, 0, 1, 1]  # "K" is 1001011: four 1s, so its parity bit is 0
sent = k + [even_parity(k)]
one_flip = sent.copy()
one_flip[2] ^= 1
two_flips = one_flip.copy()
two_flips[5] ^= 1
for name, word in [("sent", sent), ("one bit flipped", one_flip), ("two bits flipped", two_flips)]:
    print(f"{name:17} {''.join(map(str, word))}  parity check {'passes' if sum(word) % 2 == 0 else 'FAILS'}")

sent              10010110  parity check passes
one bit flipped   10110110  parity check FAILS
two bits flipped  10110010  parity check passes

The 7-bit code of the letter K gets its parity bit, and of the two damaged copies, the one with one flipped bit is caught and the one with two is not. Among all the ways a block of bits can be damaged, about half flip an even number of bits, so a parity bit lets about half of all damaged blocks through. That is acceptable only where errors are rare and come one at a time, and it is why parity alone protects so little on a network link.

Two-dimensional parity: rows and columns

Arrange the data in a block, add a parity bit to every row and a parity bit to every column (a last bit, in the corner, checks the parity bits themselves), and a single flipped bit makes exactly one row and one column fail. The receiver flips the bit where they cross:

"""Two-dimensional parity on a 4 x 4 block of bits: find and fix one flipped bit, then try every 1- to 4-bit error."""
from itertools import combinations


def even_parity(bits):
    return sum(bits) % 2


def add_parity(rows):
    """Append a parity bit to each row, then a row of column parities (its last bit checks both)."""
    rows = [r + [even_parity(r)] for r in rows]
    return rows + [[even_parity(col) for col in zip(*rows)]]


def failing(block):
    """The rows and the columns whose parity no longer checks."""
    bad_rows = [i for i, r in enumerate(block) if sum(r) % 2]
    bad_cols = [j for j, c in enumerate(zip(*block)) if sum(c) % 2]
    return bad_rows, bad_cols


data = [[1, 0, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]]
block = add_parity(data)
print("block with parity:", ["".join(map(str, r)) for r in block])
block[1][2] ^= 1  # one bit of the data is hit by noise
rows, cols = failing(block)
print("one flip: rows", rows, "and columns", cols, "fail, so the bad bit is", (rows[0], cols[0]))
block[rows[0]][cols[0]] ^= 1  # flip it back: corrected
block[0][0] ^= 1
block[0][3] ^= 1  # two flips in one row
rows, cols = failing(block)
print("two flips in one row: rows", rows, "and columns", cols, "fail: detected, but not located")
block[0][0] ^= 1
block[0][3] ^= 1

# Every pattern of 1 to 4 flipped bits among the 25 bits, and how many of them the checks miss.
cells = [(i, j) for i in range(5) for j in range(5)]
print()
for n in range(1, 5):
    missed = total = 0
    for flips in combinations(cells, n):
        for i, j in flips:
            block[i][j] ^= 1
        total += 1
        missed += failing(block) == ([], [])
        for i, j in flips:
            block[i][j] ^= 1
    print(f"{n} bit{'s' if n > 1 else ' '} flipped: {total:6,} patterns, {missed:3} undetected")

block with parity: ['10111', '01100', '11011', '00101', '00101']
one flip: rows [1] and columns [2] fail, so the bad bit is (1, 2)
two flips in one row: rows [] and columns [0, 3] fail: detected, but not located

1 bit  flipped:     25 patterns,   0 undetected
2 bits flipped:    300 patterns,   0 undetected
3 bits flipped:  2,300 patterns,   0 undetected
4 bits flipped: 12,650 patterns, 100 undetected

The program finds the flipped bit of the diagram from the failing row and column, flips it back, and then shows what two-dimensional parity cannot do. Two flips in the same row leave that row’s parity even, but two columns fail: the error is detected but cannot be located. And the program tried every one of the 15,275 patterns of one to four flipped bits among the 25 bits: all 2,625 patterns of one, two or three flips were detected, and only 100 of the 12,650 four-bit patterns got through. Those 100 are the corners of rectangles: two flips in each of two rows, in the same two columns, keep every row and every column even. Choose 2 rows of 5 and 2 columns of 5 and you get 10 × 10 = 100.

The cost is 9 parity bits for 16 data bits. Two-dimensional parity shows the idea behind error correction (enough independent checks pin a bad bit down), but it pays far more redundant bits for each corrected bit than the codes below.

Hamming distance: how many errors a code can handle

The Hamming distance between two words of the same length is the number of positions in which they differ: 0110011 and 0100011 are at distance 1, while 0110011 and 1110000 are at distance 3. A code is a set of allowed words, its codewords, and its minimum distance d is the smallest distance between any two of them. From d alone you can read off what the code can do:

The reasoning, which Richard Hamming set out in 1950, is short. Fewer than d flips can never turn one codeword into another, so the damage always shows. And if at most t bits flip with 2t + 1 ≤ d, the received word is still closer to the codeword that was sent than to any other, so the receiver can correct it by choosing the nearest codeword. The program below finds d for three small codes by comparing every pair of codewords:

"""Minimum Hamming distance of three small codes, found by comparing every pair of codewords."""
from itertools import combinations, product


def distance(a, b):
    """How many positions two words of the same length differ in."""
    return sum(x != y for x, y in zip(a, b))


def hamming74(d1, d2, d3, d4):
    """Hamming(7,4): positions 1 to 7 hold p1 p2 d1 p4 d2 d3 d4, with even parity."""
    return (d1 ^ d2 ^ d4, d1 ^ d3 ^ d4, d1, d2 ^ d3 ^ d4, d2, d3, d4)


codes = {
    "3 data bits + 1 parity bit": [bits + (sum(bits) % 2,) for bits in product((0, 1), repeat=3)],
    "1 bit sent three times": [(b, b, b) for b in (0, 1)],
    "Hamming(7,4)": [hamming74(*bits) for bits in product((0, 1), repeat=4)],
}
print("0110011 vs 0100011:", distance("0110011", "0100011"))
print("0110011 vs 1110000:", distance("0110011", "1110000"))
print()
for name, code in codes.items():
    d = min(distance(a, b) for a, b in combinations(code, 2))
    print(f"{name}: {len(code)} codewords, minimum distance {d}: detects {d - 1}, corrects {(d - 1) // 2}")

0110011 vs 0100011: 1
0110011 vs 1110000: 3

3 data bits + 1 parity bit: 8 codewords, minimum distance 2: detects 1, corrects 0
1 bit sent three times: 2 codewords, minimum distance 3: detects 2, corrects 1
Hamming(7,4): 16 codewords, minimum distance 3: detects 2, corrects 1

A parity bit gives d = 2: it detects one error and corrects none. Sending each bit three times gives d = 3 and lets the receiver take a majority vote, at the cost of three bits for every data bit. Hamming(7,4) also reaches d = 3, with only 3 check bits for every 4 data bits. Two-dimensional parity from the section above has d = 4, which is why its smallest undetected errors had four flipped bits; it detects three and corrects one.

Detecting and correcting compete for the same distance. A code with d = 3 can either correct one error, or detect up to two, but not both at once: a receiver that corrects every single-bit error will silently “correct” a two-bit error into the wrong codeword, as the next section shows.

Hamming(7,4): parity bits that point at the error

Hamming’s construction numbers the positions of a codeword from 1 and puts check bits at the positions that are powers of two, 1, 2 and 4; the data bits fill positions 3, 5, 6 and 7. Each check bit gives even parity over the positions whose number has its bit set in binary. In the table, the last three columns say whether p1, p2 or p4 checks each position:

The receiver repeats the three checks. Each failing check contributes its own weight, 1, 2 or 4, and the sum, called the syndrome, is the position of the flipped bit: a bit at position 6 (binary 110) is covered by p2 and p4, so exactly those two checks fail and 2 + 4 = 6. An equivalent shortcut is to XOR together the position numbers of all the 1s in the word, which gives 0 for a correct codeword.

"""Hamming(7,4): encode 4 data bits, flip each of the 7 bits in turn, and let the syndrome point at it."""


def encode(data):
    """'1011' -> '0110011': positions 1 to 7 are p1 p2 d1 p4 d2 d3 d4, with even parity."""
    d1, d2, d3, d4 = (int(c) for c in data)
    p1 = d1 ^ d2 ^ d4  # checks positions 1, 3, 5, 7 (bit value 1 set in the position number)
    p2 = d1 ^ d3 ^ d4  # checks positions 2, 3, 6, 7 (bit value 2 set)
    p4 = d2 ^ d3 ^ d4  # checks positions 4, 5, 6, 7 (bit value 4 set)
    return "".join(map(str, (p1, p2, d1, p4, d2, d3, d4)))


def syndrome(word):
    """The position (1 to 7) of a single flipped bit, or 0 when every check passes."""
    s = 0
    for position in range(1, 8):
        if word[position - 1] == "1":
            s ^= position  # the XOR of the positions of all 1s
    return s


def decode(word):
    """Correct up to one flipped bit, then return the 4 data bits."""
    s = syndrome(word)
    if s:
        bits = list(word)
        bits[s - 1] = "1" if bits[s - 1] == "0" else "0"
        word = "".join(bits)
    return word[2] + word[4] + word[5] + word[6]


def flip(word, *positions):
    bits = list(word)
    for p in positions:
        bits[p - 1] = "1" if bits[p - 1] == "0" else "0"
    return "".join(bits)


sent = encode("1011")
print("data 1011 is sent as", sent, "with syndrome", syndrome(sent))
for p in range(1, 8):
    received = flip(sent, p)
    print(f"bit {p} flipped: {received}  syndrome {syndrome(received)} ({syndrome(received):03b})  decoded {decode(received)}")

two = flip(sent, 2, 6)
print(f"\nbits 2 and 6 flipped: {two}  syndrome {syndrome(two)}  decoded {decode(two)}  (wrong: two errors look like one)")

data 1011 is sent as 0110011 with syndrome 0
bit 1 flipped: 1110011  syndrome 1 (001)  decoded 1011
bit 2 flipped: 0010011  syndrome 2 (010)  decoded 1011
bit 3 flipped: 0100011  syndrome 3 (011)  decoded 1011
bit 4 flipped: 0111011  syndrome 4 (100)  decoded 1011
bit 5 flipped: 0110111  syndrome 5 (101)  decoded 1011
bit 6 flipped: 0110001  syndrome 6 (110)  decoded 1011
bit 7 flipped: 0110010  syndrome 7 (111)  decoded 1011

bits 2 and 6 flipped: 0010001  syndrome 4  decoded 1001  (wrong: two errors look like one)

Every single flip produced its own position as the syndrome, and every one was corrected back to the data 1011. The last line is the warning from the previous section: flipping bits 2 and 6 gives the syndrome 2 XOR 6 = 4, so the decoder flips a third bit and returns 1001, wrong and without complaint.

The construction grows: r check bits can point at any of $2^r - 1$ positions, so they protect up to $2^r - r - 1$ data bits, which gives Hamming(15,11) and Hamming(31,26). Adding one more parity bit over the whole word raises the minimum distance to 4, which lets a receiver correct any single error and still detect any double one.

The Internet checksum

IPv4, UDP and TCP do not use parity: they use the Internet checksum of RFC 1071, which treats the data as 16-bit numbers and adds them up in ones’ complement arithmetic:

1. Pair the bytes into 16-bit words, most significant byte first; an odd number of bytes gets one zero byte at the end.
2. Add the words. Whenever a sum overflows 16 bits, add the carry back in at the bottom (the end-around carry).
3. The checksum is the complement of the sum: every bit flipped.

For the IPv4 header, the checksum field is set to zero while the sender computes it (RFC 791). The receiver adds up every word of the header including the checksum, and a header that arrived intact sums to 0xFFFF.

"""The 16-bit Internet checksum (RFC 1071) of an IPv4 header, checked, then updated after a router lowers the TTL."""

# A 20-byte IPv4 header with the checksum field (bytes 10 and 11) set to zero. Addresses from the
# documentation ranges of RFC 5737: 192.0.2.10 to 198.51.100.20, TTL 64, protocol 6 (TCP).
header = bytearray.fromhex("4500 003c 1c46 4000 4006 0000 c000 020a c633 6414")


def add(*words):
    """Ones' complement addition: a carry out of the top bit is added back at the bottom (end-around carry)."""
    total = 0
    for w in words:
        total += w
        total = (total & 0xFFFF) + (total >> 16)
    return total


def words_of(data):
    """The data as 16-bit words; an odd length is padded with one zero byte."""
    if len(data) % 2:
        data = bytes(data) + b"\x00"
    return [data[i] << 8 | data[i + 1] for i in range(0, len(data), 2)]


def internet_checksum(data):
    """The complement of the ones' complement sum of the data's 16-bit words."""
    return ~add(*words_of(data)) & 0xFFFF


print("words:   ", " ".join(f"{w:04x}" for w in words_of(header)))
print(f"sum:      {add(*words_of(header)):04x}")
checksum = internet_checksum(header)
print(f"checksum: {checksum:04x}")
header[10:12] = checksum.to_bytes(2, "big")
print(f"receiver: the sum of all ten words, checksum included, is {add(*words_of(header)):04x}")

# A router forwards the packet: TTL 64 becomes 63, so the word 4006 becomes 3f06.
old_word = header[8] << 8 | header[9]
header[8] -= 1
new_word = header[8] << 8 | header[9]
hc = header[10] << 8 | header[11]
incremental = ~add(~hc & 0xFFFF, ~old_word & 0xFFFF, new_word) & 0xFFFF  # RFC 1624, equation 3
header[10:12] = b"\x00\x00"
print()
print(f"after the TTL change: incremental {incremental:04x}, recomputed {internet_checksum(header):04x}")

# RFC 1624's own example: the other fields sum to CD7A and one field changes from 5555 to 3285.
c, m, m_new = 0xCD7A, 0x5555, 0x3285
hc = ~add(c, m) & 0xFFFF
print()
print(f"old checksum {hc:04x}, recomputed after the change {~add(c, m_new) & 0xFFFF:04x}")
print(f"RFC 1141 shortcut, HC + m + ~m':   {add(hc, m, ~m_new & 0xFFFF):04x}")
print(f"RFC 1624 equation 3, ~(~HC + ~m + m'): {~add(~hc & 0xFFFF, ~m & 0xFFFF, m_new) & 0xFFFF:04x}")

words:    4500 003c 1c46 4000 4006 0000 c000 020a c633 6414
sum:      cddb
checksum: 3224
receiver: the sum of all ten words, checksum included, is ffff

after the TTL change: incremental 3324, recomputed 3324

old checksum dd2f, recomputed after the change 0000
RFC 1141 shortcut, HC + m + ~m':   ffff
RFC 1624 equation 3, ~(~HC + ~m + m'): 0000

The header’s ten words sum to 0xCDDB, so the checksum is 0x3224, and the receiver’s sum over all ten words comes out at 0xFFFF. That is no coincidence: adding any number to its own complement sets every bit, and in ones’ complement arithmetic 0xFFFF is a second way of writing zero.

Updating the checksum after a change

The IPv4 checksum covers only the header, and RFC 791 has every router recompute it, because the router changes a field: it lowers the time to live (TTL) by one. Rather than sum the whole header again, a router can update the checksum from the change alone. RFC 1624 gives the formula, with HC the old checksum, m the old 16-bit word and m′ the new one, and ~ the complement:

In the run, the TTL went from 64 to 63, so the word 0x4006 became 0x3F06, and the incremental update and the full recomputation both gave 0x3324. The last three lines replay RFC 1624’s own example of why the formula is written this way. The older shortcut of RFC 1141, HC + m + ~m′, gives 0xFFFF where the correct checksum is 0x0000. Both mean zero to a receiver that sums the whole header and compares the total with 0xFFFF, as RFC 1071 recommends, but an implementation that recomputes the checksum and compares it with the field rejects a good packet.

IPv6 dropped the header checksum altogether. RFC 8200 makes the UDP checksum compulsory instead (in IPv4 it is optional) and notes that the fields of the IPv6 header are “not covered by an internet-layer checksum”: the link’s CRC protects each hop, and the transport checksum, which also covers the addresses, protects the whole path. Routers no longer have a checksum to update at all.

What the checksum cannot see

The Internet checksum is cheap: one addition per 16-bit word, in any order. RFC 1071 lists that order independence as a feature, because it lets implementations add words in parallel or in whichever byte order the computer uses. It is also the checksum’s weakness:

"""What the Internet checksum cannot see: words in another order, and some pairs of flipped bits."""
from itertools import combinations

# The header of internet_checksum.py, with its checksum 3224 filled in.
header = bytes.fromhex("4500 003c 1c46 4000 4006 3224 c000 020a c633 6414")


def add(*words):
    total = 0
    for w in words:
        total += w
        total = (total & 0xFFFF) + (total >> 16)
    return total


def passes(data):
    """The receiver's test: the ones' complement sum of every word, checksum included, is FFFF."""
    return add(*(data[i] << 8 | data[i + 1] for i in range(0, len(data), 2))) == 0xFFFF


def flip(data, *positions):
    """A copy of the data with the given bits flipped (bit 0 is the first bit sent)."""
    out = bytearray(data)
    for p in positions:
        out[p // 8] ^= 0x80 >> (p % 8)
    return bytes(out)


print("as sent:", passes(header))
swapped = header[:12] + header[16:20] + header[12:16]  # source and destination addresses trade places
print("addresses swapped:", passes(swapped))

bits = len(header) * 8
singles = [p for p in range(bits) if passes(flip(header, p))]
print(f"\n{bits} single-bit errors, undetected: {len(singles)}")

pairs = list(combinations(range(bits), 2))
missed = [(a, b) for a, b in pairs if passes(flip(header, a, b))]
print(f"{len(pairs):,} two-bit errors, undetected: {len(missed):,} ({len(missed) / len(pairs):.1%})")
same_column = all(a % 16 == b % 16 for a, b in missed)
opposite = all((header[a // 8] >> (7 - a % 8) & 1) != (header[b // 8] >> (7 - b % 8) & 1) for a, b in missed)
print("all of them hit the same bit position in two different words:", same_column)
print("all of them turn one 0 into 1 and one 1 into 0:", opposite)
a, b = missed[0]
print(f"the first: position {a % 16} (counting from the left, from 0) of word {a // 16} and of word {b // 16}")

as sent: True
addresses swapped: True

160 single-bit errors, undetected: 0
12,720 two-bit errors, undetected: 260 (2.0%)
all of them hit the same bit position in two different words: True
all of them turn one 0 into 1 and one 1 into 0: True
the first: position 0 (counting from the left, from 0) of word 0 and of word 6

Swapping the source and destination addresses changes the header completely and leaves the sum untouched. Every one of the 160 single-bit errors was detected, but 260 of the 12,720 two-bit errors, 2.0 %, were not, and all of them had the same shape: the same bit position in two different words, one changing from 0 to 1 and the other from 1 to 0. One word grew by $2^k$ while the other shrank by $2^k$, so the sum stayed the same.

A CRC has no such blind spots for errors this small. The 32-bit CRC of Ethernet keeps a minimum distance of at least 4 on frames of up to 12,144 bits, according to the measurements that RFC 3385 summarises, so it detects every one-, two- and three-bit error in any frame up to 1,518 bytes, the classic Ethernet maximum. That is why links check frames with CRCs, while the checksum stays in IP, UDP and TCP, where it is quick to compute and to update and where a CRC on the link has already caught most damage. The next lesson builds CRCs from scratch.

Interview questions

What does a code’s minimum Hamming distance tell you? It is the smallest number of bits in which any two codewords differ, and it fixes what the code can do: with minimum distance d, every pattern of up to d − 1 flipped bits is detected, because it cannot turn one codeword into another, and up to ⌊(d − 1)/2⌋ flipped bits can be corrected by choosing the nearest codeword. A single parity bit has d = 2 (detects one error, corrects none), and Hamming(7,4) has d = 3 (corrects one, or detects two).

Why does a receiver add up an IPv4 header, checksum included, and expect 0xFFFF? The sender stored the complement of the sum of all the other words in the checksum field. Adding a number and its complement sets every bit, so an intact header sums to 0xFFFF, which is zero in ones’ complement arithmetic. Any other total means that the header changed on the way.

Key takeaways

• A parity bit detects every odd number of flipped bits and misses every even number.
• Two-dimensional parity locates and corrects a single flipped bit; in the 5 × 5 block every 1-, 2- and 3-bit error was detected and 100 of 12,650 four-bit errors were missed.
• A code with minimum distance d detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋, but not both at full strength at once.
• Hamming(7,4) puts check bits at positions 1, 2 and 4; the syndrome is the position of a single flipped bit, and two flipped bits are “corrected” into the wrong data.
• The Internet checksum is the complement of the ones’ complement sum of 16-bit words; an intact header sums to 0xFFFF, and routers update it with RFC 1624’s formula when the TTL changes.
• It misses reordered words and errors that cancel out, 2.0 % of all two-bit errors in the example header; links use CRCs, and IPv6 dropped its header checksum.