Visualizza wikitesto di Codice di Hamming

{{F|matematica|arg2=telecomunicazioni|febbraio 2013}}
Nelle [[telecomunicazioni]] il '''codice di Hamming''' è un [[Forward Error Correction|codice correttore]]
[[codice lineare|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 [[codice lineare|codici lineari]], ed i suoi parametri sono <math>\left[\frac{q^m-1}{q-1},\frac{q^m-1}{q-1}-m,3\right]</math>, dove ''q'' è la grandezza dell'alfabeto utilizzato (ad esempio 2 se è binario) e ''m'' è il numero di bit usati.

Il [[bit di parità|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: <math> 2^n \ge \ N</math>.

Se, <math>2^n\ = \ N</math>, 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 <math> 2^5\ =\ 32</math> 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.

{| align=center border=1
! 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:
* <math>n</math>, il numero di bit del messaggio originale;
* <math>k</math>, il numero di "check" bit (di ridondanza) aggiunti al messaggio originale;
* <math>m=n+k</math>, il numero di bit del messaggio finale (cioè il messaggio dopo la codifica con Hamming).

# Trovare un valore di K: <math>n+1 \le 2^k - k</math>;
# Posizionare i K bit trovati, all'interno del messaggio originale, secondo le potenze del 2 (<math>2^0=1; 2^1=2; 2^2=4; 2^3=8;....</math>, si considerano le potenze in base al valore di K, se K è uguale a tre si prenderanno in considerazione le potenze fino a <math>2^2=4</math>);
# 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'''
{| align=center border=1
! K!! Bit di Parità
|- 
| K1(3,5) 
| 1
|-
| K2(3)
|1
|-
| K3(5)
| 0
|-
|-
|}
Si ottiene così il messaggio codificato: 11'''1'''0'''0'''

''Ricevitore''

Messaggio ricevuto (errato): 11000
{| align=center border=1
! 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 ==
{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|Hamming code|Hamming code}}

{{Portale|matematica|informatica}}

[[Categoria:Teoria dei codici]]
[[Categoria:Logica matematica]]