Hamming codes: finding the one bit that lied

1. Introduction

Have you ever thought what happened when you send a message over a wire or wireless network? Data on any medium is fragile. A single bit flips from any reason — cosmic ray, bad solder, defected cable, et cetera. and your message arrives wrong. In old days, a scratch really does affect the 1s and 0s on the CD, but despite that, the data was still readable.

Error can occur in two ways: Hard errors and Soft errors.

Historial events:
• 1972: early space & nuclear era case studies
• 1977: semiconductor manufacturing contamination case studies
• 2003: how cosmic ray caused a big voting error in belgium elections

"The single-event upset (SEU) is a type of radiation-induced error that occurs when a single bit in a digital circuit is flipped due to the influence of a high-energy particle, such as a cosmic ray or a particle from a nuclear explosion. This type of error is particularly relevant in space and nuclear environments, where the risk of radiation exposure is high."

2. The problem

It all started with Claude Shannon at Bell Labs ^[𝓳]it's quite funny how every pioneer seemed to work at bell labs 😂.... He was developing the theory of information and communication. Same place, his colleague Richard Hamming was working on the problem of error detection and correction. It was the time when shannon mentioned the efficient error correction is always possible no matter how high the bit flips in theory on his paper A Mathematical Theory of Communication^[𝓳]they both shared labs despite working on different things which doesn't feel coincidental 😂....

Facts aside, Parity checking was already being used to detect errors in the calculations of the relay-based computers of the day, and Hamming realized that a more sophisticated pattern of parity checking allowed the correction of single errors along with the detection of double errors.

3. A single parity bit

The simplest trick: reserve one bit at the front of the block whose only job is to make the total count of 1s even. Take for example, the following 4x4 grid which consists of 16 bits:

Richard's insight here: if any bit flips during transmission, the total count of 1s goes from even to odd. The receiver can tell something happened. Amazing isn't it?

But, but, but... this is not enough. We got following problems:

• It only tells you that an error happened — not where.
• What if two bits flip? The count stays even. Silence. No alarm at all.

4. Triple redundancy (the brute force)

Okay, so how do we actually restore lost data? Send every bit three times. At recovery, take the majority vote — two matching bits win. It works, but now two-thirds of your transmission is redundant. Fine for a thought experiment, painful at scale.

5. Hamming's trick — parity at powers of 2

Hamming's move: instead of one parity bit over the whole block, put several parity bits at positions that are powers of 2 — indices 1, 2, 4, 8, 16... Each one covers a different subset of the block. Run the checks together and you can narrow down the error to a single coordinate. Yes, that's the whole trick. Quite elegant isn't it?

For a 16-bit block laid out as a 4×4 grid (indices 0–15), you get 12 data bits and 4 parity bits. Scale it up and the pattern holds: parity bits grow as log₂ of the block size. Double the block, add one more parity bit.

6. Hamming's construction

Parity, on its own, only detects errors. In its simplest form you count the 1s in a block, reduce that count modulo 2, and append the answer — 0 for an even count, 1 for an odd one. The jump from detection to correction is the whole idea.

Let m be the number of information bits, k the number of check bits, and $n=m+k$. Since k bits can address the numbers 0 through $2^k-1$, we need them to reach every position in the block:

When that holds, the location of a single error falls straight out as the k-bit binary of its index — what Hamming called the checking number. He places the check bits at the power-of-2 positions $x_1,x_2,x_4,\dots ,x_{2^{k-1}}$ and the m data bits everywhere else. His original (7, 4) code has $k=3$, $m=4$, $n=7$, and a rate of $\genfrac{}{}{0ex}{}{4}{7}\approx 0.571$.

Each check bit owns exactly one bit of the checking number. At the encoder, $x_1$ is fixed by the partial parity over every position whose index carries a 1 in its least-significant bit:

Those indices — 1, 3, 5, 7, … — are precisely the odd ones. So if a single bit flips in any odd position, the decoder instead finds the sum broken:

The least-significant bit of the checking number is now a 1. The next check, $x_2$, covers every index with a 1 in its second bit — 2, 3, 6, 7, … , whose binaries 10, 11, 110, 111 all share that bit:

and a flip in any of those positions turns it into

The remaining checks $x_4,x_8,\dots ,x_{2^{k-1}}$ follow the same pattern, each reading off one higher bit of the position. Collect the results from right to left — eqⁿ(1)/(2) give bit 0, eqⁿ(3)/(4) give bit 1, and so on — and the error's location appears in binary. Once you know where the error is, flip back.

7. Why Galois fields? (the XOR part)

Quick detour into where this arithmetic comes from, because the name carries a story. A Galois field — or finite field named after Évariste Galois — is a number system with only finitely many elements where you can still add, subtract, multiply and divide and nothing breaks. The smallest one, GF(2), is just {0, 1}.

His Galois theory tied the symmetry of a polynomial's roots — a group — to whether the equation can be solved by radicals, finally explaining why there's no general formula for the quintic, a question left open for three centuries. Finite fields dropped out of the same circle of ideas, which is why we still call them Galois fields and write GF(q).

That sounds abstract, but the impact is everywhere you don't look. The arithmetic of GF(2ⁿ) is the engine under error-correcting codes — Hamming here, Reed–Solomon in CDs, QR codes and deep-space probes — and the AES cipher guarding your traffic does its mixing in GF(2⁸). A teenager's pure-maths notes from 1832 quietly run a large slice of the modern internet.

"Galois' most significant contribution to mathematics is his development of Galois theory. He realized that the algebraic solution to a polynomial equation is related to the structure of a group of permutations associated with the roots of the polynomial. You may see another blog post about this as i know a little for now about this."

Before the grid makes sense, you need the arithmetic. Parity only cares about odd vs even — not the actual count. Normal addition gives you carries: 1 + 1 = 2. That's useless here. What you want is addition where pairs cancel:

1 + 1 = 0        (even count → nothing)
1 + 1 + 1 = 1    (odd count → stays)

That's exactly what happens in GF(2) — the Galois field with two elements {0, 1}. Addition in GF(2) is XOR. On a computer, you already have the operator: ^.

GF(2): 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. No carry, ever. Multiplication is AND. This is the field binary machines were born into.

Galois fields generalise to GF(pⁿ) for prime p, but XOR only works at base 2 — there are just two states. GF(3) with elements {0, 1, 2} needs modular clock arithmetic (2² mod 3 = 1, not 4). Fine for theory, not what your CPU does natively. Hamming lives in GF(2) because the data is binary.

8. The (15, 11) code and the master bit

For fun fact, in a 15-bit block, only 11 bits carry your message. Four are parity bits (at 1, 2, 4, 8). Position 0 — the 0th bit — is special. It is called the master parity bit.

Its job is the same as the single parity bit from section 3: make the total count of 1s even in the block. The four smaller parity bits then each cover their own subsets, and together they pinpoint a single flipped bit.

Why bother with a master bit if the four checks already locate errors? Because four bits give you 2⁴ = 16 outcomes — enough to name each of the 16 positions, but not enough for a 17th outcome: "nothing is wrong." The master bit handles that. When all five checks pass, you know the block is clean. When only the four subset checks fail but the master says even… that's a different story (two-bit errors — covered at the end).

9. Four checks on a 4×4 grid

Here's the mental model that finally clicked for me. Lay the 16 bits in a grid. Run four parity questions — two about columns, two about rows. Each question splits the grid in half:

Column checks

Row checks

You got the gist? If P₁ says the error is in columns {2, 4} and P₂ says {3, 4}, the only column in both sets is the 4th. Run the row checks the same way and you have a row. Intersection → exact bit.

In standard Hamming notation, bit k participates in parity check P_i if and only if the i-th bit of k's binary representation is 1. The grid view above is the same thing, just folded into rows and columns so you can draw it on paper.

10. Computing parity by hand (the XOR method)

When I was first encoding bits manually, I kept a cheat sheet for which parity bits each cell touches:

• P₁ — columns 2 and 4
• P₂ — columns 3 and 4
• P₄ — rows 2 and 4
• P₈ — rows 3 and 4

Pick a cell, mark yes/no for each parity bit. That gives you a 4-bit pattern. Read it as P₈ P₄ P₂ P₁ (high to low):

R2C4 → P₁ yes, P₂ yes, P₄ yes, P₈ no  →  0011
R3C2 → P₁ yes, P₂ no,  P₄ no,  P₈ yes →  1001
R4C4 → all four yes                   →  1111
R1C2 → P₁ yes only                    →  0001

When multiple data bits are set, XOR their patterns together. Even contributions cancel (GF(2) again), odd ones survive:

Data at R1C4 and R3C2:

  R1C4:  0011
  R3C2:  1001
       ────── XOR
         1010

→ P₁ = 0, P₂ = 1, P₄ = 0, P₈ = 1

11. Try it yourself

Three ways to learn: free play, a click-through guided walkthrough, or an interactive video that plays automatically and pauses for you to check syndrome and fix errors.

Want the actual C++? See the c++ playground tab — same encode/decode logic, runs in the browser: toggle bits, inject noise, see output.

12. Walkthrough: send, corrupt, fix

Let's run the whole pipeline. Message to send: 00110001110 (11 data bits). After placing them in the grid and computing parity, the sender transmits:

The receiver's job:

1. Global check. Total number of 1s is odd → exactly one bit flipped. Time to find it.
2. Column checks. P₁ says columns {1, 3} have odd parity — error is there. P₂ splits {1, 2} (even, clean) vs {3, 4} (odd) → error is in column 3.
3. Row checks. P₄ flags rows {1, 3}; P₈ narrows to {3, 4} vs {1, 2} → error is in row 3.
4. Fix. Row 3, column 3 → index 10. Flip it back. Extract the 11 data bits → 00110001110. Done.

13. The XOR-sum shortcut

There's a faster way to get the error index without walking columns and rows separately. XOR together the positions of every bit that is currently 1 (including parity bits):

clean block — 1s at positions {1, 2, 3, 5, 6, 8, 11}:
  1 ^ 2 ^ 3 ^ 5 ^ 6 ^ 8 ^ 11 = 0   ✓ no error

noise at position 9:
  1 ^ 2 ^ 3 ^ 5 ^ 6 ^ 9 ^ 11 = 9   → flip bit 9 to fix

Why? Each parity bit at position 2ⁱ was chosen so that re-checking produces a syndrome whose binary value is the error location. The XOR of all set positions is the compact version of running those four checks. If the four check results are Q₁=1, Q₂=1, Q₄=1, Q₈=0, read 0111 as binary → position 7.

14. When two bits flip

Single-bit correction is the happy path. What about two?

• First flip toggles the master parity from even → odd.
• Second flip toggles it back odd → even.

The master bit now looks fine — as if nothing happened. But the four subsets still flag an error. That contradiction — master says "all good," subsets say "something's wrong" — is how you detect a two-bit error. You can't correct it (two bits could mimic a single-bit error in a smaller code), but at least you know not to trust the auto-fix. Quite interesting isn't it?

15. Closing thought

Funny, how possibility of finding such ideas, feels almost obvious. We only see the final results and forget the messy process of finding them. Years of confusion, wrong turns someone tried and failed? For me, it's very distinct thinking. Sometimes I wonder if I'll ever have a thought that original in my lifetime.

16. References

Where I picked this up — papers, notes, and videos worth your time:

1. Wikipedia. Hamming code.
2. Hall, J. I. Notes on Coding Theory — Hamming Codes. Michigan State University.
3. Gadiyar, H. G., & Padma, R. (2014). Hamming's Original Paper Rewritten in Symbolic Form: A Preamble to Coding Theory. arXiv:1401.5919.
4. Kekulawala, C. (2024). Hamming Code and Failures in Semiconductor Main Memory. Medium.
5. 3Blue1Brown (2020). But what are Hamming codes? The origin of error correction. YouTube.
6. 3Blue1Brown (2020). Hamming codes part 2: The one-line implementation. YouTube.

note: a few blocks here rephrased with an AI assistant for finding the right word, purely for clearer wording and explanation. the maths, the worked examples, and the playgrounds are the real deal.

My C++ implementation below, so you can toggle bits, inject noise, and watch encode / decode run without a compiler. The logic matches the source line-for-line. Open standalone ↗

#include <iostream>
#include <vector>

using namespace std;

// Hamming (16, 11): indices 1..15, parity at powers of two (1, 2, 4, 8),
// master bit P0 at index 0.

vector<int> encode(const vector<int>& message) {
  vector<int> block(16, 0);
  int msgidx = 0;

  // Fill data slots only — skip parity positions 1, 2, 4, 8.
  // (idx & (idx - 1)) == 0 exactly when idx is a power of two.
  for (int idx = 1; idx < 16; idx++) {
    if ((idx & (idx - 1)) != 0) {
      block[idx] = message[msgidx++];
    }
  }

  // XOR indices of all 1-bits in positions 1..15.
  // The low four bits of that sum become P1, P2, P4, P8.
  int parity_sum = 0;
  for (int idx = 1; idx < 16; idx++) {
    if (block[idx] == 1) {
      parity_sum ^= idx;
    }
  }

  block[1] = parity_sum & 1;
  block[2] = (parity_sum >> 1) & 1;
  block[4] = (parity_sum >> 2) & 1;
  block[8] = (parity_sum >> 3) & 1;

  // P0: even parity over bits 1..15 (overall / master check).
  int p0 = 0;
  for (int idx = 1; idx < 16; idx++) {
    p0 ^= block[idx];
  }
  block[0] = p0;

  return block;
}

vector<int> decode(vector<int>& receivedBlock) {
  // Syndrome from P1..P8: zero means those checks pass.
  int syndrome = 0;
  for (int idx = 1; idx < 16; idx++) {
    if (receivedBlock[idx] == 1) {
      syndrome ^= idx;
    }
  }

  // Total parity over all 16 bits (uses P0 together with syndrome).
  int total_parity = 0;
  for (int idx = 0; idx < 16; idx++) {
    total_parity ^= receivedBlock[idx];
  }

  // Case 1: clean codeword
  if (syndrome == 0 && total_parity == 0) {
    cout << "No error detected" << endl;
  }
  // Case 2: only P0 flipped
  else if (syndrome == 0 && total_parity == 1) {
    cout << "Error in master bit" << endl;
    receivedBlock[0] ^= 1;
  }
  // Case 3: single-bit error at index == syndrome
  else if (syndrome != 0 && total_parity == 1) {
    cout << "single-bit error at position " << syndrome << endl;
    receivedBlock[syndrome] ^= 1;
    cout << "Corrected the error" << endl;
  }
  // Case 4: two-bit error (detect only)
  else {
    cout << "Two bit error detected" << endl;
    return {};
  }

  // Extract the 11 data bits from corrected positions.
  vector<int> message;
  for (int idx = 1; idx < 16; idx++) {
    if ((idx & (idx - 1)) != 0) {
      message.push_back(receivedBlock[idx]);
    }
  }
  return message;
}

void printmsg(const vector<int>& v) {
  for (int bit : v) {
    cout << bit;
  }
  cout << endl;
}

int main() {
  vector<int> message = {1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0};
  cout << "Original msg
";
  printmsg(message);

  auto encoded_data = encode(message);
  cout << "Encoded data is:
";
  printmsg(encoded_data);

  // Single-bit error example:
  // encoded_data[9] ^= 1;

  // Double-bit error (detected, not corrected):
  encoded_data[5] ^= 1;
  encoded_data[10] ^= 1;

  cout << "Received block:
";
  printmsg(encoded_data);
  auto decoded_data = decode(encoded_data);

  if (!decoded_data.empty()) {
    cout << "Received message:
";
    printmsg(decoded_data);
  }
  return 0;
}

Default message matches main(): 10110100110. Try double (5 & 10) then decode — same two-bit test as the source.