Math 2.0

Information and communication theory, circuits Definition

Hamming distance

Builds on AlphabetStringMetric space

Definition

Let Σ\Sigma be a finite alphabet and let n≥1n \ge 1. The Hamming distance of two strings x=x1⋯xnx = x_1 \cdots x_n and y=y1⋯yny = y_1 \cdots y_n in Σn\Sigma^n is dH(x,y)=∣{i∈{1,…,n}:xi≠yi}∣.d_H(x, y) = \abs{\set{i \in \set{1, \dots, n} : x_i \ne y_i}}.

Remarks

Example: dH(10110,11100)=2d_H(10110, 11100) = 2, since the strings differ exactly in positions 22 and 44.

Non-example: the strings 101101 and 1010 have no Hamming distance, because the definition needs strings of the same length. Their edit distance, which also allows insertions and deletions, is 11.

The function dHd_H is a metric on Σn\Sigma^n. The triangle inequality holds because each position where xx and zz differ is a position where xx and yy differ or where yy and zz differ. For binary strings, dH(x,y)d_H(x, y) is the number of ones in x⊕yx \oplus y, the coordinatewise sum modulo 22. In Mathlib the notion is hammingDist.

Reading path

To understand this page from the ground up, read these 18 pages in order. The foundations come first.

Show the path as a graph
Alphabet, concept, no evidence levelAlphabetconceptElement, definition, no evidence levelElementdefinitionProposition, concept, no evidence levelPropositionconceptReal numbers, object, no evidence levelReal numbersobjectString, concept, no evidence levelStringconceptSet, definition, no evidence levelSetdefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionFunction, definition, no evidence levelFunctiondefinitionMetric space, definition, no evidence levelMetric spacedefinitionHamming distance, definition, no evidence levelHamming distancedefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Alphabet concept
  2. Element definition
  3. Proposition concept
  4. Real numbers object
  5. String concept
  6. Set definition
  7. Implication definition
  8. Predicate definition
  9. Ordered pair definition
  10. Existential quantifier definition
  11. Universal quantifier definition
  12. Cartesian product definition
  13. Subset definition
  14. Uniqueness quantifier definition
  15. Binary relation definition
  16. Function definition
  17. Metric space definition
  18. Hamming distance definition

Where this leads

6 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Hamming_distance
About this page
TagK5287V64FH
URIm2://K5287V64FH
Kinddefinition
WritingW0 stub
MSC94B05, 68R15, 68P30
DefinesHamming distance
UsesAlphabet, String, Metric space
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by