Error-correcting codes: The idea
In plain words
The idea explained without jargon
Noise or wear sometimes flips a bit in stored or sent data. An error-correcting code adds extra check bits, worked out from the message by a fixed rule. Only a small set of the possible bit patterns are valid, and the valid ones are kept far apart. When a received pattern is not valid, the receiver picks the valid pattern nearest to it, and that is usually the one that was sent. A code whose valid patterns differ in at least d places can repair every pattern of up to (d - 1) / 2 errors [1]. Hamming's first code used 7 bits to carry 4 message bits and could repair any single flipped bit [1]. More check bits buy more protection, at the cost of space or speed.
as of 2026-11-12
Key equation
The equation that sums it up, and what each symbol means
- Equation
- t = floor((d - 1) / 2)
- Symbols
- {"t":"the number of errors in a block that the code can always repair","d":"the minimum distance: the smallest number of places in which two valid codewords differ"}
- Note
- A code with minimum distance d can correct all patterns of (d - 1) / 2 or fewer errors, rounded down [1]. Hamming's (7, 4, 3) code has d = 3, so t = 1.
as of 2026-11-12
An analogy
A picture from everyday life that makes the idea easier to hold
Think of spelling. Of all the strings of letters you could type, only a few are real words, and a mistyped word is usually closer to the word you meant than to any other. A reader fixes 'wrld' without being told. The picture stops being true because words are not spaced evenly: a code is built so that its valid patterns are far apart in a planned way, and if too many errors arrive at once, the receiver is fooled and repairs the wrong thing.
as of 2026-11-12
Sources
- Channel Coding: The Road to Channel Capacity Proceedings of the IEEE, on arXiv (D. J. Costello Jr. and G. D. Forney Jr.), 2006