Hamming Codes — Mathematics Knowledge System

Overview

Hamming codes are a family of linear error-correcting codes invented by Richard Hamming in 1950. The most common is the [7,4,3] code, which encodes 4 message bits into 7 codeword bits using 3 parity-check bits, achieving single-error correction and double-error detection (SECDED with an extra parity bit). Hamming codes are perfect codes — they achieve the Hamming bound with equality, meaning error spheres of radius 1 tile the space perfectly with no wasted space. For redundancy r bits, the Hamming code has parameters [2^r - 1, 2^r - 1 - r, 3]. They are used in ECC RAM and data storage systems.

Intuition

In the [7,4,3] Hamming code, three parity bits are placed at positions 1, 2, and 4 (powers of 2). Each parity bit covers a specific set of data positions. When a bit error occurs, exactly the parity checks covering that position will fail. The binary pattern of failing parity checks gives the binary address of the error — the 'syndrome' points directly to the corrupted bit. It is like a binary search: three yes/no parity checks locate one error in 7 bits, since 2³ - 1 = 7.

Formal Definition

Definition

The [7,4,3] Hamming code is defined by the parity-check matrix H (3×7) whose columns are the binary representations of 1 through 7:

H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}

Parity-check matrix for [7,4,3] Hamming code

\mathbf{s} = H\mathbf{r}^T \pmod{2}

Syndrome computation

\text{Ham}(r) = [2^r - 1,\; 2^r - 1 - r,\; 3]

General Hamming code parameters

2^k \cdot V(n, 1) = 2^n \text{ where } V(n,1) = 1 + n

Hamming code is perfect (achieves equality in Hamming bound)

Notation

Notation	Meaning
$H$	Parity-check matrix
$\mathbf{s}$	Syndrome vector s = Hr mod 2
$[2^r-1, 2^r-1-r, 3]$	Hamming code parameters for r parity bits

Theorems

Theorem 1: Hamming Codes Are Perfect

For every r \geq 2, the Hamming code Ham(r) = [2^r - 1, 2^r - 1 - r, 3] achieves equality in the Hamming bound. The Hamming spheres of radius 1 centered at codewords partition \mathbb{F}_2^n exactly.

Theorem 2: Syndrome Decoding

Let \mathbf{r} = \mathbf{c} + \mathbf{e} be the received word with single-bit error \mathbf{e} = \mathbf{e}_i (error in position i). Then the syndrome \mathbf{s} = H\mathbf{r}^T = H\mathbf{e}_i^T equals column i of H, which is the binary representation of i.

Worked Examples

1
Message bits go to positions 3,5,6,7. Parity bits at positions 1,2,4 must be computed.
$c_3=m_1=1,\ c_5=m_2=0,\ c_6=m_3=1,\ c_7=m_4=1$
2
p₁ (position 1) covers positions 1,3,5,7: p₁ ⊕ c₃ ⊕ c₅ ⊕ c₇ = 0, so p₁ = 1⊕0⊕1 = 0.
$p_1 = c_3 \oplus c_5 \oplus c_7 = 1 \oplus 0 \oplus 1 = 0$
3
p₂ (position 2) covers positions 2,3,6,7: p₂ = c₃ ⊕ c₆ ⊕ c₇ = 1⊕1⊕1 = 1.
$p_2 = c_3 \oplus c_6 \oplus c_7 = 1 \oplus 1 \oplus 1 = 1$
4
p₄ (position 4) covers positions 4,5,6,7: p₄ = c₅ ⊕ c₆ ⊕ c₇ = 0⊕1⊕1 = 0.
$p_4 = c_5 \oplus c_6 \oplus c_7 = 0 \oplus 1 \oplus 1 = 0$
5
Codeword: (p₁,p₂,c₃,p₄,c₅,c₆,c₇) = (0,1,1,0,0,1,1).
$\mathbf{c} = (0,1,1,0,0,1,1)$

✓ Answer

Encoded codeword is 0110011.

Practice Problems

Mediumapplication

Determine the parameters [n, k, d] of the Hamming code with r = 4 parity bits.

Mediumfree response

Explain why Hamming codes are called 'perfect codes' and what that means geometrically.

Common Mistakes

Common Mistake

Thinking the parity-check matrix H and generator matrix G are the same thing.

G (k×n) encodes messages into codewords: c = mG. H ((n-k)×n) verifies codewords: Hc^T = 0. They satisfy GH^T = 0.

Common Mistake

Assuming the syndrome tells you which bit was flipped in the original message, not in the codeword.

The syndrome gives the position of the error in the n-bit codeword, not the k-bit message. After correcting the codeword, you extract the message bits.

Quiz

Historical Background

Richard Hamming worked at Bell Labs in the 1940s on electromechanical computers that frequently crashed due to bit errors in punched cards. The weekend batch-job machines would detect errors and restart from scratch rather than fix them. Hamming, frustrated by wasted computation, set out to devise a code that could automatically locate and correct single-bit errors. His 1950 paper introduced what we now call Hamming codes, along with the concept of Hamming distance.

1948
Hamming develops his coding idea while working on BSTJ computers at Bell Labs.
Richard Hamming
1950
Hamming publishes 'Error Detecting and Error Correcting Codes' in BSTJ.
Richard Hamming
1954
Extended Hamming code (SECDED) developed for practical memory applications.
1970s
Hamming codes adopted for ECC in computer memory (ECC RAM).

Summary

Hamming codes [2^r-1, 2^r-1-r, 3] use r parity bits to protect 2^r-1-r message bits, correcting 1 error and detecting 2 errors.
The syndrome s = Hr^T (mod 2) equals the binary address of the error position — decode by flipping that bit.
Hamming codes are perfect codes: error spheres of radius 1 partition F₂^n exactly, achieving the Hamming bound with equality.
The [7,4,3] Hamming code is the most common instance, with rate 4/7 ≈ 57%; used in ECC RAM.

References

PaperHamming, R.W. (1950). Error Detecting and Error Correcting Codes. Bell System Technical Journal, 29(2), 147-160.
BookMacKay, D.J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Ch. 1.
WebsiteWikipedia — Hamming code