information
Correct the corrupted block
It is 1950 at Bell Labs, and the computers of the day corrupt bits often enough that a long unattended calculation is regularly ruined — and worse, the machine doesn't even know it erred. Design a code that can correct any single-bit error (and detect two) in a sixty-four-bit block with minimal added redundancy, and that a 1950s relay-and-tube machine can actually compute. The overhead must be small and the arithmetic simple enough for the hardware of the era. Get it wrong and either every long computation stays hostage to silent flips, or your redundancy is so bloated the machine spends its life on parity instead of work — self-correcting codes are what let unreliable hardware do reliable arithmetic, and the constraint is doing it in period-realistic logic.
Who this problem belongs to
The two figures whose methods fit it best, out of 33 in contention.
This problem is a description of Hamming's actual annoyance and actual invention. At Bell Labs in the late 1940s his weekend relay-computer runs were silently ruined by dropped bits, and his 1950 paper 'Error Detecting and Error Correcting Codes' gives exactly the construction demanded here: place parity bits at power-of-two positions so that the failing check bits spell out the binary address of the flipped bit, then add one overall parity bit to get single-error-correction, double-error-detection. For a 64-bit payload this costs 7 check bits plus the SEC-DED bit — provably minimal for this scheme — and the decoding is nothing but XOR trees, trivially realizable in relay-and-tube logic. He also proved the sphere-packing bound showing you cannot do better. The problem is his biography.
Shannon shares the building, the decade, and the mathematical frame. His 1948 paper defined channel capacity and proved that codes driving error to zero exist below it, giving the theoretical ceiling against which Hamming's construction is measured; his 1937 thesis reduced relay circuits to Boolean algebra, precisely the design language a 1950s parity-check circuit is written in. What he did not supply is the explicit constructive code — his existence proofs are famously non-constructive random-coding arguments, and he left the concrete algebra to Hamming, Golay, and later Reed and Muller. Handed this problem, Shannon has every conceptual tool to verify optimality and to engineer the relay logic, and his own 1950s papers show he could produce clever explicit gadgets when pressed. Slightly behind the man who actually did it.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
33 figures are scored on this problem. Draw it in a battle to see where you land.