Error detection and correction

The formula

The whole field hangs off one geometric idea: the Hamming distance between two codewords is the number of bit positions where they differ.

d(a, b) = number of positions where a and b disagree

Reading: how many single-bit errors it takes to turn codeword a into codeword b. If your valid codewords are spread out, noise has to work hard to land you on a different valid word.

The minimum distance d_min of a code — the smallest distance between any two of its valid codewords — sets everything you can do:

detect up to  s errors   requires   d_min ≥ s + 1
correct up to t errors   requires   d_min ≥ 2t + 1

Reading: to detect s flips you only need the corrupted word to not be another valid word. To correct t flips you need the received word to still be closer to the original than to any other codeword — hence the factor of two. Combined:

t = floor( (d_min - 1) / 2 )

A single parity bit is the cheapest detector — append one bit so the total count of 1s is even:

p = b1 XOR b2 XOR ... XOR bn

Reading: d_min = 2, so it detects any odd number of flips and corrects none.

A CRC (cyclic redundancy check) treats the message as a polynomial over GF(2) and appends the remainder after dividing by a fixed generator polynomial g(x):

CRC = ( M(x) · x^r ) mod g(x)      (r = degree of g)

Reading: the receiver redivides; a nonzero remainder means a detected error. Bit-shift-and-XOR in hardware, no multiplication.

For Reed–Solomon RS(n, k) over a symbol alphabet, the code is maximum-distance-separable:

d_min = n - k + 1
t = (n - k) / 2   symbol errors corrected

Reading: every parity symbol you add buys exactly half a symbol-error of correction — the best any block code can do.

Where you meet it

RF and telemetry test benches. Downlink from a UAV, a missile flight test, or a satellite arrives buried in noise. The frame sync, the CRC pass/fail flag, and the FEC decoder's corrected-bit count are the three numbers you watch. A CRC that keeps failing while signal strength looks fine points at a clocking or bit-slip problem, not a link-budget problem.
Memory and storage on the bench. DRAM in a flight computer runs SECDED ECC (single-error-correct, double-error-detect) — a Hamming code plus one extra parity bit. When you see corrected-error counters climbing on a board under vibration or thermal soak, that's ECC doing its job and telling you a part is marginal before it fails outright.
Design review board. Someone proposes a link and quotes a raw bit-error rate. The question that stops the meeting: what's the coded BER after FEC, and how much bandwidth (code rate) did you spend to get it? A code rate of 1/2 means half your channel carries redundancy, not payload. That trade is the whole conversation.
Anything with a QR code or a scratched disc. Reed–Solomon is why a QR label with a coffee stain still scans and why a fingerprinted CD still plays. Same math, consumer packaging.

How it works

Picture every possible n-bit word as a point in a grid. A code carves out a small subset of those points and calls them "valid." Noise nudges a transmitted point to a nearby point. Detection works if the nudge never lands you exactly on another valid point. Correction works if you snap the received point back to the nearest valid point and that nearest neighbor is the one you sent. All of coding theory is arranging the valid points far enough apart for the noise you expect.

The mistake people make is treating "error correction" as free insurance. It isn't — you pay in bandwidth, power, latency, and silicon. A rate-1/2 code doubles your transmission time or halves your throughput. Push the code rate up toward 1 and you're barely correcting anything; push it down and you're mostly transmitting parity. Shannon's channel-coding theorem ^[4] says there's a hard ceiling, the channel capacity C: you can get arbitrarily reliable at any rate below C and it's flatly impossible above it. Good codes get close to C; nothing beats it.

The other gotcha is error type. A single parity bit or a naive Hamming code assumes random, isolated bit flips. Real channels throw burst errors — a whole run of adjacent bits wrecked by a fade, a scratch, or a static hit. CRCs are specifically strong against bursts up to the degree of the generator polynomial. Reed–Solomon works on multi-bit symbols, so a burst that trashes one symbol costs you one symbol-error regardless of how many bits inside it flipped — which is exactly why it went on the compact disc and the Voyager downlink ^[7]. And interleaving — scrambling bit order before transmission and unscrambling after — spreads a burst across many codewords so each one only sees a correctable sprinkle.

Know the limit of the guarantee. A code that corrects t errors is guaranteed only up to t. Feed it t+1 and it may silently "correct" to the wrong codeword and hand you clean-looking garbage. That's the danger zone: undetected error is worse than detected error, because you trust it. This is why storage stacks layer a strong detector (CRC) on top of a corrector — the CRC is the backstop that catches the corrector when it guesses wrong.

Concrete numbers. The classic Hamming(7,4) code sends 4 data bits in 7, has d_min = 3, and corrects exactly one bit error per block — verified by enumerating all 16 codewords. RS(255,223), the old NASA/CCSDS workhorse, adds 32 parity symbols, gives d_min = 33, and corrects up to 16 symbol errors in a 255-symbol block.

History

The field starts with two men in the same building. In 1948 Claude Shannon at Bell Labs published A Mathematical Theory of Communication and proved the counterintuitive result that a noisy channel has a finite capacity below which error-free communication is possible — but his proof was an existence proof ^[4]^[5]. It said good codes exist without telling you how to build one.

Richard Hamming, a colleague of Shannon's at Bell, had a more immediate irritation: the relay computer he shared ran unattended on weekends, and when the card reader flipped a bit, the machine halted and threw away his whole job. Tired of losing weekends, he worked out codes that didn't just detect the error but pinpointed and fixed it. His paper Error Detecting and Error Correcting Codes ran in the April 1950 Bell System Technical Journal and introduced the distance idea and the Hamming(7,4) code that still carries his name ^[1]^[2].

Detection got its polynomial workhorse in 1961, when W. Wesley Peterson laid out the systematic theory of cyclic codes for error detection — the mathematics that became the CRC, now stamped on every Ethernet frame, ZIP file, and PNG ^[6]. A year earlier, in 1960, Irving Reed and Gustave Solomon published the symbol-oriented block codes that would prove almost tailor-made for burst-heavy channels ^[3]^[7]. A Reed–Solomon encoder flew on the Voyager probes at their 1977 launch — a bet that ground decoders would catch up — and the concatenated RS downlink was first used in anger at the 1986 Uranus encounter; RS then shipped in the first compact discs in 1982 ^[3]^[7].

Two threads then sat quietly for decades. Robert Gallager introduced low-density parity-check (LDPC) codes in his 1960 MIT doctoral thesis (published as an MIT Press monograph in 1963); they were too expensive to decode with 1960s hardware and were nearly forgotten until MacKay and Neal rediscovered them in the mid-1990s ^[8]. And in 1993, Claude Berrou, Alain Glavieux, and Punya Thitimajshima stunned a Geneva conference with turbo codes — the first practical codes to claw within roughly half a decibel of Shannon's 1948 limit ^[9]^[10]. Together, turbo and LDPC codes are why your phone gets a usable signal at the edge of a cell. Shannon promised the ceiling in 1948; it took forty-five years to build a ladder that reached it.

Related tools

/tools/snr-enob
/tools/thermal-noise-floor
/tools/noise-figure-temperature
/tools/db-converter

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →