A noisy bit does not apologize.

It flips, and the receiver sees another perfectly legal bit. The channel does not attach a note saying, “this one changed.”

Error correction works by refusing to use all possible bit strings as messages. It spends redundancy to leave empty space around valid messages. When noise moves a received word into that empty space, the decoder can often infer which valid word was nearby.

That is the core idea:

reliability is bought by spacing codewords apart

The code is a geometry.

Bits Live on a Cube

An \(n\)-bit word is a vertex of an \(n\)-dimensional cube. Two words are close if they differ in few positions. That distance is now called Hamming distance.

Hamming’s 1950 paper explicitly uses this geometric model, identifying binary sequences with vertices of a unit \(n\)-dimensional cube.1 A code is a selected subset of those vertices. The minimum distance of the code is the smallest distance between any two selected vertices.

If two codewords are distance 3 apart, then a single-bit error cannot turn one valid word into another valid word. It lands in a neighboring non-codeword. A nearest-neighbor decoder can move it back.

If two bits flip, the received word may be closer to the wrong codeword, or may look like a single-bit error somewhere else. Distance 3 buys guaranteed single-error correction. It does not buy arbitrary miracles.

Seven Bits With an Address Book

The \((7,4)\) Hamming code stores four data bits in seven transmitted bits. Positions 1, 2, and 4 are parity checks. Positions 3, 5, 6, and 7 carry data.

The parity checks are arranged so that every bit position has a unique binary address:

position: 1 2 3 4 5 6 7
address:  1 2 3 4 5 6 7

After receiving seven bits, recompute the three parity checks. The failed checks form a three-bit syndrome. If the syndrome is 5, flip bit 5. If the syndrome is 0, accept the word.

This is a beautiful little trick. The syndrome is not merely a flag saying “something is wrong.” It is an address.

The price is rate:

\[\text{rate} = \frac{4}{7}.\]

Four information bits consume seven channel uses. The code is less efficient than raw transmission on a perfect channel and far more reliable on a moderately noisy one.

A Noisy Channel on the Table

The lab below compares four schemes on a binary symmetric channel, where every transmitted bit independently flips with probability \(p\).

  • raw sends the four payload bits directly;
  • Hamming(7,4) corrects one flipped bit in the seven-bit block;
  • SECDED(8,4) adds one overall parity bit, so it can correct one error and detect every two-bit error;
  • repeat-3 sends each payload bit three times and decodes by majority vote.

The outcome probabilities are exact sums over all error masks, not Monte Carlo. The one-word panel lets you choose a payload and a seven-bit error mask to see the Hamming syndrome directly.

Exact binary symmetric channel calculation over all error masks. Success means the decoded payload equals the transmitted payload. Wrong means the decoder accepts an incorrect payload. Erasure means SECDED detected an uncorrectable pattern and refused to deliver a payload. The script also runs a deterministic audit over the finite toy code before reporting its check count.

At \(p=3\%\), raw four-bit transmission has about an 11.5% block error rate: one or more payload bits flipped. Hamming(7,4) is much better because all single-bit errors in the seven-bit block are corrected. Its wrong-accepted rate is 1.71%, mostly from two or more flips.

SECDED adds an eighth parity bit. It slightly reduces delivered success because some corrupted blocks become erasures, but it sharply reduces wrong accepted payloads: at the same 3% bit-flip rate, the lab reports 0.13% silent wrong payloads and 2.10% detected erasures. That is often the right bargain. In memory systems, storage, and transport protocols, “I know this block is bad” can be much safer than a quiet wrong answer.

Repeat-3 does well at low bit error rates, but it spends twelve transmitted bits to send four payload bits. Its rate is \(1/3\), versus \(4/7\) for Hamming. Reliability is never free. The question is which reliability you bought per channel use.

Detection Is Not Correction

Single parity detects any odd number of bit flips. It cannot tell you where the error happened.

Hamming parity checks do more. They are arranged so that each bit participates in a unique pattern of checks. A single flipped bit therefore leaves a unique syndrome. The decoder can correct it.

But correction and detection are different promises:

detection says "this is not a codeword"
correction says "this is probably that codeword"

The unextended \((7,4)\) Hamming code corrects every one-bit error, but two-bit errors can masquerade as one-bit errors. The decoder flips a third bit and may deliver the wrong payload.

Adding the eighth parity bit changes the geometry. The extended code has minimum distance 4. It can still correct one error, and now every two-bit error is detected rather than silently “corrected” into nonsense.

That is why the lab separates wrong from erasure. A low error rate is not enough. The kind of error matters.

Because this example is small, the implementation does not need sampling faith. Its exported runAudit() checks the finite state space directly: all 16 clean payload round trips for each scheme, every one-bit Hamming and SECDED correction case, every two-bit SECDED detection case, the Hamming two-bit miscorrection failure mode, the minimum distances 3 and 4, and probability-mass conservation for several channel settings. The visible 1113/1113 audit counter is not a claim about every physical channel. It is a promise that the model on the page matches the theorem on the page.

Shannon Promised Existence, Not a Circuit

Two years before Hamming’s paper, Shannon framed communication as reproducing a message selected at one point at another point, with noise and uncertainty made mathematical.2 His noisy-channel coding theorem says, roughly, that below channel capacity there exist codes whose error probability can be driven arbitrarily low with long enough blocks.

That theorem is astonishing. It is also existential. It does not hand you a cheap encoder, a decoder, latency bounds, or a convenient circuit.

Hamming(7,4) lives at the other end of the story: tiny, explicit, mechanical, and easy to decode. It is not capacity-achieving. It is a working geometry.

The modern coding-theory arc is the attempt to keep Shannon’s promise while making decoding computationally plausible.

Gallager’s low-density parity-check codes were a major step in that direction: represent the code by a sparse parity-check matrix, so each check touches only a small number of bits.3 Sparse checks make iterative decoding possible at long block lengths. Decades later, MacKay and Neal helped revive LDPC codes by showing near-Shannon-limit empirical performance with sparse matrices.4

The same idea is visible in miniature in Hamming(7,4). A syndrome is a small set of parity-check failures. Modern sparse-graph decoders generalize that local evidence into an iterative belief update over a much larger graph.

Before You Trust the Code

When I see an error-correcting code in a system, I want a ledger:

  • channel model: independent flips, burst errors, erasures, soft information, or something messier;
  • code rate and block length;
  • minimum distance or an empirical distance proxy;
  • guaranteed correction and detection radius;
  • probability of wrong accepted data versus detected failure;
  • latency budget for decoding;
  • whether the decoder uses hard bits or reliability scores;
  • interleaving strategy if burst errors are plausible;
  • behavior near the operating point, not only asymptotic capacity;
  • compatibility/versioning story for stored encoded data.

The most dangerous metric is “corrected errors.” A high correction count can mean the code is doing its job. It can also mean the channel is drifting toward a regime where two-error patterns become common and silent miscorrection is next.

The Sentence to Keep

An error-correcting code is a packing of messages in a noisy space.

Parity checks carve the space. Distance creates neighborhoods. The syndrome is a coordinate system for the noise you promised to handle. When the noise leaves that neighborhood, the honest decoder should know the difference between correction and refusal.

Primary Sources

  1. Richard W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal, 29(2), 1950. DOI: 10.1002/j.1538-7305.1950.tb00463.x. ↩

  2. Claude E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal, 27, 1948. ↩

  3. Robert G. Gallager, “Low-Density Parity-Check Codes”, IRE Transactions on Information Theory, 8(1), 1962. ↩

  4. David J. C. MacKay and Radford M. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes”, Electronics Letters, 32(18), 1996. ↩