A bit is a fragile thing. Stored as a tiny pocket of charge in a memory cell, or beamed across the air at gigahertz frequencies, it can be flipped from to by a stray cosmic ray, a thermal fluctuation, or a wisp of radio noise. If a single such accident corrupts a single bit in a long message, the receiver typically has no way to tell, and any computation that depends on that bit silently goes wrong. The question is: how can a sender add a small amount of redundancy to a message so that the receiver can not only notice that something went wrong, but identify which bit flipped and fix it?
The first satisfying answer was published in 1950 by Richard Hamming, working at Bell Labs. The codes that bear his name are still in daily use seventy-five years later, behind the scenes of the memory chips, satellite links, and storage devices that the modern world runs on. This article explains how they work.
Why a single parity bit is not enough
The simplest form of redundancy is a parity bit: append one extra bit to a message such that the total number of s in the augmented message is always even. If a single bit flips somewhere on its journey, the parity becomes odd, and the receiver knows something has gone wrong. So far so good.
The problem is that a single parity bit tells the receiver only that an error occurred, not where. With nothing further to go on, the only recovery is to ask the sender to retransmit — costly when bandwidth is precious, and impossible when the message is being read off a damaged disk that no longer holds the original. To actually correct an error you need to localize it.
Hamming’s idea: parity bits in clever positions
Hamming’s insight was to use several parity bits, each one watching over a carefully chosen subset of the message bits. If the subsets are chosen so that every possible single-bit error produces a unique pattern of failures across the parity bits, then the receiver can decode that pattern and identify exactly which bit went bad.
The classical example is the Hamming(7,4) code, which packages four data bits together with three parity bits into a seven-bit codeword. The three parity bits cover overlapping subsets of the data bits according to the diagram below: watches ; watches ; watches . The trick is that every data bit is covered by a different combination of parity bits.
Each parity bit is set so that the sum of the bits inside its circle is even — equivalently, equals the XOR of the data bits in its circle. The sender chooses the parities; the receiver, on getting the seven bits, recomputes each parity and notes which ones now come out wrong. The pattern of wrong parities is called the syndrome.
Here is the magic. Read the syndrome as a three-bit number , where if parity failed. That binary number is exactly the position of the bit that flipped, indexed cleverly. A syndrome of means no error. A syndrome of means bit flipped; means bit ; on up to , the only pattern where all three parities fail, which singles out the very centre bit covered by all three circles. Eight possible syndromes, eight possible outcomes: no error, or one of seven specific bits is wrong. The receiver flips that bit back, and the message is restored.
What the geometry is telling us
The cleverness becomes inevitable once you think of bit strings as points in a discrete geometry. Every seven-bit string is a corner of a seven-dimensional cube. The valid codewords — the ones a sender might actually transmit — form a small subset of these corners, scattered through the cube. The Hamming distance between two corners is the number of bit positions in which they differ.
A code that can correct a single-bit error must space its valid codewords so that no two of them are within Hamming distance of each other. If every codeword has a “no-fly zone” of all strings at distance around it — the strings reachable from it by a single flip — then those no-fly zones must be disjoint, and a received string within someone’s zone can be uniquely traced back to its centre. The Hamming(7,4) code achieves this: it has codewords spaced at Hamming distance at least apart in a cube with corners, and the no-fly zones (each containing strings) just barely tile the whole cube — . The code is “perfect” in the sense that no string is wasted.
More errors, more redundancy
A code’s distance — the smallest Hamming distance between two of its codewords — is the single number that controls its power. A code of distance detects up to errors and corrects up to . Hamming(7,4) has distance : it corrects one error and detects two. To correct two errors you need distance , which requires more parity bits per data bit. There is no free lunch — the more errors you want to handle, the more redundancy you must pay.
The pleasant surprise is how cheap basic protection turns out to be. Hamming(7,4) carries four useful bits per seven transmitted: an overhead of about , and it guarantees recovery from any single-bit error. An “extended” Hamming code adds one further parity bit to make the codeword eight bits long — the format used in ECC RAM today — which can correct any single-bit error and detect any double-bit error, at an overhead of one byte per eight data bytes.
The descendants
Hamming’s 1950 paper opened a whole field. Reed–Muller codes generalised the construction. BCH codes and especially the closely related Reed–Solomon codes moved from bits to bytes and gave the protection used by CDs, DVDs, QR codes, and barcodes — designed to tolerate not just a flipped bit but a whole scratched-out region. Low-density parity-check codes and turbo codes approached the absolute theoretical limit set by Shannon’s noisy-channel theorem, and now run inside every modern smartphone, every Wi-Fi connection, and the data links to the Voyager probes still transmitting from beyond the heliosphere.
Every one of these schemes works on the same plan Hamming sketched: pack a message into a small high-dimensional structure where the valid messages sit far apart from each other, so that even after noise has nudged each one a little, you can find your way back to the right corner of the cube. The discrete geometry of codewords turned out to be one of the most quietly important pieces of mathematics of the 20th century — without it, no modern computer or network would work for an afternoon.
Frequently asked
Who was Hamming and why did he invent these codes?
Richard Hamming was a mathematician at Bell Labs in the late 1940s. The story goes that the early relay computers he used would crash whenever they hit a bit error in their punched cards, losing him an entire weekend's worth of computation. After one too many such losses he decided that since the machine could detect that something was wrong, it ought to be able to fix it, and he published his single-error-correcting code in 1950.
What is the difference between detecting and correcting an error?
A simple parity bit lets a receiver notice that one bit must have flipped, but gives no information about which one — so all the receiver can do is ask for a retransmission. A correcting code adds enough extra bits that the receiver can identify the exact position of the flipped bit and silently restore it. Hamming codes are the smallest codes capable of single-bit correction.
What does the 'distance' of a code mean?
The Hamming distance between two bit strings is the number of positions in which they differ. The distance of a code is the smallest Hamming distance between any two valid codewords. A code of distance d can detect up to d − 1 errors and correct up to (d − 1)/2 errors. The classical Hamming code has distance 3, so it corrects any single-bit error and detects any double-bit error.
Where are Hamming codes used today?
Versions of Hamming's idea are everywhere. ECC RAM in servers uses an extended Hamming code so cosmic-ray bit flips do not silently corrupt data. Deep-space probes use related codes for transmissions across millions of kilometres of noisy vacuum. CDs and QR codes use stronger Reed–Solomon codes that descend from the same ideas. Modern hard drives, solid-state storage, and wireless networks all run continuously on error-correcting codes that trace their lineage to Hamming's 1950 paper.