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