Hamming metric
Let
be bit patterns, that is, vectors consisting of zeros and ones.
The Hamming distance defined as
is equal to the number of positions where the bit patterns are differents.
For instance, if and then
because and have different bits at three positions.
The Hamming distance holds the properties of a metric (otherwise it would not be truly a distance):
-
•
for any .
-
•
if and only if .
-
•
for any .
-
•
for any .
If we realize that is counting something (positions where bits differ), then it’s clear that can never be negative. Also, 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 differs at some position from , then differs at the sae position from .
We are left to prove the last condition (trangle inequality). If
then counts at how many places does differ from . For instance, suppose that . This means that the third bits are different, which adds to the whole sum .
Now, if it cannot happen that and at the same , so we have that or . In either case, the sum also increases by one.
So, for each mismatch that increases by one, also increases by one. We conclude that
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 |