Hamming Distance & Minimum Distance

Counting disagreeing positions, and the distance that bounds correction.

The idea

The Hamming distance measures how far apart two words are, and a code's minimum distance determines how many transmission errors it can correct.

Definition (Hamming distance and minimum distance).

The Hamming distance $d(u, v)$ between two words of the same length is the number of positions where they disagree. The minimum distance of a code $C$ is $d = \min_{u \neq v} d(u, v),$ the minimum taken over all pairs of distinct codewords $u, v$ in $C$.

Equivalently, $d(u, v)$ is the number of single-symbol flips that turn $u$ into $v$. It is a genuine distance: $d(u, v) = 0$ only when $u = v$, it is symmetric, and it satisfies the triangle inequality. For a code $C$, the pair that matters is the closest one, since that is the first pair the channel can confuse, and it fixes the correction guarantee.

Theorem (Error-correction guarantee).

A code of minimum distance $d$ corrects up to $t = \lfloor (d-1)/2 \rfloor$ errors: every word within $t$ flips of a codeword is nearer to that codeword than to any other, so nearest-codeword decoding returns exactly what was sent.

Put a ball of radius $t$ around each codeword, holding every word within $t$ flips of it. Two such balls cannot overlap: a word lying in both would put its two centers within $2t \le d - 1$ of each other, closer than the minimum distance allows. In the space of all $q^{n}$ words of length $n$ over a $q$-symbol alphabet, the balls therefore sit as disjoint islands around the codewords, most words lying in none of them. So a received word within $t$ flips of the sent codeword is nearer to it than to any other codeword, and decoding to the nearest codeword returns exactly what was sent. A code of minimum distance $d$ corrects up to $\lfloor (d-1)/2 \rfloor$ errors.

Ways to work on it

Not sure where to start? Take the ten-question placement test.