Article on other languages:
- Hammingův_kód
- Hamming-Code
- Hamming_code
- Código_Hamming
- Hamming_kode
- Code_de_Hamming
- קוד_המינג
- ハミング符号
- 해밍_부호
- Hamming-code
- Kod_Hamminga
- Código_de_Hamming
- Код_Хемминга
- Hamming_code
- Hamming_kodu
- Mã_Hamming
- 汉明码
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
Nelle telecomunicazioni il codice di Hamming è un codice correttore lineare che prende il nome dal suo inventore Richard Hamming. Il codice di Hamming può rivelare e correggere gli errori di 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 singoli e doppi.
Il codice di Hamming fa parte dei codici lineari, ed i suoi parametri sono ![\left[\frac{q^m-1}{q-1},q^m-m,3\right]](http://upload.wikimedia.org/math/f/2/9/f29c5aca22be85c3621c92e77dadb727.png)
, 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 rivelazione 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.
| 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 1 presente 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 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 il valore di K :
; - Posizionare i K bit trovati, all'interno del messaggio originale, secondo le potenze del 2 (20 = 1;21 = 2;22 = 4;23 = 8;...., si considerano le potenze in base al valore di K, se K è uguale a tre si prenderanno in considerazione le potenze fino a 22 = 4;
- Trovare il valore dei K:
- Codificare in binario le posizioni dei bit del messaggio (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 cosi 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à cosi 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))
Nel caso in cui ad essere sbagliato sia un K, la posizione trovata sarà O, ma l'informazione utile al ricevitore non ha subito modifiche di conseguenza il messaggio è corretto; diversamente, quando la posizione trovata supera i bit vuol dire che nel messaggio sono presenti più di un errore, allora il ricevitore chiede alla sorgente di ri-inviare il messaggio perché questi non riesce a correggere l'errore.
Voci correlate
- codice Hamming(7,4)
- distanza di Hamming
- distanza di Levenshtein, una generalizzazione della distanza di Hamming
