Hamming Codes

Every wire, disk and radio link occasionally flips a bit. A single parity bit can detect that something went wrong — but it can't tell you which bit broke, so all you can do is ask for the data again. What if the message could simply repair itself?

In 1950, frustrated by a weekend computer that halted on every error, Richard Hamming found a way. By adding just a few extra parity bits, placed at clever positions, he built a code where any single flipped bit doesn't just raise an alarm — it announces its own address.

That jump from "an error happened" to "the error is right here, and here's the fix" is the whole story of error-correcting codes. It is why a cosmic ray can strike your RAM and your computer never even notices.

Type four data bits. The demo encodes them into a 7-bit Hamming(7,4) codeword by adding three parity bits. Then click any bit to flip it — as if noise corrupted the channel.

<p class="hint">{{hint}}</p>

<div class="row">
  <span class="lbl">{{lbl_data}}</span>
  <div id="data" class="bits small"></div>
  <button id="rand" type="button" class="ghost">{{btn_random}}</button>
</div>

<div class="row">
  <span class="lbl">{{lbl_codeword}}</span>
</div>
<div id="word" class="bits"></div>
<div class="idx" id="idx"></div>

<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="fix" type="button">{{btn_fix}}</button>
  <button id="reset" type="button" class="ghost">{{btn_no_error}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .6rem; margin: .5rem 0 .2rem; flex-wrap: wrap; }
.lbl { font-size: .85rem; font-weight: 600; color: #1d3557; }
.bits { display: flex; gap: 6px; }
.bit { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
       font: 700 18px ui-monospace, monospace; border-radius: 8px; user-select: none;
       border: 1px solid #cdd9e3; background: #e8eef3; color: #1d3557; cursor: pointer; transition: all .1s; }
.bits.small .bit { width: 38px; height: 38px; font-size: 16px; }
.bit.parity { background: #d7e3ef; border-color: #b9cbdd; }
.bit.flipped { background: #e63946; border-color: #c92f3c; color: #fff; }
.bit.fixed { background: #0a7d33; border-color: #086628; color: #fff; }
.bit:hover { filter: brightness(.96); }
.idx { display: flex; gap: 6px; margin: 2px 0 .4rem; }
.idx span { width: 44px; text-align: center; font: 600 11px ui-monospace, monospace; color: #889; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the syndrome. The three parity checks combine into a number from 0 to 7. If it's 0, the word is clean. If it's anything else, that number is the position of the broken bit — the receiver flips it back and recovers your original nibble, with no retransmission. Flip a parity bit, a data bit, any bit: the syndrome always names the culprit.

Unlike many problems on KipuHub, this one is completely solved — and the solution is constructive and fast.

• Detection vs. correction. A lone parity bit gives the code minimum distance 2: it can spot one error but never locate it. Hamming codes reach minimum distance 3, which is exactly enough to correct any single error (and detect any double error).
• The syndrome does the locating. Each parity bit checks a carefully chosen subset of positions. After transmission you recompute all the parity checks; the failing checks, read as a binary number, spell out the exact index of the flipped bit. Decoding is a handful of XORs — linear time, no search.
• It's provably efficient. Hamming(7,4) carries 4 data bits in 7, and perfect Hamming codes meet the Hamming bound with equality: not one bit is wasted for the single-error-correcting guarantee.
• Proven in 1950. Richard Hamming published the construction in Error Detecting and Error Correcting Codes, founding the field of coding theory.

So this is the happy opposite of an intractable problem: cheap to encode, cheap to decode, and mathematically guaranteed to fix any single-bit error. The same algebra over SAT-style boolean variables here works for us instead of against us.

"Make the data survive noise" is one of computing's most universal demands, and Hamming's idea is the seed of how we meet it:

• ECC memory. Server and aerospace RAM stores extra Hamming-style parity so a cosmic-ray bit flip is corrected on the fly, invisibly.
• Storage and RAID. Flash controllers and disk arrays lean on error-correcting codes to keep your files intact as cells wear out.
• Deep-space and wireless links. Spacecraft, Wi-Fi and cellular all wrap data in codes descended from Hamming's so faint, noisy signals still arrive correct.
• Everyday redundancy. QR codes, CDs and barcodes all bake in correction so a scratch or smudge doesn't lose the message.

Understand the syndrome trick and you've met the foundation of reliable computing — the same drive to tame uncertainty that powers primality testing in cryptography and countless other algorithms.

Hamming codes hide a small miracle: by spending just three extra bits on four, you buy a guarantee that any single error will announce its own location and be erased. Detection becomes correction, and the channel quietly heals itself.

So the next time your computer runs for months without a glitch despite the constant rain of cosmic rays and electrical noise, remember Richard Hamming's 1950 insight. The reliability we take for granted isn't luck — it's a few clever parity bits, doing their quiet, self-correcting work.