Distanza di Hamming

Nella teoria dell'informazione, la distanza di Hamming tra due stringhe di ugual lunghezza è il numero di posizioni nelle quali i simboli corrispondenti sono diversi. In altri termini, la distanza di Hamming misura il numero di sostituzioni necessarie per convertire una stringa nell'altra, o, vista in altro modo, il numero minimo di errori che possono aver portato alla trasformazione di una stringa nell'altra.

Esempi

• La distanza di Hamming tra 1011101 e 1001001 è 2.
• La distanza di Hamming tra 2143896 e 2233796 è 3.

Il peso di Hamming di una stringa di lunghezza k è la sua distanza di Hamming dalla stringa costituita da k zeri. Quindi è il numero di elementi diversi da zero di una stringa: per una stringa binaria è semplicemente il numero di 1; per esempio, il peso di Hamming di 11101 è 4.

Proprietà

Per una fissata lunghezza ${\displaystyle n}$ la distanza di Hamming è una metrica sull'insieme delle stringhe aventi quella lunghezza, poiché soddisfa le condizioni di non negatività, identità di due elementi aventi distanza nulla, simmetria, e si può dimostrare, mediante induzione completa, che essa soddisfa anche la disuguaglianza triangolare.

La distanza di Hamming tra due elementi ${\displaystyle a}$ e ${\displaystyle b}$ è il peso di Hamming di ${\displaystyle a-b}$, per un'appropriata scelta dell'operatore "${\displaystyle -}$".

Per due stringhe binarie ${\displaystyle a}$ e ${\displaystyle b}$ essa è equivalente all'operazione ${\displaystyle a}$ xor ${\displaystyle b}$. È anche equivalente alla distanza della geometria del taxi tra due vertici di un ipercubo ${\displaystyle n}$-dimensionale, dove ${\displaystyle n}$ è la lunghezza delle stringhe.

Storia e applicazioni

La distanza di Hamming prende il suo nome da Richard Hamming, che la introdusse nel suo fondamentale lavoro sui codici per il riconoscimento e la correzione degli errori. Viene usata nelle telecomunicazioni per contare il numero di bit errati in una parola binaria a lunghezza fissa, allo scopo di stimare l'errore. Per questo motivo viene anche chiamata distanza del segnale. L'analisi del peso di Hamming dei bit viene usata in diverse discipline, tra le quali la teoria dell'informazione, la teoria dei codici e la crittografia. Però, per confrontare stringhe di lunghezze differenti, o stringhe per le quali ci si aspettano anche inserimenti e cancellazioni, oltre alle sostituzioni, è più appropriato usare metriche più sofisticate, come la distanza di Levenshtein.

Bibliografia

• Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2): 147-160, 1950.

Voci correlate

• Codice di Hamming
• Distanza di Levenshtein, una generalizzazione della distanza di Hamming

Collegamenti esterni

• (EN) Eric W. Weisstein, Distanza di Hamming, su MathWorld, Wolfram Research.
• (EN) Distanza di Hamming, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Hamming distance, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL

Portale Informatica

Portale Matematica