Introduction

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.

Encode and Correct

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">Type four <b>data bits</b>, and we encode them into a 7-bit
    Hamming(7,4) codeword by adding three parity bits (positions 1, 2 and 4).
    Then <b>click any bit</b> to flip it — like noise on the wire. Watch the
    syndrome point straight at the error and fix it.</p>

<div class="row">
  <span class="lbl">Data:</span>
  <div id="data" class="bits small"></div>
  <button id="rand" type="button" class="ghost">Random</button>
</div>

<div class="row">
  <span class="lbl">Sent codeword (click to flip):</span>
</div>
<div id="word" class="bits"></div>
<div class="idx" id="idx"></div>

<div class="status" id="status">Click a bit to inject an error.</div>
<div class="btns">
  <button id="fix" type="button">Decode &amp; correct</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hamming(7,4): positions are 1..7. Positions that are powers of two
// (1,2,4) hold parity bits; the rest (3,5,6,7) hold the 4 data bits.
// p1 (pos 1) covers positions 1,3,5,7  (index bit 0)
// p2 (pos 2) covers positions 2,3,6,7  (index bit 1)
// p4 (pos 4) covers positions 4,5,6,7  (index bit 2)
// Decoding: XOR the positions of all the 1-bits. The result (the
    // "syndrome") is 0 if clean, or exactly the position of the flipped bit.
const DATA_POS = [3, 5, 6, 7];     // where the 4 data bits live (1-indexed)
let data = [1, 0, 1, 1];           // current 4 data bits
let word = new Array(8).fill(0);   // word[1..7], the transmitted codeword
let flipped = -1;                  // which position the user flipped (-1 = none)

function encode() {
  const w = new Array(8).fill(0);
  DATA_POS.forEach((p, i) => { w[p] = data[i]; });
  // parity bit at position 2^k = XOR of data bits it covers
  [1, 2, 4].forEach(pp => {
    let x = 0;
    for (let p = 1; p <= 7; p++) if (p !== pp && (p & pp)) x ^= w[p];
    w[pp] = x;
  });
  return w;
}
// Syndrome = XOR of the indices of every position currently holding a 1.
function syndrome(w) {
  let s = 0;
  for (let p = 1; p <= 7; p++) if (w[p]) s ^= p;
  return s;
}

function isParity(p) { return p === 1 || p === 2 || p === 4; }

function render() {
  // data bits
  const d = document.getElementById('data'); d.innerHTML = '';
  data.forEach((b, i) => {
    const el = document.createElement('div');
    el.className = 'bit'; el.textContent = b;
    el.addEventListener('click', () => { data[i] ^= 1; resend(); });
    d.appendChild(el);
  });
  // codeword
  const wEl = document.getElementById('word'); wEl.innerHTML = '';
  const idx = document.getElementById('idx'); idx.innerHTML = '';
  for (let p = 1; p <= 7; p++) {
    const el = document.createElement('div');
    el.className = 'bit' + (isParity(p) ? ' parity' : '') + (p === flipped ? ' flipped' : '');
    el.textContent = word[p];
    el.addEventListener('click', () => {
      word[p] ^= 1;
      flipped = (word[p] !== encode()[p]) ? p : -1;
      setStatus('Click a bit to inject an error.', '');
      render();
    });
    wEl.appendChild(el);
    const lab = document.createElement('span');
    lab.textContent = (isParity(p) ? 'p' : 'd') + p;
    idx.appendChild(lab);
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function resend() {
  word = encode(); flipped = -1;
  setStatus('Click a bit to inject an error.', '');
  render();
}

function fix() {
  const s = syndrome(word);
  if (s === 0) {
    setStatus('Syndrome = 0 — no error detected. Word is clean.', 'ok');
    render();
    return;
  }
  // s is the position of the broken bit. Flip it back.
  word[s] ^= 1;
  flipped = -1;
  render();
  // mark the corrected cell green
  const cells = document.getElementById('word').children;
  cells[s - 1].classList.add('fixed');
  setStatus(fmt('Syndrome = %s% → corrected bit at position %s%. Data recovered!', { s: s }), 'ok');
  console.log('syndrome', s, 'corrected word', word.slice(1).join(''));
}

document.getElementById('fix').addEventListener('click', fix);
document.getElementById('reset').addEventListener('click', resend);
document.getElementById('rand').addEventListener('click', () => {
  data = data.map(() => Math.random() < 0.5 ? 0 : 1); resend();
});
resend();
Result
Console

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.

The Real Story

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hamming-codes/Content licensed under CC BY-NC 4.0.