Hamming Code : rilevazione e correzione di 1 bit Questo esempio ci mostra la rilevazione e correzione dell’errore di 1 bit . Utilizza le seguenti regole: 1. I bit di

1

Hamming Code : rilevazione e correzione di 1 bit

Questo esempio ci mostra la rilevazione e correzione dell’errore di 1 bit . Utilizza le seguenti regole: 1. I bit di controllo (ridondanti) sono nelle posizioni corrispondenti alle potenze di 2 : 1, 2, 4, 8, 16, 32, 64, etc. (20, 21, 22, 23. ecc.) .Tutte le altre posizioni sono per i dati : 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc. Ogni bit di controllo (parità pari o dispari) controlla un gruppo di bit di dati. Posizione 1 : controlla 1 bit, salta 1 bit, controlla 1 bit, salta 1 bit, etc. (1-3-5-7-9-11-13-15,...) ; Posizione 2: controlla 2 bits, salta 2 bits, controlla 2 bits, salta 2 bits, etc. (2,3--6,7--10,11-- 14,15,...) ; Posizione 4 (è il terzo bit di controllo) : controlla 4 bits, salta 4 bits, controlla 4 bits, salta 4 bits, etc. (4,5,6,7----12,13,14,15----20,21,22,23,...) . Occorre settare il bit di controllo a 1 se il numero totale di 1 nelle posizioni che controlla è dispari; settarlo a 0 se è pari . Una codeword è il risultato della somma dei bit di dati + i bit di controllo . Regola del codice ottimo:

bit_dati+bit_controllo+1 <= 2

; se ad esempio i bit di controllo sono 3 e i bit dei dati 4 (1 nibble) avremo : 4+3+1 <= 2

,Ok . Con 7 bit di dati (ascii standard) e 4 di controllo avremo : 7+4+1 <= 2

Ok.

Diremo allora codice di Hamming (7,4) nel primo caso e codice di Hamming (11,7) nel secondo. Le posizioni dei bit partono da destra .

Esempio : codice Hamming (11,7)

Ogni codeword contiene 7 bit di dati (ascii standard). Occorrono 4 bit di check : codice (11, 7) Vogliamo inviare la sequenza 1001101 (77d , il carattere “ M “)

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

Come abbiamo visto sopra i bit di controllo sono nelle posizioni 2

, 2

, 2

, 2

Le x saranno i bit di check (controllo) e li calcoliamo così:

Prendiamo le posizioni dove c’è un 1 (scritte in binario a 4 bit) e le sommiamo assieme, due a due, con l’algebra Modulo 2 (usiamo cioè le XOR come abbiamo visto per il CRC):

11 = 1011 7 = 0111 6 = 0110 3 = 0011 risultato: 1001

(Passaggi: 1011 XOR 0111 = 1100 ; 1100 XOR 0110 = 1010 ; 1010 XOR 0011 = 1001 ) 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 Inviamo allora la stringa: 10011100101 formata da 11 bit.

Il ricevente estrae gli 1 (come abbiamo fatto prima) però questa volta ci sono anche i check bit; fa il calcolo usando la somma Modulo 2 con le XOR :

Calcolo :

11 = 1011

8 = 1000

7 = 0111

6 = 0110

3 = 0011

2 1 = 0001

0000

(Passaggi:1011 XOR 1000 = 0011 ; 0011 XOR 0111 = 0100 ; 0100 XOR 0110 = 0010 0010 XOR 0011 = 0001 ; 0001 XOR 0001 = 0000).(Se otteniamo 0000 è tutto OK ).

Proviamo adesso a sbagliare un bit , diciamo che il bit in posizione 11 è cambiato da 1 a 0 in seguito ad un disturbo imprevedibile della linea elettrica. Essendo adesso 0 non lo metteremo più nel

calcolo Modulo 2:

8 = 1000 7 = 0111 6 = 0110 3 = 0011 1 = 0001

1011 = 11

(posizione del bit errato). (Sindrome).

La sequenza 1011 (la Sindrome), trasformata in decimale, ci indica la posizione del bit errato. Basta allora fare un XOR con 1 per rimettere le cose a posto.

Bit in posizione 11

= 0 XOR 1 = 1 .

Abbiamo esaminato il caso della parità pari; per la parità dispari occorre invertire i bit di check 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: usiamo 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

Inviamo allora la stringa: 10001101110 formata da 11 bit.

Ricevente:

11 = 1011 7 = 0111 6 = 0110 4 = 0100 3 = 0011 2 = 0010 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).Se otteniamo 0000 è tutto OK , come prima.

Come si vede, questi circuiti (codifica e decodifica di Hamming) possono essere realizzati

completamente con semplici porte XOR.

3 Proviamo adesso a sbagliare un bit , diciamo che il bit in posizione 8 (bit di controllo !) è cambiato da 0 a 1 in seguito ad un disturbo. Essendo adesso 1 lo metteremo nel calcolo Modulo 2:

11 = 1011 8 = 1000 7 = 0111 6 = 0110 4 = 0100 3 = 0011 2 = 0010

(Passaggi:1011 XOR 1000 = 0011 ; 0011 XOR 0111 = 0100; 0100 XOR 0110 = 0010 ; 0010 XOR 0100 =0110; 0110 XOR 0011 = 0101 XOR 0010 = 0111 ; 0111 XOR 1111 ci dà la Sindrome per la parità dispari: 1000

cioè 8 decimale.

Sindrome: 1000

= 8

(posizione del bit errato).

La sequenza 1000

(la Sindrome), trasformata in decimale, ci indica la posizione del bit errato.

Basta allora fare un XOR con 1 per rimettere le cose a posto.

Bit in posizione 8

= 1 XOR 1 = 0.

Si rimanda alla dispensa di Teoria per la spiegazione della Distanza di Hamming alla base di questo

esercizio.