Distància de Hamming

En informàtica, la distància de Hamming entre dues cadenes de la mateixa longitud és el nombre de posicions diferents. Si considerem cadenes de bits, correspon al nombre de bits que s'han de canviar d'una cadena perquè passi a tenir el valor d'una altra cadena.

cub binari de 3 bits per trobar la distància de Hamming

Exemple de dues distàncies: 100→011 té distància 3 (camí vermell); 010→111 té distància 2 (camí blau)

hipercub binari de 4 bitsper trobar la distància de Hamming

Dos exemples de distàncies: : 0100→1001 té distància 3 (camí vermell); 0110→1110 té distància 1 (camí blau)

Exemples

• La distància de Hamming entre 1011101 i 1001001 és 2.
• La distància de Hamming entre 2143896 i 2233796 és 3.
• La distància de Hamming entre "ramer" i "cases" és 3.

En termes de l'operació xor, si considerem a i b definits com segueixen, podem calcular la distància sumant el nombre de bits de a xor b. Això és, a = (0 0 0 1 1 1 1) i b = (1 1 0 1 0 1 1)

aleshores

d = 1 + 1 + 0 + 0 + 1 + 0 + 0 = 3

Propietats

Per a una longitud fixada n, la distància de Hamming és una distància en l'espai vectorial de les paraules d'aquella longitud. Així satisfà:

${\displaystyle \forall a,b\in F:d(a,b)=d(b,a)}$	(simetria)
${\displaystyle \forall a,b\in F:d(a,b)>0}$	(no negativitat)
${\displaystyle \forall a,b\in F:d(a,b)=0\Leftrightarrow a=b}$	(Identitat dels indiscernibles)
${\displaystyle \forall a,b,c\in F:d(a,c)\leq d(a,b)+d(b,c)}$	(desigualtat triangular)

La desigualtat triangular es demostra per inducció.

La distància entre dues paraules a i b es pot veure també com el pes de Hamming de a−b per a una tria adequada de l'operador −.

Per a cadenes binàries a i b, la distància de Hamming és equivalent al nombre d'uns que hi ha en a xor b. L'espai mètric de cadenes binàries de longitud n amb la distància de Hamming és anomenat el cub de Hamming. És equivalent a un espai mètric entre els vèrtexs d'un hipercub. Podem veure cada cadena binària de longitud n com un vector de ${\displaystyle \mathbb {R} ^{n}}$ si tractem cada símbol de la cadena com una coordenada real. Amb aquesta interpretació, les cadenes són vèrtexs del cub n dimensional (un hipercub), i la distància de Hamming de les cadenes és equivalent a la distància de Manhattan entre vèrtexs.