Hamming metric

Let

	$\displaystyle x$	$\displaystyle=(x_{1},x_{2},x_{3},\ldots,x_{n}),$
	$\displaystyle y$	$\displaystyle=(y_{1},y_{2},y_{3},\ldots,y_{n})$

be bit patterns, that is, vectors consisting of zeros and ones.

The Hamming distance $d_{H}(u,v)$ defined as

$\sum_{j=1}^{n}|x_{i}-y_{i}|$

is equal to the number of positions where the bit patterns are differents.

For instance, if $u=(0,1,1,0,1,0,1)$ and $v=(1,0,1,0,1,0,1)$ then

$d_{H}(u,v)=|0-1|+|1-0|+|1-1|+|0-0|+|1-1|+|0-0|+|1-1|=3$

because $u$ and $v$ have different bits at three positions.

The Hamming distance holds the properties of a metric (otherwise it would not be truly a distance):

•

$d_{H}(x,y)\geq 0$ for any $x, y$ .
•

$d_{H}(x,y)=0$ if and only if $x=y$ .
•

$d_{H}(x,y)=d_{H}(y,x)$ for any $x, y$ .
•

$d_{H}(x,y)\leq d_{H}(x,z)+d_{H}(z,y)$ for any $x, y, z$ .

If we realize that $d_{H}$ is counting something (positions where bits differ), then it’s clear that $d_{H}$ can never be negative. Also, $d_{H}(x,x)=0$ because a bit pattern has no different bits respect to itself, and if two bit patterns coincide on each position, they are indeed the same pattern, which proves the second property. The third condition also follows from the trivial fact that if $x$ differs at some position from $y$ , then $y$ differs at the sae position from $x$ .

We are left to prove the last condition (trangle inequality). If

	$\displaystyle x$	$\displaystyle=(x_{1},x_{2},x_{3},\ldots,x_{n})$
	$\displaystyle y$	$\displaystyle=(y_{1},y_{2},y_{3},\ldots,y_{n})$
	$\displaystyle z$	$\displaystyle=(z_{1},z_{2},z_{3},\ldots,z_{n})$

then $d_{H}(x,y)$ counts at how many places does $x$ differ from $y$ . For instance, suppose that $x_{3}\neq y_{3}$ . This means that the third bits are different, which adds $1$ to the whole sum $d_{H}(x,y)$ .

Now, if $x_{3}\neq y_{3}$ it cannot happen that $x_{3}=z_{3}$ and $z_{3}=y_{3}$ at the same , so we have that $x_{3}\neq z_{3}$ or $z_{3}\neq y_{3}$ . In either case, the sum $d_{H}(x,z)+d_{H}(z,y)$ also increases by one.

So, for each mismatch that increases $d_{H}(x,y)$ by one, $d_{H}(x,z)+d_{H}(z,y)$ also increases by one. We conclude that

$d_{H}(x,y)\leq d_{H}(x,z)+d_{H}(z,y).$

Title	Hamming metric
Canonical name	HammingMetric
Date of creation	2013-03-22 14:59:37
Last modified on	2013-03-22 14:59:37
Owner	drini (3)
Last modified by	drini (3)
Numerical id	7
Author	drini (3)
Entry type	Definition
Classification	msc 05C12
Classification	msc 94C99
Synonym	Hamming distance
Synonym	Hamming metric
Related topic	HammingDistance