CODICE DI HAMMING

You are viewing the theme
[Voti: 0    Media Voto: 0/5]

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},frac{q^m-1}{q-1}-m,3right], 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:  2^n ge  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 1 presente nel codice si altera. Anche questo tipo di codifica individua la presenza ma non la posizione dell’errore.