Hamming distance is the number of positions at which two sequences of equal length contain different symbols. It measures the substitutions required to transform one sequence into the other without inserting, deleting, or rearranging symbols. Named after Richard Hamming, it is fundamental to error-correcting codes and is widely used to compare binary strings, categorical records, and encoded data.
Definition and examples
Let and be sequences over the same alphabet . Their Hamming distance is
where the indicator equals when the symbols differ and otherwise.
For example,
differ at the third and fifth positions, so . The definition is not restricted to binary data: the strings karolin and kathrin have Hamming distance .
The alphabet may consist of bits, letters, nucleotide symbols, or categories. The identity of a symbol matters, but its numerical magnitude does not: replacing with contributes the same distance as replacing with .
For sequences of positive length, the normalized Hamming distance is
It lies between and and represents the fraction of mismatching positions. Some software libraries use “Hamming distance” to mean this normalized quantity, so the convention must be checked when interpreting results.
Mathematical properties
For a fixed length , Hamming distance is a metric on . It satisfies:
- Non-negativity: .
- Identity of indiscernibles: exactly when .
- Symmetry: .
- Triangle inequality: .
The triangle inequality follows position by position: if , then at least one of or must hold.
The resulting space is called a Hamming space. For binary sequences, it can be represented as an -dimensional hypercube: vertices are binary strings, and an edge connects strings differing in exactly one position. Hamming distance is then the length of a shortest path along the edges.
Hamming weight
The Hamming weight of a sequence over an alphabet with a designated zero symbol is the number of its nonzero coordinates. For binary strings, it is simply the number of bits.
Binary Hamming distance can therefore be expressed as
where denotes bitwise exclusive OR. For vectors over a finite field, the analogous identity is
For binary vectors regarded as real-valued vectors, Hamming distance also equals their Manhattan distance and their squared Euclidean distance:
These equalities depend on the coordinates being binary; they do not generally hold for arbitrary categorical or numerical data.
Historical development
Hamming distance takes its name from Richard W. Hamming, whose 1950 paper Error Detecting and Error Correcting Codes established foundational results on detecting and correcting errors in digital information. His work at Bell Laboratories connected the construction of codes with the separation between their valid codewords.
Hamming codes became an important family of single-error-correcting codes. Their design illustrates the central principle of distance-based coding: valid messages are represented by strings sufficiently separated that a limited number of symbol errors can be detected or corrected.
The distance subsequently became a standard tool throughout coding theory and in applications involving fixed-position comparisons of discrete data.
Role in error detection and correction
A block code is a set of valid codewords. For a code with at least two codewords, its minimum distance is
This quantity determines its guaranteed protection against symbol substitutions.
Error detection
A code can detect every pattern of at most substitutions if
Fewer than substitutions cannot turn one valid codeword into another. Thus, a received word containing such errors must lie outside the code and can be recognized as invalid.
Error correction
A code can uniquely correct every pattern of at most substitutions if
Equivalently, its guaranteed correction radius is
The reason is geometric: the sets of words within distance of distinct codewords must not overlap. Otherwise, the same received word could be consistent with two transmitted codewords.
For example, the binary repetition code
has minimum distance , so it corrects any single-bit error by majority decoding.
If error locations are known, the affected symbols are called erasures. A code of minimum distance can uniquely recover from up to erasures. More generally, it guarantees unique recovery from substitutions and erasures when
These guarantees concern substitution errors and known erasures, not insertions or deletions.
Hamming balls and the packing bound
A Hamming ball of radius around contains all words whose distance from is at most . Over an alphabet of size , its size is
There are ways to choose the differing positions and ways to replace their symbols.
If a code with codewords corrects every pattern of at most substitutions, its correction balls are disjoint. Consequently,
This is the Hamming bound, also called the sphere-packing bound. It limits how many codewords can fit into a fixed-length space while maintaining a specified correction capability.
Computation
For general sequences, a direct algorithm compares corresponding symbols and counts mismatches. Assuming constant-time symbol comparisons, its time complexity is , with auxiliary space.
For packed binary data, computation typically uses two operations:
- Apply bitwise exclusive OR to the inputs.
- Count the bits in the result.
The second operation is called a population count. Many processors provide instructions for it. If an -bit sequence is stored in machine words of width , the comparison requires word operations when exclusive OR and population count each take constant time per word. Unused padding bits must be excluded.
Large-scale comparisons can exploit vector instructions or parallel computing. Nevertheless, efficiently comparing one pair does not automatically make searching a large collection efficient: finding close matches also depends on the representation and search method.
The unit of comparison matters. A mismatch between two bytes counts as one symbol mismatch in a byte-level calculation, but may represent several differing bits. Likewise, comparing Unicode text by encoded bytes, code points, or user-perceived characters can produce different results.
Applications
Communications and storage
Hamming distance measures separation between valid encoded messages in digital transmission and storage. It supports the analysis of codes designed to resist corruption, including binary block codes and symbol-based systems such as Reed–Solomon codes. For the latter, distance normally counts differing field symbols rather than differing individual bits.
Binary representations and similarity search
In information retrieval and computer vision, objects can be represented by compact binary descriptors. Hamming distance provides a fast way to compare them, making it useful in matching image features and searching collections of binary fingerprints.
The usefulness of the comparison depends on the encoding. A small distance indicates similarity only when the representation has been designed to preserve relevant similarities.
In particular, ordinary cryptographic hashes are not similarity-preserving encodings: similar inputs are not expected to produce nearby hash values.
Machine learning
In machine learning, Hamming distance can compare fixed-length categorical feature vectors. It is also used in multilabel classification, where each label is represented by a binary indicator. The normalized distance between the predicted and true label vectors gives the fraction of incorrectly predicted label indicators, commonly called Hamming loss.
This differs from exact-match evaluation, which treats an entire prediction as incorrect whenever any label differs.
Biological sequences
For equal-length, aligned DNA or protein sequences, Hamming distance counts mismatching positions. It is a simple measure of observed sequence difference, but it does not model insertion and deletion events, repeated substitutions at the same site, or differing probabilities of biological substitutions.
Related measures and limitations
Edit distance
Hamming distance assumes fixed positional correspondence and, in its standard form, equal-length inputs. Edit distance can instead allow insertions, deletions, and substitutions.
For example, abcd and bcda have Hamming distance , but their unit-cost Levenshtein distance is : delete the initial a and insert it at the end. A positional shift can therefore create many Hamming mismatches even when the strings are closely related under an editing model.
Unequal importance of positions
Ordinary Hamming distance assigns the same cost to every mismatch. A weighted version is
For fixed strictly positive weights, this remains a metric. With nonnegative weights that include zeros, distinct sequences can have zero distance, producing a pseudometric.
Neither version automatically captures differences in similarity among symbols: every unequal pair at a given position receives the same penalty.
Representation dependence
Hamming distance measures differences in an encoding, not an intrinsic similarity between the represented objects. Under one-hot encoding, changing one categorical value to another changes two bits, although it changes only one original categorical position.
Likewise, a small numerical change can flip many bits in a binary integer representation. Hamming distance is therefore not generally an appropriate measure of numerical closeness.
Normalization also does not remove all dependence on the alphabet. If two symbols are independently and uniformly drawn from an alphabet of size , their probability of differing is . Expected normalized distances between random strings therefore vary with alphabet size.