Distância de Hamming

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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[editar | editar código-fonte]

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.1 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.2

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[editar | editar código-fonte]

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 ab 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[editar | editar código-fonte]

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.

Algoritmo de exemplo[editar | editar código-fonte]

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.

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

A seguinte função C calculará a distância de Hamming entre dosi 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.

unsigned hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0, val = x ^ y;
 
  // Count the number of set bits
  while(val)
  {
    ++dist; 
    val &= val - 1;
  }
 
  return dist;
}

Ver tambem[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Hamming (1950).
  2. Pilcher, Wong & Pillai (2008).

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]