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.

Maintenance — 7 October 2026. The cover has been replaced because its original generation file and receipt could not be recovered within the available access. The replacement was received from the native image tool and visually inspected; its file, prompt and source references are preserved in the private editorial record. The previous cover and its unverified provenance remain in the history. This is an illustration, not experimental evidence; the central scientific result is unchanged.

AI-generated conceptual illustration of Hamming (7,4): four data bits, three check bits, one bit flip corrected per block. Symbolic tiles, not a circuit.

Before the equations

A bit is a value, 0 or 1. A flip changes one into the other. Parity asks whether a group contains an even or odd number of 1s. For example, 101 contains two 1s: its parity is even. Redundancy means sending extra information that lets the receiver check the data. Here, three overlapping checks can locate one flipped bit, provided there is at most one in a seven-bit block.

To understand the idea, follow the worked example in section 3, then return to the equations in section 2. To verify it, use the complete program below. Before continuing, ask yourself: does a successful check prove that no bits changed? Section 5 explains why the answer depends on the error model.

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.

8. Reproduce the finite calculation

Protocol HAMMING-REPRO-1. Copy the complete Python block into reproduce_hamming.py and run python3 reproduce_hamming.py. It uses only the Python standard library, no network, data download or random seed. It was executed with CPython 3.12.14 in this editorial revision. Bit positions start at 1; the eighth bit sets even overall parity. The program enumerates all 16 messages, independently constructs the valid seven-bit words from parity constraints, and compares them with the encoder.

Expected output: status PASS, codewords 16, minimum_distances [3, 4]. The counts are 128 correct recoveries with zero or one error for seven bits; 144 for eight bits; 448 double errors detected by the extended code; 336 double errors miscorrected by the seven-bit decoder; and 896 triple errors miscorrected by the specified eight-bit decoder. The last two counts are negative controls: they expose the limits, not successful corrections. At p = 0.01, coded_message_error is approximately 0.00203104163494 and uncoded_message_error 0.03940399. These probabilities assume independent flips at fixed p, not equal energy or bandwidth.

"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform


def encode(data):
    a, b, c, d = data
    return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)


def syndrome(word):
    a, b, c, d, e, f, g = word[:7]
    return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)


def flip(word, positions):
    result = list(word)
    for position in positions:
        result[position - 1] ^= 1
    return tuple(result)


def decode7(word):
    position = syndrome(word)
    return flip(word, (position,)) if position else word


def decode8(word):
    position, parity = syndrome(word), sum(word) % 2
    if parity:
        return flip(word, (position or 8,))
    return None if position else word


def distance(a, b):
    return sum(x != y for x, y in zip(a, b))


def require(condition, label):
    if not condition:
        raise RuntimeError(label)


messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
    word for word in product((0, 1), repeat=7)
    if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
          "eight_double_detected": 0, "seven_double_miscorrected": 0,
          "eight_triple_miscorrected": 0}
for word in code7:
    for positions in [()] + [(i,) for i in range(1, 8)]:
        require(decode7(flip(word, positions)) == word, "seven-bit recovery")
        counts["seven_zero_or_one"] += 1
    for positions in combinations(range(1, 8), 2):
        received = flip(word, positions)
        require(syndrome(received) != 0, "double error detectable")
        require(decode7(received) != word, "double error outside correction guarantee")
        counts["seven_double_miscorrected"] += 1
for word in code8:
    for positions in [()] + [(i,) for i in range(1, 9)]:
        require(decode8(flip(word, positions)) == word, "eight-bit recovery")
        counts["eight_zero_or_one"] += 1
    for positions in combinations(range(1, 9), 2):
        require(decode8(flip(word, positions)) is None, "double error must be flagged")
        counts["eight_double_detected"] += 1
    for positions in combinations(range(1, 9), 3):
        result = decode8(flip(word, positions))
        require(result is not None and result != word and result in code8,
                "triple error counterexample")
        counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
                  "codewords": len(code7), "minimum_distances": [min7, min8],
                  "counts": counts, "p": p, "coded_message_error": failure,
                  "uncoded_message_error": uncoded, "status": "PASS"}, indent=2))

PASS means these finite mathematical checks passed. It does not establish hardware performance, robustness to other error models, or independent replication. The python field records your interpreter version and may differ. If execution raises RuntimeError, preserve the script and full output and investigate the named check; do not interpret a partial run as validation.

News method for this article

2026-10-03 — Revision HAMMING-EN-2 adds the progressive introduction and the complete reproduction protocol. The scientific body and programmed figure are retained from HAMMING-EN-1. For this update, the primary construction and its limits were rechecked against the 1950 paper and MIT sections 5.6–5.7; the finite program was executed. Writing and translations are by AI, with no independent expert or human validation.

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.