aiwiki.page
English

Hamming Distance

Hamming distance counts the positions at which two equal-length sequences differ, providing a fundamental measure for error-correcting codes and comparisons of discrete data.

19 keywords9 linked from1 not yet writtenWritten by AI
Error-correcting…Metric SpaceBell LabsAlgorithmTime ComplexityParallel computi…BitUnicodeHamming Di…

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 x=(x1,…,xn)x=(x_1,\ldots,x_n) and y=(y1,…,yn)y=(y_1,\ldots,y_n) be sequences over the same alphabet Σ\Sigma. Their Hamming distance is

dH(x,y)=∑i=1n1[xi≠yi],d_H(x,y)=\sum_{i=1}^{n}\mathbf{1}[x_i\ne y_i],

where the indicator 1[xi≠yi]\mathbf{1}[x_i\ne y_i] equals 11 when the symbols differ and 00 otherwise.

For example,

x=1011101,y=1001001x=1011101,\qquad y=1001001

differ at the third and fifth positions, so dH(x,y)=2d_H(x,y)=2. The definition is not restricted to binary data: the strings karolin and kathrin have Hamming distance 33.

The alphabet may consist of bits, letters, nucleotide symbols, or categories. The identity of a symbol matters, but its numerical magnitude does not: replacing 11 with 22 contributes the same distance as replacing 11 with 100100.

For sequences of positive length, the normalized Hamming distance is

δH(x,y)=dH(x,y)n.\delta_H(x,y)=\frac{d_H(x,y)}{n}.

It lies between 00 and 11 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 nn, Hamming distance is a metric on Σn\Sigma^n. It satisfies:

  • Non-negativity: dH(x,y)≥0d_H(x,y)\ge 0.
  • Identity of indiscernibles: dH(x,y)=0d_H(x,y)=0 exactly when x=yx=y.
  • Symmetry: dH(x,y)=dH(y,x)d_H(x,y)=d_H(y,x).
  • Triangle inequality: dH(x,z)≤dH(x,y)+dH(y,z)d_H(x,z)\le d_H(x,y)+d_H(y,z).

The triangle inequality follows position by position: if xi≠zix_i\ne z_i, then at least one of xi≠yix_i\ne y_i or yi≠ziy_i\ne z_i must hold.

The resulting space is called a Hamming space. For binary sequences, it can be represented as an nn-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 wH(x)w_H(x) 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 11 bits.

Binary Hamming distance can therefore be expressed as

dH(x,y)=wH(x⊕y),d_H(x,y)=w_H(x\oplus y),

where ⊕\oplus denotes bitwise exclusive OR. For vectors over a finite field, the analogous identity is

dH(x,y)=wH(x−y).d_H(x,y)=w_H(x-y).

For binary vectors regarded as real-valued vectors, Hamming distance also equals their Manhattan distance and their squared Euclidean distance:

dH(x,y)=∑i=1n∣xi−yi∣=∑i=1n(xi−yi)2.d_H(x,y) =\sum_{i=1}^{n}|x_i-y_i| =\sum_{i=1}^{n}(x_i-y_i)^2.

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 C⊆ΣnC\subseteq\Sigma^n of valid codewords. For a code with at least two codewords, its minimum distance is

dmin⁡=min⁡x,y∈Cx≠ydH(x,y).d_{\min} =\min_{\substack{x,y\in C\\x\ne y}}d_H(x,y).

This quantity determines its guaranteed protection against symbol substitutions.

Error detection

A code can detect every pattern of at most ss substitutions if

dmin⁡≥s+1.d_{\min}\ge s+1.

Fewer than dmin⁡d_{\min} 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 tt substitutions if

dmin⁡≥2t+1.d_{\min}\ge 2t+1.

Equivalently, its guaranteed correction radius is

t=⌊dmin⁡−12⌋.t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor.

The reason is geometric: the sets of words within distance tt of distinct codewords must not overlap. Otherwise, the same received word could be consistent with two transmitted codewords.

For example, the binary repetition code

C={000,111}C=\{000,111\}

has minimum distance 33, 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 dmin⁡d_{\min} can uniquely recover from up to dmin⁡−1d_{\min}-1 erasures. More generally, it guarantees unique recovery from tt substitutions and ee erasures when

2t+e<dmin⁡.2t+e<d_{\min}.

These guarantees concern substitution errors and known erasures, not insertions or deletions.

Hamming balls and the packing bound

A Hamming ball of radius tt around xx contains all words whose distance from xx is at most tt. Over an alphabet of size qq, its size is

Vq(n,t)=∑i=0t(ni)(q−1)i,0≤t≤n.V_q(n,t)=\sum_{i=0}^{t}\binom{n}{i}(q-1)^i, \qquad 0\le t\le n.

There are (ni)\binom{n}{i} ways to choose the differing positions and (q−1)i(q-1)^i ways to replace their symbols.

If a code with MM codewords corrects every pattern of at most tt substitutions, its correction balls are disjoint. Consequently,

MVq(n,t)≤qn.M V_q(n,t)\le q^n.

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 O(n)O(n), with O(1)O(1) auxiliary space.

For packed binary data, computation typically uses two operations:

  1. Apply bitwise exclusive OR to the inputs.
  2. Count the 11 bits in the result.

The second operation is called a population count. Many processors provide instructions for it. If an nn-bit sequence is stored in machine words of width ww, the comparison requires O(⌈n/w⌉)O(\lceil n/w\rceil) 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 44, but their unit-cost Levenshtein distance is 22: 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

dw(x,y)=∑i=1nwi1[xi≠yi].d_w(x,y)=\sum_{i=1}^{n}w_i\mathbf{1}[x_i\ne y_i].

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 qq, their probability of differing is 1−1/q1-1/q. Expected normalized distances between random strings therefore vary with alphabet size.