Cos’è la distanza di Hamming?

Cos'è? - Miniatura della rubrica di marcogarosi.it

La codifica delle informazioni è una delle sfide di maggior rilievo che si deve affrontare nella progettazione di circuiti digitali. Pensa, ad esempio, alla rappresentazione dei numeri interi (sia positivi che negativi): tra le tante codifiche, le più famose sono quella in modulo e segno e quella in complemento a due. Se stai lavorando con numeri naturali, puoi adottare la sola codifica in modulo. E così via.

È quindi importante formalizzare cosa indica una determinata sequenza di bit in un dato contesto. Successivamente, però, si presenta un ulteriore problema: la gestione degli errori. Un circuito digitale, infatti, può presentare degli errori – soprattutto all’aumentare della complessità delle operazioni e del tempo in cui vengono eseguite.

Quanto sei distante?

Proprio per questo motivo si è iniziato a considerare un nuovo parametro, denominato “distanza di Hamming“. Questa misura, che fa parte della teoria dell’informazione, è stata ideata dal matematico statunitense Richard Wesley Hamming.

Innanzitutto, però, prima di poter parlare di distanza di Hamming, è necessario avere due informazioni – generalmente dette “stringhe” – da comparare. Per semplicità, le chiamiamo “sequenza 1” e “sequenza 2” e assumiamo che siano lunghe 8 bit. Ora, quindi, possiamo confrontarle. La distanza di Hamming tra “sequenza 1” e “sequenza 2” è data dal numero di bit che hanno un valore diverso.

Se stai cercando di capire come si calcoli effettivamente la “distanza” non devi preoccuparti: procediamo subito con un esempio. Se “sequenza 1” è “00000001” e “sequenza 2” è “00000011”, la distanza di Hamming tra le due stringhe è pari a uno. I due valori codificati, rispettivamente, in “sequenza 1” e “sequenza 2”, infatti, differiscono per un solo bit – il penultimo.

Da un punto di vista logico, equivale alla “somma modulo-2“, che i programmatori, solitamente, chiamano “xor” (exclusive or). Guardando alla tabella delle verità ci accorgiamo come l’operatore xor ci restituisca un bit 1 soltanto se i due valori sono differenti:

ABA ⊕ B
000
011
101
110

Eseguendo lo xor bit-a-bit per ogni coppia in posizione n di “sequenza 1” e “sequenza 2” possiamo calcolare la distanza di Hamming in modo più “matematico”.

Il rilevamento degli errori

Ora, probabilmente, ti stai chiedendo perché la distanza di Hamming sia utile per rilevare gli errori. In effetti, a prima vista, sembra solo un numero dalla dubbia utilità. Ovviamente non è così.

Considerala come il numero di sostituzioni da apportare a “sequenza 1” per trasformarla in “sequenza 2”. Se la guardi da questo punto di vista, puoi accorgerti come, in realtà, indichi il numero minimo di errori che hanno portato una delle due sequenze a diventare l’altra.

A cosa serve?

Date queste sue caratteristiche, ha trovato innumerevoli applicazioni. Tra le più importanti:

  • nelle telecomunicazioni serve a contare il numero di bit errati in una sequenza a lunghezza fissa, così da poter calcolare – almeno approssimativamente – l’errore;
  • nella progettazione di circuiti combinatori a due livelli permette – assieme ad altre tecniche (come le mappe di Karnaugh o il metodo di Quine e McCluskey) – di trovare gli implicanti primi più grandi.

Questo importante parametro, tuttavia, presenta una limitazione: non è adatta al confronto di stringhe di lunghezza differente o che presentano cancellazioni e inserimenti al posto delle sole sostituzione. In questi casi, perciò, si tende a ricorrere a tecniche più complesse – sebbene concettualmente simili – che permettono di tenere traccia di ogni modifica subita dalla stringa. Una delle più famose, ad esempio, è la distanza di Levenshtein, ideata dallo scienziato russo Vladimir Levenshtein.