# Hamming distance

A function on words of fixed length over an alphabet describing the number of changes to the symbols of one word required to reduce it to another. Let $A$ be an alphabet of symbols and $C$ a subset of $A^n$, the set of words of length $n$ over $A$. Let $u=(u_1,\ldots,u_n)$ and $v = (v_1,\ldots,v_n)$ be words in $C$. The Hamming distance $d(u,v)$ is defined as the number of places in which $u$ and $v$ differ: that is, $\sharp\{ i : u_i \neq v_i,\,i=1,\dots,n \}$.

The Hamming distance satisfies $$ d(u,v) \ge 0 \ \text{and}\ d(u,v) = 0\ \text{if and only if}\ u=v\ ; $$ $$ d(u,v) = d(v,u)\ ; $$ $$ d(u,v) \le d(u,w) + d(w,v) \ . $$ Hamming distance is thus a metric on $C$.

In the theory of error-correcting codes it is assumed that words from $C$ are transmitted down a noisy channel and that some symbols are changed during the transmission: see for example the symmetric channel. Maximum likelihood decoding of a received word $r$ consists of finding the word in $C$ nearest to $r$ in the Hamming metric. If the minimum Hamming distance between words of $C$ is $\delta$, then this process is capable of detecting up to $\delta-1$ errors in $r$, and correcting up to $\left\lfloor \frac{\delta-1}{2} \right\rfloor$ errors.

The **Hamming weight** $w(x)$ of a word $x$ over an alphabet containing a distinguished symbol $0$ is the distance $d(\mathbf{0},x)$ where $\mathbf{0}$ is the all-$0$ word. For linear codes in a vector space over a finite field, the distance is determined by the weight: $d(x,y) = w(x-y)$.

#### References

- Goldie, Charles M.; Pinch, Richard G.E.
*Communication theory*, London Mathematical Society Student Texts.**20**Cambridge University Press (1991)**ISBN**0-521-40456-8 Zbl 0746.94001 - van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics
**86**Springer (1992)**ISBN**3-540-54894-7 Zbl 0747.94018

**How to Cite This Entry:**

Hamming distance.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Hamming_distance&oldid=54614