Cos’è la distanza di Hamming?

Distanza di Hamming

La distanza di Hamming è una metrica per confrontare due stringhe di dati binari. Quando si confrontano due stringhe binarie di uguale lunghezza, la distanza di Hamming è il numero di posizioni di bit in cui i due bit sono diversi.

La distanza di Hamming tra due stringhe, a e b è indicata come d(a,b).

E’ usata per l’individuazione o la correzione degli errori quando i dati sono trasmessi su reti di computer. Si usa anche nella teoria della codifica per confrontare parole di dati di uguale lunghezza.

Calcolo della distanza di Hamming

Per calcolare la distanza di Hamming tra due stringhe e , eseguiamo la loro operazione XOR, (a⊕ b), e poi contiamo il numero totale di 1 nella stringa risultante.

Esempio

Supponiamo che ci siano due stringhe 1101 1001 e 1001 1101.

11011001 ⊕ 10011101 = 01000100. Poiché, questo contiene due 1, la distanza di Hamming, d(11011001, 10011101) = 2.

Distanza minima di Hamming

In un insieme di stringhe di uguale lunghezza, la distanza minima di Hamming è la più piccola distanza di Hamming tra tutte le possibili coppie di stringhe in quell’insieme.

Esempio

Supponiamo ci siano quattro stringhe 010, 011, 101 e 111.