Hamming, 1950: how three check bits can repair one error

Written by an AI system from the cited sources, with automated checks under the News editorial method.

AI-generated conceptual cover: structured checks restore order in a disturbed stream; not a literal circuit or evidence of unlimited error correction.

1. Reliability through structured redundancy

In April 1950, Richard W. Hamming published “Error Detecting and Error Correcting Codes” in the Bell System Technical Journal. His problem was practical: detecting a fault in an unattended calculation could stop the work, but locating and correcting it could let the calculation continue. The paper gives explicit binary constructions, not a promise that arbitrary damage can be repaired. [1,2]

The advance is to make redundancy informative. Repeating four bits three times would require twelve transmitted bits. A Hamming code uses seven to protect the same four data bits against any one bit flip within that block. These are different arrangements of redundancy, not a claim that one code is optimal for every channel. Compression removes redundancy; error correction deliberately adds a controlled kind.

2. Seven positions, three questions

Number the transmitted positions from 1 to 7. Positions 1, 2 and 4 hold check bits; positions 3, 5, 6 and 7 hold data bits d₁, d₂, d₃ and d₄. The symbol ⊕ means exclusive OR: addition modulo 2, so 1 ⊕ 1 = 0. Choose even parity using the three equations below. The subscripts on p denote positions, not the order of the checks. [1, §3]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$p4​=d2​⊕d3​⊕d4​

The receiver repeats the checks over positions {1,3,5,7}, {2,3,6,7} and {4,5,6,7}. A failed check gives a syndrome bit of 1; a satisfied check gives 0. Call these s₁, s₂ and s₄. Under the assumption of at most one flipped bit, its position is j:

$j=s_1+2s_2+4s_4$j=s1​+2s2​+4s4​

A zero syndrome means no error only under that assumption; it is not a universal certificate of integrity.

3. A correction you can reproduce

Take data 1010. The equations give p₁ = 1, p₂ = 0 and p₄ = 1. The transmitted word, read left to right in position order, is therefore 1011010. If position 6 flips, the receiver gets 1011000. The first check is even; the second and third are odd. Thus (s₁,s₂,s₄) = (0,1,1), and j = 0 + 2 + 4 = 6. Flip position 6 back and read positions 3,5,6,7: the recovered data are 1010.

Scientific schematic produced by code; exact bit strings, not experimental data.

This example is an editorial calculation, not an experimental measurement. The same procedure also corrects a flipped check bit. It assumes the block boundaries and bit positions are known; a missing or inserted bit is a different error model.

4. Why the construction works

Three binary checks have eight possible outcomes. That is exactly enough to identify seven possible single-error positions plus the no-error case. More generally, a binary code with r check bits and n total bits needs at least n + 1 distinct syndromes for single-error correction:

$2^r\ge n+1$2r≥n+1

The Hamming construction attains this count with n = 2ʳ − 1 and k = n − r data bits. For r = 3, n = 7 and k = 4. Its minimum Hamming distance—the fewest differing positions between two valid words—is 3. No received word can be within one flip of two different valid words, because that would place those words at distance at most 2.

There are 16 valid words, each with itself and seven one-flip neighbours. The disjoint sets fill all 128 seven-bit words: 16 × 8 = 128. “Perfect” describes this packing property, not flawless operation at arbitrary noise levels. [1, §§5,7]

5. The trap of two errors

Two flipped bits always produce a nonzero syndrome in this code, so a detector that only flags invalid words can detect them. But a decoder that interprets every nonzero syndrome as a single error can make a wrong correction. For example, flips at positions 2 and 5 give the same syndrome as a flip at position 7. Correcting position 7 then leaves three wrong bits and another valid word.

Add an eighth bit so that the total parity of all eight positions is even. This extended code has minimum distance 4 and supports single-error correction plus double-error detection, abbreviated SECDED. The following decisions assume at most two bit flips. q is the parity of all eight received bits. [1, §4]

Three or more errors lie outside that guarantee. A SECDED decoder can miscorrect some of them; “double-error detection” is not a promise to diagnose every larger fault.

6. A numerical benefit—with explicit assumptions

Suppose each transmitted bit flips independently with probability p = 0.01, the same for 0 and 1. Assume perfect encoding/decoding and known block boundaries. For the seven-bit code with the single-error decoder described here, the recovered four-bit message is wrong exactly when the block contains at least two flips:

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$Pfail​​=1−(1−p)7−7p(1−p)6.​

The result is approximately 0.002031, or 0.2031% of blocks. Sending the four data bits without coding gives 1 − (1 − p)⁴ = 0.039404, or 3.9404% of four-bit messages with an error. These are message-error probabilities, not residual bit-error rates or measured device performance.

The protection costs three extra bits for every four data bits: 75% more transmitted bits, and a code rate of 4/7 ≈ 0.5714 data bits per transmitted bit. The comparison holds p fixed; it does not hold bandwidth, transmission time and energy per message simultaneously fixed.

7. What the result does and does not promise

The lasting contribution is a constructive link between algebra and reliability: choose valid words with separation, compute compact checks, and use the checks to localize a limited fault. The seven-bit case can be verified exhaustively rather than accepted on authority. For this article, all 16 messages and their 128 zero-or-one-error cases were checked, together with the 448 two-error cases of the extended code.

This is not a code for correcting arbitrary bursts, corrupted software, adversarial changes or lost synchronization. A real system must match its code to its fault model and protect the encoder, decoder and surrounding logic. Hamming’s paper does not supply measurements for modern hardware. Our numerical illustration is deliberately separated from such claims. The subject complements Shannon’s limits on communication by showing one explicit, finite construction—not a universal capacity-achieving solution.

News method for this article

Reference revision: HAMMING-EN-1. The 1950 primary paper was read in full from an archival scan and its OCR; the construction and SECDED cases were also checked on the scanned pages. The publisher’s record confirms the bibliographic date. MIT’s teaching notes provide a modern comparison of notation. Calculations and finite-code checks were executed with a reproducible script. Drafting and the seven translations are by AI; these checks are not independent expert review or human validation. The localized schematic is code-generated. The cover is an AI-generated conceptual illustration, not a photograph, instrument or data figure.

Sources

[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.

[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.

[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.