Error Correction from Scratch — Sending Data on the Assumption It Will Break

Starting from a single parity bit, this article builds up Hamming distance, syndrome decoding and Reed–Solomon codes with no assumed background, then explains why a smudged QR code still scans — and where ECC bites you in production.

Sending data on the assumption it will break

Almost everyone has spelled their name over the phone and been misheard, and the fix is always the same: "S as in Sierra, M as in Mike." The information has not changed — you are deliberately using more words. That extra length is not waste; it is material for reconstructing the original once part of it is destroyed.

One assumption needs flipping first. A radio link or a disk is not something that "rarely breaks" — treat it as something that breaks at some rate, always. Not "make sure it does not break" but "make sure it can be reconstructed after it breaks": that shift is the doorway in.

This field also runs in exactly the opposite direction to Entropy Coding from Scratch. Compression strips out redundancy that is merely repetitive; error correction adds redundancy that is deliberately useful. So real systems always compress first and add parity afterwards. Reverse the order and the compressor cheerfully deletes the protection you just paid for.

The cheapest insurance — one parity bit

The smallest possible redundancy is one bit: append a 0 or 1 so that the number of ones is even. For 1011 there are three ones, so the parity bit is 1 and you send 10111. The receiver counts again, and an odd count means something got corrupted.

There are two limits. You do not learn where the damage is, so you cannot repair it. And two simultaneous flips restore the original parity, so the check quietly reports that all is well. Going further takes more than extra redundancy — it takes designing how the redundancy is added.

Think in distances and the whole picture appears

Change your point of view. Treat a bit string of length $n$ as one point in $n$-dimensional space. The ruler for the gap between two points is Hamming distance.

Put in words, $\#\{\,\cdot\,\}$ is "how many things satisfy this condition" and $x_i \neq y_i$ is "position $i$ disagrees". Line the two strings up and count the positions where they disagree — that is all it says. A single bit error is exactly a move of distance 1 to a neighbouring point.

Designing a code means picking, out of the $2^n$ points, the subset you are allowed to transmit (the codewords), and the quality of that choice is the minimum distance $d_{\min}$ between any two of them. If codewords are $d_{\min}$ apart, up to $d_{\min}-1$ errors land on a point that is not a codeword and so can be detected; pull that point back to the nearest codeword and you have corrected it.

You can repair as many errors as half the minimum separation minus one, rounded down; the $\lfloor\,\cdot\,\rfloor$ brackets are the round-down symbol, so a half-measure is always discarded on the safe side. Or, in words, once you have fixed how far apart the codewords sit ($d_{\min}$), the repair budget ($t$) is no longer yours to choose — it follows. Draw a ball of radius $t$ around each codeword: this is the largest $t$ for which the balls still do not overlap. With $d_{\min}=3$, a point one flip out sits at distance 1 from its own codeword and 2 or more from every other, so the repair is unambiguous — but two flips can drift closer to a different codeword. Hence one bit of correction, no more.

One further distinction pays off constantly. An error is damage whose location is unknown; an erasure is damage whose location is known (a bit that read back as ?, a numbered packet that never arrived). When the position is known you only have to fill in a value, so the same redundancy recovers twice as many symbols.

Hamming codes — making the error report its own address

In 1950, Richard Hamming at Bell Labs started from "if the machine can detect an error, why can't it locate and fix it?" and built a code with $d_{\min}=3$. The famous one is the Hamming (7,4) code: four data bits plus three check bits, sent as seven.

The clever part is where the check bits go. Number the positions 1 to 7 and write each number in binary. The first check bit covers every position whose ones place is set (1, 3, 5, 7), the second the twos place (2, 3, 6, 7), the third the fours place (4, 5, 6, 7), and the check bits themselves live at positions 1, 2 and 4. The receiver simply recomputes those three parities — which, written compactly, is one multiplication by a parity-check matrix $H$.

$r$ is the seven received bits, $H$ is a 3×7 table whose every column is the binary representation of that column's position number, and $s$ is the three-bit result, called the syndrome. $\pmod 2$ means "the remainder after dividing by two" — 0 when the count of ones is even, 1 when it is odd. Said in words, the formula asks for nothing more than "recompute, over the seven bits that actually arrived, the same three parities you agreed on in advance". 000 means clean. Otherwise — and this is the trick — reading those three bits as a binary number gives the position of the damaged bit directly.

Work it through. Encoding 1011 gives the codeword 0110111 (positions 1 to 7). If the fifth bit flips and 0110011 arrives, the three parities come out 1, 0, 1, and reading from the low end, $1 + 0 \times 2 + 1 \times 4 = 5$. The code itself answers "position 5 is broken", so flipping that bit back restores the word.

This is syndrome decoding. The naive approach compares the received word against every codeword — but with $k$ data bits there are $2^k$ of them, so brute force grows exponentially. Syndrome decoding replaces the whole search with one lookup indexed by $n-k$ bits.

Production systems usually append one more overall parity bit, giving an extended Hamming code with $d_{\min}=4$: single-error correction, double-error detection (SECDED). By equation (2) the correction power stays at $t=1$ and only detection gains a notch. Server ECC memory is built this way, most commonly as (72,64) — eight check bits for 64 data bits. Refusing to correct a double-bit error and stopping at detection is the point: pushed past its limit, a decoder can turn the word into a different, valid-looking codeword (miscorrection), and reporting "unreadable" beats silently returning wrong data.

The Hamming (7,4) decoder in code

The decoding side is remarkably short.

import numpy as np

# each column is the binary representation of its position number (3x7)
H = np.array([[1, 0, 1, 0, 1, 0, 1],    # ones place:  positions 1,3,5,7
              [0, 1, 1, 0, 0, 1, 1],    # twos place:  positions 2,3,6,7
              [0, 0, 0, 1, 1, 1, 1]])   # fours place: positions 4,5,6,7

def decode(r):                          # r: the seven received bits
    s = H @ r % 2                       # the syndrome (3 bits)
    pos = s[0] + 2 * s[1] + 4 * s[2]    # reads directly as the error position
    if pos:
        r = r.copy()
        r[pos - 1] ^= 1                 # flip exactly one bit back
    return r[[2, 4, 5, 6]]              # pull out the data bits

Notice how thoroughly % 2 dominates. Error-correction arithmetic runs end to end in the field of two elements, GF(2), where addition and subtraction are both XOR. With no carries the hardware is just a mesh of XOR gates, which is why ECC fits inside a memory controller at roughly a clock cycle of added latency.

Protecting whole bytes — Reed–Solomon

Hamming codes are strong against scattered independent flips, but most real damage arrives as a burst: a scratch on a disc, a fade on a radio link, a smudge on a QR code. Three consecutive flips inside seven bits and a Hamming code is helpless.

The Reed–Solomon code, published in 1960 by Irving Reed and Gustave Solomon, solves this by working on symbols — usually one byte — instead of individual bits. Whether one bit or all eight inside a byte are destroyed, it counts as a single symbol error and consumes one slot of budget. Bursts become structurally cheap.

RS($n$, $k$) adds $n-k$ check symbols to $k$ data symbols, and the mechanism is polynomials: treat the data as coefficients and transmit the polynomial's value at $n$ points. Any $k$ points pin the polynomial down, so the surplus $n-k$ points can be spent locating and repairing the corrupted ones.

$t$ is the number of errors whose position is unknown, $e$ the number of erasures whose position is known: an error you must first locate costs two check symbols, an erasure costs one. It is really a piece of accounting, which says: the $n-k$ check symbols are your budget, every error withdraws two and every erasure withdraws one, and the word stays recoverable for exactly as long as you stay inside that budget. The "known position means twice the repairs" rule from earlier is exactly this inequality.

RS(255,223), long used in NASA deep-space links, carries 32 check symbols: up to 16 corrupted bytes if positions are unknown, or 32 bytes of erasures if they are known. Audio CDs layer RS(32,28) and RS(28,24) with cross-interleaving (the CIRC scheme), scattering a scratch's contiguous damage across many blocks before decoding. Interleaving raises nobody's correction power — it is preprocessing that turns bursts into the scattered errors the code is good at.

Why a smudged QR code still scans

The everyday example is the QR code: underneath the squares is a Reed–Solomon code over GF(256), with the payload turned into bytes, check bytes appended, and the result laid out on a grid. You choose one of four correction levels — L, M, Q, H — recovering roughly 7%, 15%, 25% and 30% of the codewords. A grid of a given size holds a fixed number of codewords, so raising the level always shrinks the payload that fits.

What really makes it robust is less the code than the layout.

• Data and check bytes are split into blocks and interleaved across the grid, so a localised smudge shaves a little off every block instead of annihilating one
• The three big corner squares (finder patterns) are not for correction — they let the scanner work out position, rotation and scale. Destroy them and the code is never located at all
• The format information (which level, which mask) is protected by a separate BCH code and written twice in different places
• One of eight mask patterns is XORed over the grid, chosen by a penalty score, to avoid large uniform areas that make scanning unstable

Putting a logo in the middle works only because it is borrowing against that correction budget. The covered modules are treated as errors and repaired, and the headroom shrinks by exactly that much. Add faded printing and camera shake and the total crosses the threshold — the code that worked yesterday stops working today. If the logo overlaps the finder patterns or the format information, even level H cannot save it.

How this shows up on the job

Infrastructure and storage engineers meet ECC through memory first. On Linux, rasdaemon and edac-util count corrected errors (CE) and uncorrectable errors (UE), and the number to watch is the rate of change of CE. "It was corrected, therefore it is fine" is the wrong reading: a DIMM whose CE count keeps climbing is usually degrading toward a UE, and on SSDs smartctl's uncorrectable error counters are a wear indicator in the same way.

Embedded and communications firmware engineers choose the codes themselves. NAND controllers historically used BCH and have largely moved to LDPC, because shrinking cells raise the raw bit error rate and demand stronger correction. 5G NR splits the job — LDPC for data channels, polar codes for control channels — a common pattern of using different codes for short control messages and long data payloads.

Anyone printing QR codes onto physical media touches the level and the quiet zone. With Python's qrcode that means error_correction=ERROR_CORRECT_H, border (the margin in modules; the standard requires at least 4) and box_size, then verifying by scanning the printed artefact with zbar or zxing. The most common self-inflicted failure is trimming border for design reasons: an insufficient quiet zone cannot be rescued by error correction at all, because the problem lives outside the code.

Application developers mostly need the detection-versus-correction distinction. CRC32 and SHA-256 tell you something broke; they do not repair it, and the per-chunk CRC discussed in Why PNG Does Not Degrade is detection only. Where retransmission is available, detect-and-resend is the cheaper design; correction codes earn their keep where you cannot ask again, like live broadcast or reading a disc.

Three pitfalls are worth carrying around. Miscorrection — damage beyond the limit can, with low but nonzero probability, mutate into a different valid codeword, which is why important data gets a CRC layered outside the correcting code. Redundancy does not simply add up — two weak codes stacked are not one strong code, and you need interleaving to reshape the damage first. A code encodes an assumption about the error distribution — feed bursts to a code designed for independent flips and you fall short of its nominal capability without warning. The design-review question "why does $d_{\min}=3$ only fix one bit?" is answerable by translating equation (2) back into overlapping balls.

Summary

• Error correction is not about building a link that never breaks; it assumes breakage and budgets redundancy that makes reconstruction possible
• Detection and correction share one ruler, the minimum distance between codewords: $d_{\min}$ determines $t = \lfloor (d_{\min}-1)/2 \rfloor$
• Hamming codes make the error report its own address as a syndrome, collapsing a brute-force search into one table lookup
• Reed–Solomon works on symbols, which makes it naturally strong against bursts — hence QR codes, CDs and deep-space links
• An erasure, whose position is known, costs half as much to repair as an error, whose position is not

How much redundancy buys how much noise immunity was settled first by Shannon's channel capacity. How that same notion of information connects to the loss functions of machine learning is covered in Information Theory and AI.