请输入您要查询的字词:

 

单词 HammingMetric
释义

Hamming metric


Let

x=(x1,x2,x3,,xn),
y=(y1,y2,y3,,yn)

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

The Hamming distanceMathworldPlanetmathPlanetmath dH(u,v) defined as

j=1n|xi-yi|

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

dH(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):

  • dH(x,y)0 for any x,y.

  • dH(x,y)=0 if and only if x=y.

  • dH(x,y)=dH(y,x) for any x,y.

  • dH(x,y)dH(x,z)+dH(z,y) for any x,y,z.

If we realize that dH is counting something (positions where bits differ), then it’s clear that dH can never be negative. Also, dH(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

x=(x1,x2,x3,,xn)
y=(y1,y2,y3,,yn)
z=(z1,z2,z3,,zn)

then dH(x,y) counts at how many places does x differ from y. For instance, suppose that x3y3. This means that the third bits are different, which adds 1 to the whole sum dH(x,y).

Now, if x3y3 it cannot happen that x3=z3 and z3=y3 at the same , so we have that x3z3 or z3y3. In either case, the sum dH(x,z)+dH(z,y) also increases by one.

So, for each mismatch that increases dH(x,y) by one, dH(x,z)+dH(z,y) also increases by one. We conclude that

dH(x,y)dH(x,z)+dH(z,y).
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/3 12:33:16