Movatterモバイル変換

Codice di Hamming

Da Wikipedia, l'enciclopedia libera.

Questa voce o sezione sugli argomenti matematica e telecomunicazioninon cita le fonti necessarie o quelle presenti sono insufficienti.

Puoimigliorare questa voce aggiungendo citazioni dafonti attendibili secondo lelinee guida sull'uso delle fonti. Segui i suggerimenti delprogetto di riferimento.

Nelletelecomunicazioni ilcodice di Hamming è uncodice correttore lineare che prende il nome dal suo inventoreRichard Hamming. Il codice di Hamming può rilevare e correggere gli errori di un singolo bit. In altre parole, ladistanza 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 deicodici lineari, ed i suoi parametri sono $\left[{\frac {q^{m}-1}{q-1}},{\frac {q^{m}-1}{q-1}}-m,3\right]$ , doveq è la grandezza dell'alfabeto utilizzato (ad esempio 2 se è binario) em è il numero di bit usati.

Ilcodice 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 contieneN informazioni distinte, la rappresentazione in forma binaria di ciascuna di esse avviene utilizzando una parola din 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

[modifica |modifica wikitesto]

Legenda:

$n {\displaystyle n}$ , il numero di bit del messaggio originale;
$k {\displaystyle 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 qualidigit 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

[modifica |modifica wikitesto]

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))