Hamming distance

Hamming distance compares corresponding positions and increments the total whenever their symbols are unequal. If x and y have equal length, their distance is the cardinality of the set of positions i for which x_i differs from y_i. Thus, the distance between 1011101 and 1001001 is two, because the strings disagree in the third and fourth positions.

The measure applies to binary strings, alphabetic text, DNA sequences represented by symbols, and general q-ary strings. It is a metric: it is nonnegative, symmetric, zero only for identical strings, and obeys the triangle inequality. Unlike edit distance, it does not permit insertion, deletion, or movement; positions must remain aligned.

In error-correcting codes, Hamming distance quantifies how far apart valid codewords are in symbol positions. The minimum distance of a code is the smallest distance between any two distinct codewords, and it determines the code's guaranteed resistance to substitution errors.

A code with minimum distance d can detect up to d minus one errors and can uniquely correct up to the floor of one half of d minus one errors. Decoding commonly chooses the codeword nearest to a received word, a procedure called maximum-likelihood decoding for a binary symmetric channel when symbol errors are equally likely. Richard Hamming introduced practical error-detecting and error-correcting codes while working at Bell Telephone Laboratories; his 1950 paper helped establish the field's terminology and methods.

Hamming distance is especially useful when substitutions matter more than insertions or deletions. It supports nearest-neighbor search, binary classification, duplicate detection, quality control, and comparison of fixed-width machine words. In digital communications, a received block can be compared with candidate codewords, while in computer engineering parity bits and syndrome calculations can locate or signal errors without comparing every candidate explicitly.

For binary vectors, Hamming distance equals the number of ones in the bitwise exclusive-or of the vectors, often called the Hamming weight of their difference. This identity makes the operation efficient in hardware and software. The metric also underlies Hamming graphs, whose vertices are strings and whose edges join strings differing in exactly one position; these graphs model single-symbol transitions and appear in combinatorics and network design.¹

Hamming distance has important edge cases that are easy to overlook. It is undefined in its ordinary form for strings of unequal length; padding, truncation, or a different metric must be specified rather than assumed. Its result also depends on symbol representation: two visually identical characters can differ when encoded with distinct Unicode normalization forms, while two different symbols may be treated as equivalent by a domain-specific encoding.

The metric is not always the right model for biological or textual data, where insertions and deletions are common; edit distance or sequence-alignment methods may be more appropriate. Conversely, its strict positional structure is valuable in fixed-length identifiers and codewords. Hamming distance can also be generalized to weighted versions, in which some coordinate errors are more costly than others, although the unweighted form remains the standard definition. The related notion of Hamming weight measures the number of nonzero coordinates in one vector rather than disagreement between two vectors.

Hamming weight

The number of nonzero symbols, usually ones, in a vector or string.

Minimum distance

The smallest Hamming distance between two distinct codewords in a code.

Codeword

A valid encoded string belonging to a specified error-detecting or error-correcting code.

Edit distance

A distance based on insertions, deletions, and substitutions, rather than aligned substitutions alone.