codice di Hamming

Nelle telecomunicazioni il codice di Hamming è un codice correttorelineare che prende il nome dal suo inventore Richard Hamming. Il codice di Hamming può rilevare e correggere gli errori di un singolo bit. In altre parole, la distanza di Hamming tra le code-word trasmesse e ricevute deve essere zero o uno per una comunicazione affidabile. In alternativa, il codice può rivelare (ma non correggere) errori doppi. Il codice di Hamming fa parte dei codici lineari, ed i suoi parametri sono , dove q è la grandezza dell'alfabeto utilizzato (ad esempio 2 se è binario) e m è il numero di bit usati. Il codice di parità consente la rilevazione dell'errore ma non la sua correzione. Aumentando la ridondanza nel messaggio (aggiunta di bit per la rivelazione e la correzione degli errori) è possibile conoscere anche la posizione del bit errato e quindi correggerlo. Il codice di Hamming fornisce questa possibilità. Se un codice contiene N informazioni distinte, la rappresentazione in forma binaria di ciascuna di esse avviene utilizzando una parola di n bit in modo che si verifichi: . Se, , un errore in uno o più bit porta ad una configurazione binaria diversa che corrisponde, però, sempre ad un dato appartenente allo stesso codice: in pratica non si riesce a comprendere se vi è stato un errore o meno. Ad esempio, supponiamo di voler codificare le cifre decimali da 0 a 9 utilizzando 5 bit. Con 5 bit sono possibili configurazioni differenti di cui solo 10 saranno utilizzate. Se vi è un errore il dato potrebbe assumere una delle altre 22 configurazioni e sarà, quindi, possibile rivelare un errore. Si noti che per la codifica delle 10 cifre decimali sarebbero necessari solo 4 bit. Il quinto bit è ridondante. Resta da definire la modalità di codifica. Un buon criterio è quello che associa ad ogni cifra decimale una configurazione binaria in cui sono presenti sempre due 1 e tre 0 (o viceversa) come nella seguente tabella. Si noti che se si verifica un errore il numero di 1 presenti nel codice si altera. Anche questo tipo di codifica individua la presenza ma non la posizione dell'errore.