Hamming distance

Updated About encyclopedia.com content Print Article Share Article
views updated

Hamming distance (Hamming metric) In the theory of block codes intended for error detection or error correction, the Hamming distance d(u, v) between two words u and v, of the same length, is equal to the number of symbol places in which the words differ from one another. If u and v are of finite length n then their Hamming distance is finite since d(u, v) ← n

It can be called a distance since it is nonnegative, nil-reflexive, symmetric, and triangular:

0 ← d(u, v)

d(u, v) = 0 iff u = v

d(u, v) = d(v, u)

d(u, w) ← d(u, v) + d(v, w)

The Hamming distance is important in the theory of error-correcting codes and error-detecting codes: if, in a block code, the codewords are at a minimum Hamming distance d from one another, then

(a) if d is even, the code can detect d – 1 symbols in error and correct ½d – 1 symbols in error;

(b) if d is odd, the code can detect d – 1 symbols in error and correct ½(d – 1) symbols in error.

See also Hamming space, perfect codes, coding theory, coding bounds, Hamming bound.