Distância de Hamming
# Distância de Hamming

| cubo binário de 3 bits para determinar a distância de Hamming | Dois exemplos desta distância: 100->011 tem distância 3 (caminho vermelho); 010->111 tem distância 2 (caminho azul) |
| hipercubo cubo binário de 4 bits para determinar a distância de Hamming ||
| Dois exemplos desta distância: 0100->1001 tem distância 3 (caminho vermelho); 0110->1110 tem distância 1 (caminho azul) ||
Na teoria da informação, a distância de Hamming entre duas strings de mesmo comprimento é o número de posições nas quais elas diferem entre si. Vista de outra forma, ela corresponde ao menor número de substituições necessárias para transformar uma string na outra, ou o número de erros que transformaram uma na outra.

## História e aplicações

A distância de Hamming é assim chamada em homenagem a Richard Hamming, que introduziu o conceito em um artigo fundamental sobre códigos de Hamming Error detecting and error correcting codes em 1950. Nas telecomunicações, ela é utilizada para sinalizar erros na transmissão de palavras binárias de comprimento fixo entre um emissor e um receptor, e por isso é algumas vezes chamada de "distância do sinal". Esta forma de análise de bits é usada em várias disciplinas incluindo a teoria da informação, a teoria de códigos e a criptografia. No entanto, para comparar strings de tamanhos diferentes, ou nas quais não apenas substituições mas também inserções e remoções devem ser esperadas, é mais apropriado usar uma métrica mais sofisticada como a distância de Levenshtein.
Para strings q-árias sobre um alfabeto de tamanho q ≥ 2 a distância de Hamming é aplicada no caso da modulação ortogonal, enquanto a distância de Lee é usada para modulação de fase. Se q = 2 ou q = 3 ambas as distâncias coincidem
A distância de Hamming também é usada em sistemática como uma medida da distância genética.
Em uma grade (tal como um tabuleiro de xadrez), os pontos a uma distância de Lee de 1 unidade constituem uma vizinhança de Von Neumann de tal ponto.

## Propriedades especiais

Para um comprimento n fixado, a distância de Hamming é uma métrica no espaço vetorial das palavras daquele comprimento, uma vez que ela obviamente cumpre as condições de ser não negativa, de distinguir apenas palavras que sejam distintas e de simetria, e pode-se mostrar facilmente por indução completa que ela também verifica a desigualdade triangular. A distância de Hamming entre duas palavras a e b também pode ser vista como o peso de Hamming de a − b escolhendo-se o operador − adequadamente.
Para strings binárias a e b, a distância de Hamming é igual ao número de uns em a XOR b. O espaço métrico das strings binárias de comprimento n, com a métrica de Hamming é conhecido como cubo de Hamming; ele é equivalente como espaço métrico ao conjunto das distâncias entre vértices em um grafo hipercubo. Também é possível interpretar uma string binária de comprimento n como um vetor em $R^{n}$ tratando cada símbolo da string como uma coordenada real; com essa imersão, as strings formam os vértices de um hipercubo de dimensão n, e a distância de Hamming entre as strings é equivalente à métrica do taxi entre os vértices.

## Exemplos

A distância de Hamming entre:
* "elabore" e "melhore" é 4.
* 2173896 e 2233796 é 3.
* 11011 e 10011 é 1.
Neste terceiro exemplo, se a cadeia de bits A(11011) fosse emitida e chegasse ao receptor como A'(10011), poderia ser usada a operação XOR da seguinte maneira:
    11011
    XOR 10011
    01000
A quantidade de bits encontrados nessa operação, é a Distância de Hamming entre a palavra transmitida e a recebida. Deste modo, conclui-se que a distância de Hamming entre as strings do exemplo é 1, pois apenas 1 bit foi encontrado após a operação XOR.
Usa-se normalmente esta teoria nos mapas de Karnaugh, servindo para simplificar expressões algébricas usadas para a construção de circuitos.

### Algoritmo de exemplo

A função Python hamming_distance calcula a distância de Hamming entre duas strings (ou outros objetos iteráveis) de mesmo comprimento, criando uma sequência de a zeros e uns indicando diferenças e correspondências entre as posições correspondentes das duas entradas, e então somando a sequência.

#### Python

A seguinte função C calculará a distância de Hamming entre dois inteiros (considerados como valores binários, isto é, como sequências de zeros e uns). O tempo de execução deste procedimento é proporcional à distância de Hamming em vez do número de bits nas entradas. Ela calcula o ou exclusivo bit a bit entre as duas entradas, e então determina o peso de Hamming do resultado (o número de bits não nulos) usando um algoritmo de Wegner (1960) que repetidamente procura e limpa o bit não nulo de menor ordem.