Error-correcting codes
A Socratic walk-through of error-correcting codes — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How can a receiver reconstruct a message even when some transmitted bits are corrupted?
A receiver holds a string of bits, some of which are wrong, and has no copy of the original to compare against. How do you fix an error you cannot see? Yet a scratched disc still plays and a probe past Neptune still sends pictures home. So the assumption to question is that the receiver works blind. What might it know in advance?
Reasoning it through
REASONING #Consider the simplest guard. Add one bit that makes the number of ones in each block even. Flip any single bit and the count turns odd, so the receiver knows something broke — but not which bit. Detection is cheap, and detection alone is not correction.
What would correction need? Suppose you sent every bit three times. Receive 101 and you take the majority. Notice what made that work: of the eight possible three-bit strings, only 000 and 111 are legal, and every illegal string sits nearer one legal one than the other. The receiver does not detect the error; it asks which legal codeword is closest to what arrived. If two legal codewords differ in at least d positions, then up to floor((d-1)/2) flips still leave you nearest your true one. Repeating three times gives d=3: one error corrected, at 200% overhead. Ruinous.
Can we do better? Richard Hamming placed parity bits at positions 1, 2, 4, 8, each checking a different overlapping subset, so a single flipped bit fails a particular combination — and those failing checks, read as a binary number, are the position of the broken bit. Hamming(7,4) carries 4 data bits in 7 and costs 43% rather than 200%; with r parity bits you can name 2^r - 1 positions, so r=7 protects 127 bits carrying 120, barely 6%. But each still corrects only one error per block, and a longer block is likelier to suffer two.
The analogy
THE ANALOGY #Think of legal codewords as towns founded deliberately far apart, with the countryside between them empty. A message is delivered to a town; noise nudges the delivery a short way into open country. And because the towns were spaced widely, the courier can look around, see which single town is nearest, and walk to it. Spread them further and bigger nudges are survivable — but land spent on emptiness is land not spent on towns.
Distance here is counted in flipped bit positions, so a "small nudge" means few errors, not gentle ones. And a large enough push does not merely strand you; it can carry you into the streets of a different town, where the courier delivers confidently to the wrong address and nobody ever learns of the mistake.
Clarifying the model
THE MODEL #The misconception to dislodge is that the code inspects the damage. It does not. It compares what arrived against the fixed catalogue of what could legally have been sent and picks the nearest entry — a bet, correct only while the errors stay inside the code's designed distance. Which is why real systems match the code to the noise they face: Hamming-style codes for scattered single-bit flips in memory, and Reed-Solomon codes, which work on groups of bits, for the burst damage of a scratched disc or a smudged QR code.
A picture of it
THE PICTURE #How to readEach bar is one member of the Hamming family, from the 7-bit block carrying 4 data bits up to the 127-bit block carrying 120; the height is the share of the transmission spent on parity rather than message. Read left to right and the cost collapses — but read it as a warning too, since every bar buys the same protection, one corrected error per block, and the cheap wide blocks on the right are likeliest to be hit twice.
What became clearer
WHAT CLEARED #Correction is not repair; it is recognition. By agreeing in advance on a sparse set of legal codewords, the sender makes any corrupted arrival identifiable as illegal and, if the corruption is small enough, traceable back to the one legal word it came from. Redundancy buys the spacing, and the art lies in buying as little of it as the channel's noise allows.
Where to go next
ONWARD #- How Reed-Solomon codes survive burst errors, and why CDs and QR codes chose them.
- What Shannon's channel-coding theorem says about the best rate any code could ever achieve.
- Why modern systems favour LDPC and turbo codes, which decode by iterated probability rather than nearest-neighbour lookup.
Key terms
TERMS #| Term | What it means |
|---|---|
| Parity bit | one added bit making the count of ones in a block even or odd; detects an odd number of errors but locates none. |
| Codeword | a full transmitted block, message bits plus check bits, drawn from the agreed legal set. |
| Hamming distance | the number of bit positions in which two codewords differ. |
| Hamming code | a family placing parity bits at power-of-two positions so the failing checks spell out the position of a single flipped bit. |
Every term the collection defines is gathered in the glossary.