From ISBN to Hamming Codes: Smarter Error Correction

DC1 Nihan Tanisali, INRIA, France.

In our previous post, we introduced the basic idea of coding theory: adding redundancy (check digit) to protect information from errors. But we didn’t actually build a real error-correcting code yet. In this post, we take the first real step — starting from the humble ISBN and ending with one of the most beautiful constructions in coding theory: the Hamming code.

Previously, we looked at the ISBN code and saw how a single check digit can detect errors, and sometimes even correct them (if we already know the position of the error). We start by reviewing the ISBN code.

ISBN as an Error-Detecting Code

An ISBN is a 13-digit number

a₁a₂a₃ — a₄a₅ — a₆a₇ — a₈a₉ — a₁₀a₁₁a₁₂ — a₁₃

and it is valid if the following weighted sum ends with zero:

S = a₁ + 3a₂ + a₃ + ⋯ + 3a₁₂ + a₁₃

Example: The book Algebraic Function Fields and Codes has the ISBN code:

978–35–40–76–878–4

Suppose a librarian types this ISBN, but one digit is unreadable:

They know the tenth digit must be either 3 or 8. They try to enter the code with 3 in the tenth digit:

ISBN(1) = 978–35–40–76–378–4, S(1) = 135 (invalid).

With 8:

ISBN(2) = 978–35–40–76–878–4 S(2) = 150 (valid).

Thus, the check digit reveals the correct version.

The Limitations

The previous examples succeed because the uncertainty is limited: we effectively know where the digit might be wrong, so the check equation can single out one valid candidate. In coding theory, this corresponds to a setting where unique decoding holds. The following example highlights the limitation of ISBN when the error position is not known in advance.

Consider the ISBN code

978–35–40–76–873–4.

There is an error as

(a₁,a₂,a₃,a₄,a₅,a₆,a₇,a₈,a₉ ,a₁₀,a₁₁,a₁₂,a₁₃) =(9,7,8,3,5,4,0,7,6,8,7,3,4),

S = a₁ + 3a₂ + a₃ + 3a₄ + a₅ + 3a₆ + a₇ + 3a₈ + a₉ + 3a₁₀ + a₁₁ + 3a₁₂ + a₁₃
= 9 + 3·7 + 8 + 3·3 + 5 + 3·4 + 0 + 3·7 + 6 + 3·8 + 7 + 3·3 + 4
= 135

However, assuming that the error is in either the 9th, the 10th, or the 12th digit yields three different books, as illustrated in the figure.

Practically, this means that correcting a mistyped ISBN cannot be done reliably from the check digit alone: multiple candidate ISBNs may satisfy the checksum, leading to ambiguity.

Finally, let’s formalize ISBN as a code:

Message length: k=12

Codeword length: n=13

Rate: 12/13

Error correction (number of unknown positions): 0

So, ISBN is essentially an error-detecting code, not a general error-correcting code.

Detection is nice, but correction is the real goal of coding theory! The simplest way to enable correction is to add redundancy: by repeating each bit, that is the repetition code.

Repetition Code as an Error-Correcting Code

A naïve approach to correcting errors is repetition: send each bit three times.

• Encode 0 as 000, 1 as 111.

• At the receiver, decode by majority vote.

This works: even if one bit flips, the majority still gives the correct value.

The Limitations of the Repetition Code

But it’s wasteful. We triple the data just to correct one error.

Message length: k=1

Codeword length: n=3

Rate: 1/3

Error correction (unknown positions): 1

Repetition codes achieve error correction by brute-force redundancy, but the cost (codeword length) grows quickly. Richard Hamming’s idea was that we can place parity bits more cleverly, so we can detect and correct errors with far less redundancy. Now, we give the construction of the (7,4) Hamming code and show how syndrome decoding locates a single-bit error.

The Hamming (7,4) Code

The simplest nontrivial Hamming code is the (7,4) code:

Message length: k=4 bits

Codeword length: n=7 bits

Rate: 4/7

Error correction: can correct 1 error in any position, without knowing where it happened.

Encoding

Take four message bits:

m = (m₁, m₂, m₃, m₄).

The aim is to encode them into a length-7 codeword:

c = (c₁, c₂, c₃, c₄, c₅, c₆, c₇)

Hamming’s key idea is to reserve a few positions for parity bits that act as consistency checks.

In the (7,4) Hamming code, the parity bits are placed at the power-of-two indices 1,2,4,

and the four message bits fill the remaining positions 3,5,6,7. Concretely,

c₃ = m₁, c₅ = m₂, c₆ = m₃, c₇ = m₄

so the codeword looks like

c = (c₁, c₂, c₃, c₄, c₅, c₆, c₇) = (c₁, c₂, m₁, c₄, m₂, m₃, m₄).

What do the parity bits (that is c₁, c₂, c₄) do? Each parity bit is chosen so that, on a certain subset of positions, the total number of 1’s is even (this is called even parity).

Equivalently, the XOR of the bits in that subset is 0:

c₁ ⊕ c₃ ⊕ c₅ ⊕ c₇ = 0,

c₂ ⊕ c₃ ⊕ c₆ ⊕ c₇ = 0,

c₄ ⊕ c₅ ⊕ c₆ ⊕ c₇ = 0.

Finally, the parity bits are given by the following equalities:

c₁ = m₁ ⊕ m₂ ⊕ m₄,

c₂ = m₁ ⊕ m₃ ⊕ m₄,

c₄ = m₂ ⊕ m₃ ⊕ m₄.

Now to visualize the mechanism here, we think the sets that each parity bit check, that is

c₁ checks {c₁, c₃, c₅, c₇}, c₂ checks {c₂, c₃, c₆, c₇}, c₄ checks {c₄, c₅, c₆, c₇}.

These three sets intersects as in the following figure:

Example Encoding

Let’s encode the message:

m = (m₁, m₂, m₃, m₄) = (1, 0, 1, 1).

Place message bits such that

c₃ = m₁ = 1, c₅ = m₂ = 0, c₆ = m₃ = 1, c₇ = m₄ = 1,

That is to say

(c₁, c₂, 1, c₄, 0, 1, 1).

Now we compute parity bits:

c₁ checks positions 1,3,5,7 → c₁ = m₁ ⊕ m₂ ⊕ m₄ = 1 ⊕ 0 ⊕ 1 = 0.

c₂ checks positions 2,3,6,7 → c₂ = m₁ ⊕ m₃ ⊕ m₄ = 1 ⊕ 1 ⊕ 1 = 1.

c₄ checks positions 4,5,6,7 → c₄ = m₂ ⊕ m₃ ⊕ m₄ = 0 ⊕ 1 ⊕ 1 = 0.

So the encoded codeword is:

c = (0, 1, 1, 0, 0, 1, 1).

Decoding and Error Correction

When a message is sent over a noisy channel, the received word may differ from the original codeword by a few flipped bits. The goal of decoding is to detect whether an error occurred and, if possible, locate and fix it. In Hamming(7,4), this is done using the parity-check matrix H:

By multiplying the received word r with H, we obtain a vector of length 3 that reveals whether the word is still consistent with the code. If the resulting vector is (0,0,0), then r passes all parity checks, so r is treated as a valid Hamming(7,4) codeword, and no error is detected. The decoded message is obtained by reading off the four information bits from r. That is when r = (r₁, r₂, r₃, r₄, r₅, r₆, r₇), then the message is simply ( r₃, r₅, r₆, r₇), i.e., the four information bits of r.

Remember our example codeword is

c = (0,1,1,0,0,1,1).

Suppose during transmission the fourth bit of c flips and we get:

r = c+e₄ = (0,1,1,0,0,1,1) + (0,0,0,1,0,0,0) = (0,1,1,1,0,1,1).

To decode, we use the parity-check matrix H:

The parity-check result is:

The resulting vector is (1,0,0), and the number “100” gives 4 in binary, indicating that the 4th bit is wrong. Flipping it back, we recover the original codeword.

Suppose during transmission the third bit of c flips. Then

r=c+e₃ =(0,1,1,0,0,1,1)+(0,0,1,0,0,0,0)=(0,1,0,0,0,1,1).

Then, we compute:

Thus s=(0,1,1), which is 011 in binary, i.e. 3. This indicates that the 3rd bit is wrong. Once again, flipping it back, we recover the original codeword.

You can try generating valid codewords, and then flipping one bit. This method will always detect where the error is.

How does the Magic Work?

This is not magic; it comes from how we label the coordinates. Number the seven positions by 1,2,…,7 and write each index in binary:

1=001, 2=010, 3=011, 4=100, 5=101, 6=110, 7=111.

Hamming chooses three parity checks, one for each binary digit: 1,2,4.

Now take a message

m = (m₁, m₂, m₃, m₄)

and the corresponding codeword

c = (m₁ ⊕ m₂ ⊕ m₄, m₁ ⊕ m₃ ⊕ m₄, m₁, m₂ ⊕ m₃ ⊕ m₄, m₂, m₃, m₄).

Then

Substituting the coordinates of c, we obtain

c₄ ⊕ c₅ ⊕ c₆ ⊕ c₇ = (m₂ ⊕ m₃ ⊕ m₄) ⊕ m₂ ⊕ m₃ ⊕ m₄ = 0,

c₂ ⊕ c₃ ⊕ c₆ ⊕ c₇ = (m₁ ⊕ m₃ ⊕ m₄) ⊕ m₁ ⊕ m₃ ⊕ m₄ = 0,

c₁ ⊕ c₃ ⊕ c₅ ⊕ c₇ = (m₁ ⊕ m₂ ⊕ m₄) ⊕ m₁ ⊕ m₂ ⊕ m₄ = 0.

Hence, for any valid codeword c,

Hcᵀ = (0, 0, 0).

Now suppose a single-bit error flips position j. Then the received word is r = c + eⱼ, where eⱼ has a 1 only in coordinate j. Its syndrome is

s = Hrᵀ = H(c + eⱼ)ᵀ = Hcᵀ + Heⱼᵀ = 0 + Heⱼᵀ = Heⱼᵀ.

But Heⱼᵀ is just the j-th column of H, and by construction that column records exactly which of the three binary digits of j are 1. In other words, s is the binary representation of the error position.

So the syndrome immediately tells us which bit flipped, and we correct by flipping that bit back.

Why do Hamming Codes Matter?

ISBN highlights the power of a single check digit: it can detect common errors cheaply, even though it cannot correct them. Repetition codes show the opposite extreme — enough redundancy can correct errors, but very inefficiently. Hamming codes sit in between: with carefully placed parity checks, they enable efficient, automatic single-error correction.

More precisely, fix the block length n=7. The length-7 repetition code can correct up to 3 errors by majority vote, but it carries only 1 information bit (rate 1/7). In contrast, the (7,4) Hamming code corrects 1 error, but it carries 4 information bits (rate 4/7). Thus, repetition achieves stronger error tolerance through extreme redundancy, while Hamming achieves much higher efficiency: it targets the most common case — a single error — with minimal overhead, using the syndrome to identify the flipped position immediately.

Together, these examples offer a first glimpse of a much larger world: linear codes, generator and parity-check matrices, and geometric viewpoints on error correction in which distance and algebraic structure determine what can be reliably recovered.