© Paolo Quartarone - Codice di Hamming

Codice di HammingCodice di Hamming

Spiegazione dell'utilizzo della

codifica di Hamming

ITIS Zuccante 2012/2013

1/19

© Paolo Quartarone - Codice di Hamming

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 Hamming di 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..

4/19© Paolo Quartarone - Codice di Hamming

Distanza di Hamming

La distanza di Hamming tra 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'OR Esclusivo (XOR)

tra i singoli bit delle due stringhe.

5/19© Paolo Quartarone - Codice di Hamming

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.

6/19© Paolo Quartarone - Codice di Hamming

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.

7/19© Paolo Quartarone - Codice di Hamming

Codici di Hamming

I codici di Hamming sono codici a distanza 3 o 4 contenenti il numero di parole che si

desidera codificare.

8/19© Paolo Quartarone - Codice di Hamming

Come si ottiene

Il codice di Hamming si 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, sonobit di controllo, gli altri sono bit di informazione.

9/19© Paolo Quartarone - Codice di Hamming

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

10/19© Paolo Quartarone - Codice di Hamming

I bit di controllo sono nelle posizioni 20 , 21, 22, 23

Le x sono 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 = 0011risultato: 1001

(Passaggi: 1011 XOR 0111 = 1100 ; 1100 XOR 0110 = 1010 ; 1010 XOR 0011 = 1001 )

11/19© Paolo Quartarone - Codice di Hamming

Inseriamo in ordine, al posto delle quattro x i 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

12/19© Paolo Quartarone - Codice di Hamming

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

13/19© Paolo Quartarone - Codice di Hamming

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)

14/19© Paolo Quartarone - Codice di Hamming

La sequenza 1011 (Sindrome), trasformata in decimale, indica la posizione del bit errato. Basta allora fare un

XOR con 1 per rimettere le cose a posto. Bit in posizione 11

d = 0 XOR 1 = 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.

© Paolo Quartarone - Codice di Hamming

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

© Paolo Quartarone - Codice di Hamming

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

© Paolo Quartarone - Codice di Hamming

Sbagliando, ad esempio il bit in posizione numero 8, otterremo :

11 = 10118 = 10007 = 01116 = 01104 = 01003 = 00112 = 0010

Risultato : 0111

(Passaggi:1011 XOR 1000 = 0011 ; 0011 XOR 0111 = 0100; 0100 XOR 0110 = 0010 ; 0010 XOR 0100 =0110;

0110 XOR 0011 = 0101 XOR 0010 = 0111)17/19

© Paolo Quartarone - Codice di Hamming

A questo punto si effettua la XOR con 11112 e si

ottiene la sindrome : 10002 = 8

d che indica la

posizione del bit errato.Basta allora fare un XOR con 1 per rimettere le

cose a posto. Bit in posizione 8

d = 1 XOR 1 = 0.

18/19

© Paolo Quartarone - Codice di Hamming

Fonti

http://it.wikipedia.org/wiki/Codice_di_Hamming

http://www.galileicrema.it/intraitis/documenti/materialedidattico/codice_hamming_1_2006.doc

http://faculty.washington.edu/lcrum/Archives/TCSS372AF08/Hamming.ppt

http://en.wikipedia.org/wiki/Hamming_code

Www.uniroma2.it/didattica/infocod/deposito/Informazione_e_Codifica_10.pdf

www.ludovico.net/download/materiale_didattico/infogen_bbcc/09_2_errore.ppt

19/19