Error Detection and Correction

Detecting versus correcting

Bits get damaged. Electrical noise on a cable, a dirty fiber connector, a weak flash cell or a particle of cosmic radiation can turn a 0 into a 1. A computer cannot look at a single bit and tell whether it is right: a damaged 1 looks exactly like a genuine 1. The only defense is redundancy: send or store a few extra bits, computed from the data with a fixed rule. The receiver applies the same rule and compares. If the results disagree, something changed.

There are two levels of ambition:

• Detection: notice that something is wrong, then throw the data away and get it again. An Ethernet switch drops a frame with a bad check value; TCP notices the gap and sends the data again. Cheap, and fine when a resend is possible.
• Correction: work out which bits were damaged and repair them on the spot. Needed when there is nothing to ask again: a memory chip, a hard disk, a QR code with a coffee stain, a space probe billions of kilometers away.

Correction costs more redundancy than detection, and the mathematics on this page — mostly XOR, remainders and counting differences — explains exactly how much.

Parity bits

The simplest scheme adds one bit. A parity bit is an extra bit chosen so that the total number of 1s in a group of bits is even (even parity) or odd (odd parity). Computing it is an XOR of all the data bits: XOR is 1 exactly when the number of 1s is odd. Worked example with even parity for the seven data bits 1011001:

1. Count the 1s: 1 + 0 + 1 + 1 + 0 + 0 + 1 = 4.
2. 4 is already even, so the parity bit is 0. Send 1011001 0.
3. One bit flips on the way: the receiver gets 1011101 0. It counts five 1s in the data, so it expects parity bit 1, but received 0: error detected.
4. Two bits flip: 1010101 0. Four 1s, parity 0, matches. The error goes unnoticed.

def even_parity_bit(byte):
    return bin(byte).count("1") % 2

data = 0b1011001
print(even_parity_bit(data))
received = data ^ 0b0000100          # one bit flipped
print(even_parity_bit(received) != even_parity_bit(data))
received2 = data ^ 0b0001100         # two bits flipped: not detected
print(even_parity_bit(received2) != even_parity_bit(data))

0
True
False

In general one parity bit detects every odd number of flipped bits and misses every even number, and it never says which bit is wrong. It survives in serial links (a UART can add a parity bit to every character), and it is the idea behind RAID parity.

XOR parity in RAID

RAID 5 stores, next to each stripe of data blocks, a parity block that is the XOR of the data blocks, bit by bit. Because XOR undoes itself (x \oplus x = 0), the XOR of all surviving blocks and the parity block rebuilds a lost disk's block. Here the "position" of the error is known — the failed disk reports itself — so one parity block is enough to correct it. The full story is on RAID: parity; in three lines:

blocks = [0b1100_1010, 0b0101_0110, 0b1111_0000]   # three data disks
parity = blocks[0] ^ blocks[1] ^ blocks[2]
rebuilt = blocks[0] ^ blocks[2] ^ parity           # disk 2 lost
print(format(parity, "08b"), rebuilt == blocks[1])

01101100 True

A lost block whose position is known is called an erasure. Correcting erasures is easier than correcting errors at unknown positions, which is why one parity disk protects against one failed disk (RAID 5) and two independent parity blocks against two (RAID 6).

Hamming distance

To compare codes, count differences. The Hamming distance between two bit strings of the same length is the number of positions in which they differ — equivalently, the number of 1s in their XOR. It is named after Richard Hamming, who worked on error-correcting codes at Bell Labs in the late 1940s.

• 1011001 and 1011101 differ in one position: distance 1.
• 0110011 and 1110000 differ in positions 1, 6 and 7: distance 3.

A code is a set of allowed bit strings (codewords). Its minimum distance d is the smallest Hamming distance between any two different codewords. This one number tells you what the code can do:

• It detects up to d - 1 flipped bits: fewer than d flips can never turn one codeword into another, so the result is not a valid codeword and the damage shows.
• It corrects up to \lfloor (d - 1)/2 \rfloor flipped bits by choosing the nearest codeword: with that few errors, the damaged word is still closer to the original than to any other codeword.

The "detects" and "corrects" columns are alternatives, not a combination: a decoder set up to correct single errors will "fix" a double error into the wrong codeword. With d = 4, a decoder can correct one error and still recognize two as uncorrectable, which is what ECC memory reports.

from itertools import combinations

def distance(a, b):
    return sum(x != y for x, y in zip(a, b))

print(distance("1011001", "1011101"), distance("0110011", "1110000"))

triple = ["000", "111"]                                   # repetition code
parity = [f"{n:03b}" for n in range(8) if f"{n:03b}".count("1") % 2 == 0]
for name, code in (("repetition", triple), ("even parity", parity)):
    d = min(distance(a, b) for a, b in combinations(code, 2))
    print(f"{name}: {code} d={d} detects {d - 1} corrects {(d - 1) // 2}")

1 3
repetition: ['000', '111'] d=3 detects 2 corrects 1
even parity: ['000', '011', '101', '110'] d=2 detects 1 corrects 0

Checksums

A checksum is a short value computed from a block of data, usually by adding up its bytes or words in some way, and sent or stored along with it so that accidental changes can be detected. The simplest version adds all bytes modulo 256. It catches any single changed byte, but it has a blind spot: addition does not care about order, so swapped bytes go unnoticed.

The Internet checksum

The IPv4 header, TCP and UDP (see TCP, UDP and Ports) all use the Internet checksum of RFC 1071: the one's-complement sum of the data taken as 16-bit words, inverted. "One's-complement sum" means ordinary addition, except that a carry out of the top bit is added back in at the bottom ("end-around carry"). Worked out for the eight bytes 00 01 f2 03 f4 f5 f6 f7 (the example in RFC 1071 itself), in hexadecimal:

1. Split into 16-bit words: 0001, f203, f4f5, f6f7.
2. Add them as ordinary numbers: 0001 + f203 + f4f5 + f6f7 = 2ddf0. That is more than 16 bits: the extra digit 2 is the carry.
3. Fold the carry back in: ddf0 + 2 = ddf2.
4. Invert every bit (one's complement): ffff − ddf2 = 220d. The checksum is 0x220d.
5. The receiver adds all words including the checksum the same way; for undamaged data the result is ffff (all ones).

import zlib

def internet_checksum(data):
    if len(data) % 2:
        data += b"\0"                                   # pad to whole 16-bit words
    total = sum(int.from_bytes(data[i:i + 2], "big") for i in range(0, len(data), 2))
    while total >> 16:
        total = (total & 0xFFFF) + (total >> 16)        # end-around carry
    return ~total & 0xFFFF

print(hex(internet_checksum(bytes.fromhex("0001f203f4f5f6f7"))))

# Blind spot: swapping two 16-bit words does not change the sum
a, b = bytes.fromhex("0001f203"), bytes.fromhex("f2030001")
print(hex(internet_checksum(a)), hex(internet_checksum(b)))
print(hex(zlib.crc32(a)), hex(zlib.crc32(b)))           # a CRC notices

0x220d
0xdfb 0xdfb
0x9f0567ae 0x786a8fff

The Internet checksum was designed to be fast to compute in software, not to be strong. That is acceptable because most links, Ethernet among them, also protect every frame with a much stronger CRC, described next. Other check values with the same goal, but for numbers people type, are the check digits in IBANs and card numbers (see Modular Arithmetic).

Cyclic redundancy checks

A cyclic redundancy check (CRC) is a check value computed as the remainder of a division: the message bits are treated as the coefficients of a polynomial and divided by a fixed generator polynomial, using arithmetic in which addition and subtraction are both XOR. The sender appends the remainder; the receiver divides the whole thing and expects remainder 0.

"Polynomial" sounds frightening, but it is only bookkeeping. The bit string 1011 stands for 1 \cdot x^3 + 0 \cdot x^2 + 1 \cdot x + 1 = x^3 + x + 1: each bit is the coefficient of one power of x. Because the coefficients are bits and 1 + 1 = 0 (no carries), long division becomes "write the generator under the leading 1 and XOR", repeated until the remaining part is shorter than the generator.

Worked example: a 3-bit CRC by hand

Message 110101, generator 1011 (x^3 + x + 1, degree 3, so the CRC has 3 bits).

1. Append three 0 bits (one per bit of the CRC): 110101000.
2. Wherever the leftmost remaining bit is 1, XOR the generator underneath it; skip over 0s.
3. Stop when only the last three bits can still be 1. They are the remainder.

110101000     message 110101 followed by three 0 bits
1011          generator under the leading 1: XOR
---------
011001000
 1011
---------
001111000
  1011
---------
000100000
   1011
---------
000001100     (the next bit is 0: skip it)
     1011
---------
000000111     remainder: 111

The sender transmits 110101 111. The receiver divides those nine bits by 1011 and gets remainder 000; if any bit changed, the remainder is (very likely) not zero:

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

crc = crc_remainder("110101" + "000", "1011")
print("crc:", crc)
print("check sent frame:   ", crc_remainder("110101" + crc, "1011"))
print("check damaged frame:", crc_remainder("110001" + crc, "1011"))

crc: 111
check sent frame:    000
check damaged frame: 111

CRC-32 and the Ethernet frame check sequence

Real CRCs use longer generators. Every Ethernet frame ends with a 4-byte frame check sequence (FCS): a CRC-32 over the frame, with the generator polynomial specified in IEEE 802.3:

Written as bits without the leading x^{32} term, that is 0x04C11DB7. The same CRC-32 protects ZIP archives and PNG images, and Python has it in the standard library. The customary test is the text "123456789", whose CRC-32 is 0xCBF43926; change a single character and the value changes completely:

import zlib, binascii

print(hex(zlib.crc32(b"123456789")))
print(hex(binascii.crc32(b"123456789")))
print(hex(zlib.crc32(b"123456788")))

0xcbf43926
0xcbf43926
0xbcf309b0

Why a division? Its mathematics guarantees strong properties. A CRC whose generator has degree r and a nonzero last term detects every burst of errors up to r bits long — for CRC-32, any run of up to 32 consecutive damaged bits, which is the typical shape of interference on a cable. For random damage beyond that, a wrong frame slips through with a chance of about 1 in 2^{32}, roughly 1 in 4.3 billion.

A switch or network card that receives a frame with a wrong FCS simply drops it and counts it. Rising CRC or FCS error counters on an interface are therefore a physical-layer symptom: a bad cable, a dirty fiber, a failing transceiver or a duplex mismatch (see common physical problems). When Emeka Obi in the NOC sees the error counter of one switch port climb while its neighbors stay at zero, the cable on that port is the first suspect.

Hamming codes: correcting a bit

An error-correcting code (ECC) adds enough redundancy that the receiver can not only detect damage but also work out the original data, as long as the number of errors stays within the code's limit. A Hamming code is a classic, efficient example: several parity bits, each covering a different, overlapping group of positions, arranged so that the pattern of failing checks spells out the position of a single flipped bit. The smallest useful one is Hamming(7,4): 7 bits sent, 4 of them data.

Encoding

Each parity bit makes the number of 1s in its group even, so it is the XOR of the data bits in that group. For the data d_1 d_2 d_3 d_4 = 1011:

1. p1 covers positions 3, 5, 7 = d1, d2, d4: 1 \oplus 0 \oplus 1 = 0.
2. p2 covers positions 3, 6, 7 = d1, d3, d4: 1 \oplus 1 \oplus 1 = 1.
3. p3 covers positions 5, 6, 7 = d2, d3, d4: 0 \oplus 1 \oplus 1 = 0.
4. Put everything in position order p1 p2 d1 p3 d2 d3 d4: the codeword is 0110011.

Decoding: the syndrome points at the error

Suppose position 5 flips and the receiver gets 0110111. It recomputes each check over its whole group, parity bit included; a correct group gives 0:

1. Check 1 (positions 1, 3, 5, 7): 0 \oplus 1 \oplus 1 \oplus 1 = 1 — fails.
2. Check 2 (positions 2, 3, 6, 7): 1 \oplus 1 \oplus 1 \oplus 1 = 0 — passes.
3. Check 3 (positions 4, 5, 6, 7): 0 \oplus 1 \oplus 1 \oplus 1 = 1 — fails.
4. Read the results as a binary number, check 3 first: 101 = 5. This number is called the syndrome. Flip bit 5 back, and the data bits (positions 3, 5, 6, 7) are 1011 again.

It works because of the layout: position 5 is 101 in binary, so it belongs to exactly the groups of check 1 and check 3. Every position has a different binary number, so every single-bit error makes a different set of checks fail, and that set is the position number. A syndrome of 0 means no error was found.

from itertools import combinations, product

def hamming74_encode(d):              # d = [d1, d2, d3, d4]
    d1, d2, d3, d4 = d
    p1 = d1 ^ d2 ^ d4
    p2 = d1 ^ d3 ^ d4
    p3 = d2 ^ d3 ^ d4
    return [p1, p2, d1, p3, d2, d3, d4]          # positions 1..7

def hamming74_decode(c):
    c = c[:]
    s1 = c[0] ^ c[2] ^ c[4] ^ c[6]
    s2 = c[1] ^ c[2] ^ c[5] ^ c[6]
    s3 = c[3] ^ c[4] ^ c[5] ^ c[6]
    pos = s1 + 2 * s2 + 4 * s3                   # 0 = no error
    if pos:
        c[pos - 1] ^= 1
    return pos, [c[2], c[4], c[5], c[6]]

code = hamming74_encode([1, 0, 1, 1])
print(code)
damaged = code[:]
damaged[4] ^= 1                                  # flip position 5
print(damaged)
print(hamming74_decode(damaged))

codewords = [hamming74_encode(list(d)) for d in product([0, 1], repeat=4)]
print("minimum distance:",
      min(sum(x != y for x, y in zip(a, b)) for a, b in combinations(codewords, 2)))

[0, 1, 1, 0, 0, 1, 1]
[0, 1, 1, 0, 1, 1, 1]
(5, [1, 0, 1, 1])
minimum distance: 3

The last line confirms the claim from the table: the 16 codewords of Hamming(7,4) are all at least 3 bits apart, so the code corrects one error. Three parity bits protect four data bits here; with r parity bits the same construction protects 2^r - r - 1 data bits, so longer Hamming codes are much more efficient (7 parity bits for 120 data bits).

Where you meet it: ECC memory

ECC memory stores extra check bits with every memory word (for example 8 check bits per 64 data bits on DDR4). The classic scheme is a Hamming code plus one overall parity bit, often called SECDED: single error correction, double error detection. The extra parity bit raises the minimum distance to 4, so one flipped bit is corrected on the fly and two flipped bits are reported as uncorrectable instead of being "corrected" into wrong data. Server logs that show a slowly growing number of corrected errors on one module are an early warning to replace it.

Stronger codes: Reed–Solomon and erasure coding

Hamming codes fix single bits. Storage and radio need more: scratches and interference damage whole bytes or bursts. Reed–Solomon codes work on blocks of bits (symbols) instead of single bits and use the arithmetic of polynomials over finite fields — the same idea as CRCs, taken further. With k data symbols and m extra symbols, any m lost symbols at known positions can be rebuilt. They are used in QR codes (which still scan with part of the code damaged), CDs and DVDs, some RAID 6 implementations and in the erasure coding of large storage clusters, where data is split into, say, 8 data fragments plus 3 coding fragments spread over different servers, so any 3 servers can fail.

Accidents versus attacks

Every method on this page assumes that errors are accidental: random noise does not know the rule. An attacker does. Anyone who changes a message can simply recompute its parity, checksum or CRC, and the receiver will accept it. The computation is public and needs no secret:

import hashlib, hmac, zlib

original = b"Pay 120.00 EUR to NL13TEST0123456789"
forged   = b"Pay 920.00 EUR to NL13TEST0123456789"

# A CRC only proves the data was not damaged by accident
print(hex(zlib.crc32(forged)), "<- the forger just sends the new CRC along")

# An HMAC needs a secret key that the forger does not have
key = b"kestrel-billing-demo-key"        # demo only: real keys come from a vault
tag = hmac.new(key, original, hashlib.sha256).hexdigest()
check = hmac.new(key, forged, hashlib.sha256).hexdigest()
print(hmac.compare_digest(tag, check))

0x75f70823 <- the forger just sends the new CRC along
False

Against deliberate tampering you need cryptography: a cryptographic hash such as SHA-256 when the expected value comes from a trusted source (the checksum file you verify a download against, as on checking packages), and an HMAC or a digital signature when the value travels with the data. The mathematics behind those is on The Math Behind Cryptography.