Error-Correcting Codes — Mathematics Knowledge System

Overview

Error-correcting codes (ECC) protect data from corruption during transmission or storage by adding structured redundancy. A code C is a set of codewords — bit strings from which the original message can be recovered even if some bits are flipped by noise. Key parameters are the block length n (total bits), dimension k (message bits), and minimum Hamming distance d (minimum number of positions where any two codewords differ). A code with minimum distance d can detect up to d-1 errors and correct up to ⌊(d-1)/2⌋ errors. Linear codes, which form a vector space over GF(2), are the most studied class and include Hamming codes, Reed-Solomon codes, and LDPC codes.

Intuition

Imagine encoding a 1-bit message as either '000' (for 0) or '111' (for 1). If one bit is flipped during transmission, you receive something like '010', which is closer to '000' than '111', so you can correct the error by majority vote. This is the [3,1,3] repetition code. More sophisticated codes spread information across many bits so that errors in any small subset can be identified and corrected. The minimum Hamming distance between codewords determines how many errors can be tolerated — codewords must be far apart so corrupted versions remain closer to the original.

Formal Definition

Definition

A binary linear [n, k, d] code C is a k-dimensional subspace of GF(2)^n with minimum Hamming distance d(C) = min_{c,c'∈C, c≠c'} d_H(c, c').

d_H(x,y) = |\{i : x_i \neq y_i\}|

Hamming distance

d(C) = \min_{\mathbf{c}, \mathbf{c}' \in C,\, \mathbf{c} \neq \mathbf{c}'} d_H(\mathbf{c}, \mathbf{c}')

Minimum distance of code

t = \left\lfloor \frac{d-1}{2} \right\rfloor

Error correction capability

R = k/n

Code rate

d \leq n - k + 1

Singleton bound

Notation

Notation	Meaning
$[n,k,d]$	Code with block length n, dimension k, minimum distance d
$d_H(x,y)$	Hamming distance between strings x and y
$R = k/n$	Code rate (fraction of bits carrying information)
$G$	Generator matrix (k × n)
$H$	Parity-check matrix ((n-k) × n)

Theorems

Theorem 1: Singleton Bound

For any [n,k,d] code over any alphabet, d \leq n - k + 1. Codes achieving equality are called maximum distance separable (MDS) codes.

Theorem 2: Hamming Bound (Sphere-Packing Bound)

For a binary [n,k,d] code correcting t = \lfloor (d-1)/2 \rfloor errors: 2^k \sum_{i=0}^{t} \binom{n}{i} \leq 2^n.

Theorem 3: Gilbert-Varshamov Bound

There exists a binary [n,k,d] code with k \geq n - \log_2 \sum_{i=0}^{d-2} \binom{n-1}{i}. Equivalently, R \geq 1 - H_b(\delta) where \delta = d/n.

Worked Examples

1
Detect up to d-1 = 2 errors.
$\text{detect} = d - 1 = 2 \text{ errors}$
2
Correct up to ⌊(d-1)/2⌋ = ⌊1⌋ = 1 error.
$t = \left\lfloor \frac{3-1}{2} \right\rfloor = 1 \text{ error}$
3
Code rate R = k/n = 4/7.
$R = 4/7 \approx 0.571$

✓ Answer

The [7,4,3] Hamming code detects 2 errors, corrects 1 error, and has rate 4/7 ≈ 57.1%.

Practice Problems

Easyfill in blank

A [15, 11, 3] Hamming code: (a) how many errors can it correct? (b) What is its rate?

Mediumapplication

Explain the trade-off between code rate R and error-correction capability t. Why can't we have both R close to 1 and t large?

Common Mistakes

Common Mistake

Confusing error detection capability (d-1) with error correction capability ⌊(d-1)/2⌋.

A code can detect up to d-1 errors (any error pattern changes the word) but can only correct up to ⌊(d-1)/2⌋ errors (closest codeword is unique).

Common Mistake

Assuming the parity-check matrix H is the same as the generator matrix G.

G is k × n and maps messages to codewords; H is (n-k) × n and checks if a received word is a valid codeword (Hc^T = 0). They satisfy GH^T = 0.

Quiz

Historical Background

Richard Hamming, frustrated by punched-card computers that crashed on single-bit errors at Bell Labs in the 1940s, invented the first single-error-correcting code in 1950. Marcel Golay independently found Golay codes. Reed and Solomon generalized the idea to non-binary alphabets in 1960, creating codes now fundamental to CDs, DVDs, and deep-space communication. The theoretical framework of linear codes over finite fields was developed by many researchers. Modern powerful codes such as LDPC (1963, rediscovered 1996) and turbo codes (1993) approach the Shannon limit.

1948
Shannon's noisy-channel theorem establishes theoretical limits for error correction.
Claude Shannon
1950
Hamming invents the Hamming code, the first single-error-correcting, double-error-detecting code.
Richard Hamming
1960
Reed and Solomon invent Reed-Solomon codes for non-binary alphabets.
Irving Reed, Gustave Solomon
1963
Gallager introduces LDPC codes (sparse parity check codes); largely ignored until 1990s.
Robert Gallager
1993
Berrou et al. invent turbo codes, achieving near-Shannon-limit performance.
Claude Berrou, Alain Glavieux

Summary

An [n,k,d] error-correcting code uses n-bit codewords to encode k-bit messages with minimum Hamming distance d.
A code with minimum distance d detects up to d-1 errors and corrects up to ⌊(d-1)/2⌋ errors.
The Singleton bound d ≤ n-k+1 limits how far apart codewords can be for a given rate; MDS codes (like Reed-Solomon) achieve this bound.
The Hamming bound (sphere-packing) and Gilbert-Varshamov bound bracket the achievable parameters of good codes.

References

BookMacKay, D.J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Part IV.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 7.
WebsiteWikipedia — Error correction code