bits.

FREE HISTORICAL FIGURES OF COMPUTING PROFILE

Richard Hamming

1915–1998 · Mathematician and computer scientist

Richard Hamming

Mathematician and computer scientist · 1915–1998 · United States

Richard Hamming developed practical and mathematical techniques for making digital computation less vulnerable to errors. His 1950 paper gives constructions for detecting errors, correcting one error, and combining single-error correction with double-error detection. Those are distinct guarantees. The distinction matters whenever a decoder must decide whether to repair a received word or report that it cannot safely do so.

A problem of unattended computation

In a 1982 retrospective, Hamming connected this research with unreliable runs on Bell Labs' Model 5 computer. He also acknowledged that repeating a computation and taking a majority was already known. Publication in 1950 was not the instant of discovery: his account describes earlier work and a delay associated with patent applications. This evidence supports a specific engineering motivation without requiring an invented quotation or a claim that no one had previously corrected errors. Hamming's retrospective

Hamming also worked on numerical methods and automatic programming, and later taught at the Naval Postgraduate School. The code studied here is one part of that career. Modern systems use many coding families; a device containing error correction need not use a Hamming code. NPS resources

Worked mechanism: locating a flipped bit

Use even parity and number seven bit positions from 1 through 7. Put data in positions 3, 5, 6, and 7. Reserve 1, 2, and 4 for parity. The three checks cover positions whose binary indices contain the corresponding bit:

CheckPositions included
11, 3, 5, 7
22, 3, 6, 7
44, 5, 6, 7

To encode data 1011, place 1,0,1,1 in positions 3,5,6,7. Check 1 already sees two ones, so its parity bit is 0. Check 2 sees three ones, so its parity bit is 1. Check 4 sees two ones, so its parity bit is 0. The codeword is 0110011.

Suppose bit 6 flips, yielding 0110001. Check 1 passes; checks 2 and 4 fail. The syndrome is 4 + 2 = 6, identifying the flipped position. Correcting position 6 recovers the codeword and hence the original four data bits. This bit ordering is an original worked presentation of the code, not a quotation of Hamming's example. His paper supplies the construction and its broader reasoning. 1950 paper

Why does this work? Each position participates in a unique nonempty combination of checks, exactly its three-bit binary index. A single flipped bit toggles precisely that combination. The all-zero syndrome represents no error under the single-error assumption.

What the decoder cannot infer

If positions 1 and 2 flip, the syndrome is the bitwise XOR of their indices: 001 XOR 010 = 011. A decoder that assumes one error will flip position 3. It has now changed three positions relative to the original word and produced a different valid codeword. The decoder cannot determine from that syndrome alone whether the original event was one error at position 3 or two errors at positions 1 and 2.

The basic code has minimum Hamming distance 3. Distance counts differing positions in equal-length words. Such a code can correct one error, or detect up to two errors when used only for detection. It cannot promise both single-error correction and dependable double-error notification with that same single-error decoder.

Adding an overall parity bit produces the extended eight-bit code with minimum distance 4. Under the assumption of at most two flipped bits, a nonzero syndrome plus odd overall parity indicates a single error among the first seven bits; a nonzero syndrome plus even overall parity indicates two errors. Zero syndrome with odd parity identifies the extra parity bit. Three or more errors fall outside this guarantee and can be misclassified. 1950 paper, single-error correction plus double-error detection

Geometry and engineering limits

There are 16 possible four-bit messages. Each seven-bit codeword needs eight distinct received patterns assigned to it: itself and its seven single-bit corruptions. Since 16 × 8 = 128 = 2^7, these neighborhoods exactly fill the seven-bit space without overlapping. There is no unassigned pattern left for the ordinary single-error decoder to label as an uncorrectable double error.

This calculation also explains why redundancy is not wasted storage. It separates valid messages far enough for a specified error model. Yet the model matters. Independent random flips, bursts of adjacent corruption, lost bits, and a faulty decoder are different failure processes. A Hamming distance calculation does not by itself cover insertion or deletion errors. End-to-end system correctness requires checking what failures the code actually protects against and what happens when its assumptions fail.

Exercises

  1. Encode and repair. Under the convention above, encode data 0110. Flip position 5, calculate all parity checks, and recover the data. Explain how a receiver distinguishes a parity-bit error from a data-bit error.
  2. Capacity of the syndrome. You want 11 data bits and single-error correction with r check bits. Derive the necessary inequality by counting the no-error case and possible single-error positions. Find the smallest r that passes this bound and state whether the bound alone constructs a code.
  3. Reliability claim. Each bit of a seven-bit word independently flips with probability 0.01. Calculate the probability of two or more flips. Explain why this is an event outside the one-error guarantee, rather than a promise that the decoder will flag every such word. Describe how adding overall parity changes the guarantee.
Compare your reasoning with the worked solutions
  1. The data positions are 3=0,5=1,6=1,7=0. Parities are p1=1,p2=1,p4=0, giving 1100110. Flipping position 5 gives 1100010. Checks 1 and 4 fail while check 2 passes, so the syndrome is 5. Flip that bit back and read positions 3,5,6,7 to recover 0110. A syndrome that is a power of two identifies one of the reserved check positions. This interpretation is justified only within the assumed single-error model.
  2. With total length n=11+r, the syndrome needs at least n+1 distinct values, hence 2^r ≥ 12+r. For r=3, 8 is less than 15; for r=4, 16 equals 16. Four check bits suffice for the familiar length-15 Hamming construction. Counting alone is only a necessary condition in general; here choosing the 15 distinct nonzero four-bit columns constructs the required checks.
  3. The complementary events are no flips and exactly one flip. The probability is 1 − 0.99^7 − 7(0.01)(0.99^6), approximately 0.002031, or 0.2031%. A two-bit event can imitate a single-bit syndrome and lead to miscorrection. Overall parity makes the extended code distinguish single from double errors under an at-most-two-errors assumption. The longer word also changes the event probabilities, and larger error patterns can still defeat that classification.

Sources and further study