�ݺ�ߣ

© Paolo Quartarone - Codice di Hamming
Codice di HammingCodice di Hamming
Spiegazione
dell'utilizzo della
codifica di Hamming
ITIS Zuccante
2012/2013
1/19

Introduzione
Il Codice di Hammingè un codice correttore lineare
che può rilevare e correggere gli errori di singolo bit.
Per una ricezione corretta di un segnale, la distanza di
Hammingdi ogni bit tra 2 stringhe della stessa
lunghezza deve essere 0. Più è alto questo numero,
minore sarà l'affidabilità dei dati ricevuti.
2/19

3/19© Paolo Quartarone - Codice di Hamming
Errore
L'errore si verifica quando il contenuto di una cella di
memoria è diverso da quello che vi si era scritto in
precedenza.
Può effettuarsi per un disturbo sul canale di
comunicazione ecc..

Distanza di Hamming
La distanza di Hammingtra due stringhe di ugual
lunghezza è il numero di posizioni nelle quali i simboli
corrispondenti sono diversi. Misura il numero di
sostituzioni necessarie per convertire una stringa
nell'altra.
Può essere calcolato eseguendo l'OREsclusivo (XOR)
tra i singoli bit delle due stringhe.

Reticolo di Hamming
Viene utilizzato per esporre in maniera grafica la distanza di Hamming, per ogni lato
dal codice di partenza al codice di arrivo, la distanza di Hamming aumenta.

Distanza di un codice
Si definisce distanza di un codice il minimo numero di
bit in cui 2 qualsiasi parole del codice differiscono.
Quindi se un codice ha distanza d, allora, se d è un
numero dispari, il codice è in grado di rilevare e
correggere (d/2) errori, altrimenti (cioè se d è pari)
esso rileva e corregge (d/2-1) errori e rileva soltanto
(senza correggere) (d/2) errori.

Codici di Hamming
I codici di Hammingsono codici a distanza 3 o 4
contenenti il numero di parole che si
desidera codificare.

Come si ottiene
Il codice di Hammingsi ottiene aggiungendo a
ciascuna stringa di lunghezza m, una stringa di
controllo lunghezza r. Il codice di Hamming sarà
quindi formato da 2 parole ciascuna di
lunghezza (m+r).
In un codice di Hamming a distanza 3 tutti i bit in
posizione p, con p potenza di 2, sono
bit di controllo, gli altri sono bit di informazione.

Esempio
Facciamo un esempio con un codice di
Hamming(11,7).
Ogni code word contiene 7 bit di dati, quindi
occorrono 4 bit di controllo.
Vogliamo inviare la sequenza 1001101
Posizione bit 11 10 9 8 7 6 5 4 3 2 1
Valore bit 1 0 0 x 1 1 0 x 1 x x

I bit di controllo sono nelle posizioni 20
, 21
, 22
, 23
Le xsono i bit di controllo che calcoliamo :
Prendiamo le posizioni dove è presente un 1,
sommiamo assieme in codice binario del numero della
posizione, due a due, utilizzando la XOR:
11 = 1011
7 = 0111
6 = 0110
3 = 0011
risultato: 1001
(Passaggi: 1011 XOR0111 = 1100 ; 1100 XOR0110 =
1010 ; 1010 XOR0011 = 1001 )

Inseriamo in ordine, al posto delle quattro xi quattro
bit :
Posizione bit 11 10 9 8 7 6 5 4 3 2 1
Valore bit 1 0 0 1 1 1 0 0 1 0 1

Adesso il destinatario estrae tutti gli 1 come
fatto prima, da tutte le posizioni :
11 = 1011
8 = 1000
7 = 0111
6 = 0110
3 = 0011
1 = 0001
Risultato : 0000
(Passaggi:1011 XOR 1000 = 0011 ; 0011 XOR
0111 = 0100 ; 0100 XOR 0110 = 0010 0010 XOR
0011 = 0001 ; 0001 XOR 0001 = 0000).
o

Proviamo adesso a sbagliare un bit , diciamo che il bit
in posizione 11 è cambiato da 1 a 0. Essendo 0 ora non
lo metteremo più nel calcolo :
8 = 1000
7 = 0111
6 = 0110
3 = 0011
1 = 0001
1011 = 11d
(posizione del bit errato)

La sequenza 1011 (Sindrome), trasformata in decimale,
indica la posizione del bit errato. Basta allora fare un
XORcon 1 per rimettere le cose a posto.
Bit in posizione 11d
= 0 XOR1 = 1 .
Questo è il caso della parità pari, per la parità
dispari occorre invertire i bit di controllo in
trasmissione (XOR con 1111) prima di inserirli al
posto delle x.
Invertiremo i bit della Sindrome in ricezione per
controllare l’esito della trasmissione.

Parità dispari usando il risultato precedente : 1001 XOR
1111 = 0110
Posizione bit 11 10 9 8 7 6 5 4 3 2 1
Valore bit 1 0 0 0 1 1 0 1 1 1 0
15/19

Inviamo allora la stringa.
11 = 1011
7 = 0111
6 = 0110
4 = 0100
3 = 0011
2 = 0010
Risultato : 1111
(Passaggi:1011 XOR 0111 = 1100 ; 1100 XOR
0110 = 1010 ; 1010 XOR 0100 = 1110 1110 XOR
0011 = 1101 ; 1101 XOR 0010 = 1111 XOR 1111 =
0000).
16/19

Sbagliando, ad esempio il bit in posizione numero 8,
otterremo :
11 = 1011
8 = 1000
7 = 0111
6 = 0110
4 = 0100
3 = 0011
2 = 0010
Risultato : 0111
(Passaggi:1011 XOR1000 = 0011 ; 0011 XOR0111 =
0100; 0100 XOR0110 = 0010 ; 0010 XOR0100 =0110;
0110 XOR0011 = 0101 XOR0010 = 0111)
17/19

A questo punto si effettua la XOR con 11112
e si
ottiene la sindrome : 10002
= 8d
che indica la
posizione del bit errato.
Basta allora fare un XOR con 1 per rimettere le
cose a posto.
Bit in posizione 8d
= 1 XOR 1 = 0.
18/19

Fonti

http://it.wikipedia.org/wiki/Codice_di_Hamming

http://www.galileicrema.it/intraitis/documenti/materialedidattico/c

http://faculty.washington.edu/lcrum/Archives/TCSS372AF08/Hamm

http://en.wikipedia.org/wiki/Hamming_code

Www.uniroma2.it/didattica/infocod/deposito/Informazione_e_Codif

www.ludovico.net/download/materiale_didattico/infogen_bbcc/09_
19/19

�ݺ�ߣ

Codice di Hamming

Recommended

More Related Content

Featured (20)

Codice di Hamming