Codice di Hamming

Nelle telecomunicazioni il codice di Hamming è un codice correttore lineare 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 $\left[{\frac {q^{m}-1}{q-1}},{\frac {q^{m}-1}{q-1}}-m,3\right]$ , 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: $2^{n}\geq \ N$ .

Se, $2^{n}\ =\ N$ , 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 $2^{5}\ =\ 32$ 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.

Decimale	Codifica
0	11000
1	10100
2	10010
3	10001
4	01100
5	01010
6	01001
7	00110
8	00101
9	00011

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.

Metodo di costruzione del codice

Legenda:

$n$ , il numero di bit del messaggio originale;
$k$ , il numero di "check" bit (di ridondanza) aggiunti al messaggio originale;
$m=n+k$ , il numero di bit del messaggio finale (cioè il messaggio dopo la codifica con Hamming).

Trovare un valore di K: $n+1\leq 2^{k}-k$ ;
Posizionare i K bit trovati, all'interno del messaggio originale, secondo le potenze del 2 ( $2^{0}=1;2^{1}=2;2^{2}=4;2^{3}=8;....$ , si considerano le potenze in base al valore di K, se K è uguale a tre si prenderanno in considerazione le potenze fino a $2^{2}=4$ );
Trovare il valore dei K:
- Codificare in binario le posizioni dei bit del messaggio finale (ad es. per un messaggio a 6 bit, si numereranno le posizioni dalla prima - 001- alla sesta - 110);
- Si controllano le posizioni in binario di ogni K, facendo attenzione a quale posizione occupa il bit 1 (ad es. nella posizione 1 occupa la posizione più a destra; nella posizione 2, invece, la posizione centrale), e quali digit del messaggio possiedono un 1 nella stessa posizione;
- Si prendono in considerazione i digit trovati e si trova il bit di parità (es. digit1=1, digit2=0,digit3=0; bit di parità=1), il bit di parità corrisponderà al valore di K.

Rilevazione e correzione dell'errore

Una volta codificato il messaggio secondo Hamming, questi arriva al ricevitore il quale lo controlla prima di utilizzarlo dato che a causa dei rumori di segnale il messaggio può subire delle modifiche. Supposto che al ricevitore arrivi un messaggio errato si procede seguendo la regola prima descritta, cioè facendo il bit di parità dei bit legati fra loro dallo stesso K.

Esempio:

Messaggio corretto:

Messaggio Originale: 10

K	Bit di Parità
K1(3,5)	1
K2(3)	1
K3(5)	0

Si ottiene così il messaggio codificato: 11100

Ricevitore

Messaggio ricevuto (errato): 11000

K	Bit di Parità
K1(3,5)	0
K2(3)	0
K3(5)	0

Ottenuti i valori dei K, si esegue l'operazione logica XOR fra i K corrispondenti del messaggio del ricevitore e quelli della sorgente. Si otterrà così una sequenza verticale di numeri binari.

Esempio:

K1 (1) XOR K1r (0)= 1

K2 (1) XOR K2r (0)= 1

K3 (0) XOR K3r (0)= 0

I risultati ottenuti vengono poi letti dal basso verso l'alto ottenendo la posizione in binario del bit errato (nel nostro caso otteniamo 011 (3dec))

Voci correlate

codice Hamming(7,4)
distanza di Hamming
distanza di Levenshtein, una generalizzazione della distanza di Hamming

Altri progetti

Wikimedia Commons contiene immagini o altri file sul codice di Hamming

Collegamenti esterni

(EN) Hamming code, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Eric W. Weisstein, Codice di Hamming, su MathWorld, Wolfram Research.
(EN) Denis Howe, Hamming code, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica

Portale Matematica