Codice di Hamming


2+1 bitNella codifica con bit di parità può essere rilevato, ma non corretto, un eventuale errore nel messaggio m (000).

Se il codice errato m' (001) fosse circondato da codici tutti non ammessi (011, 101) tranne m (000) allora sarebbe possibile risalire a m e correggere l'errore...

Distanza di Hamming

La distanza di Hamming di un codice è il numero di bit corrispondenti diversi tra due codici (il numero di errori necessari per passare da una parola all'altra...).

Si deduce la relazione esistente tra distanza del codice e numero di errori rilevabili e correggibili
Numero di erroridistanza per rilevaredistanza per correggere
ee+12e+1
123
235
347
459


Hamming(7,4)

Hamming(7, 4) è un codice con
m=7, lunghezza dei codici
n=4, bit dati
k=3, bit di controllo.

La distanza di Hamming corrispondente è 3: può rilevare e correggere un errore.

Osserva
abcXOR
0000
0011
0101
0110
1001
1010
1100
1111

Il messaggio è costituito da 4 bit dati
d1 d2 d3 d4
e 3 bit di controllo (di parità)
p1=xor(d1,d2,d4)
p2=xor(d1,d3,d4)
p3=xor(d2,d3,d4)
Il messaggio trasmesso è
p1 p2 d1 p3 d2 d3 d4

 
In pratica
Bit dati Bit di
controllo
Messaggio trasmesso
d1d2d3d4 p1p2p3 p1p2 d1p3d2d3d4
0000 000 0000000
0001 111 1101001
.... ... .......
1111 111 1111111


Hamming(7,4)I 3 bit di controllo possono essere interpretati come nella figura a destra
p1 controlla d1, d2, d4
p2 controlla d1, d3, d4
p3 controlla d2, d3, d4
d1 è controllato da p1, p2
d2 è controllato da p1, p3
d3 è controllato da p2, p3
d4 è controllato da p1, p2, p3

Esempio

Sia x=0000 il messaggio da spedire.
Calcolo i bit di controllo
p1=0
p2=0
p3=0
e costruisco m concatenando bit dati e bit di controllo
m=0000000.

1

Ricevo m'=0000001 (c'è stato un errore in d4...).
Calcolo
p1=1, errato
p2=1, errato
p3=1, errato
e dal diagramma rilevo l'errore in d4, perché dipende da p1, p2 e p3.

Ricevo m''=0100000
Calcolo
p1=0
p2=0, errato
p3=0
e dal diagramma rilevo che non esiste un dato che dipende soltanto da p2, quindi è errato proprio p2!

2

Ricevo m'=0000011 (errori in d3 e d4).
Calcolo
p1=1, errato
p2=0
p3=0
Se, per ipotesi, ci può essere un solo errore
dal diagramma rilevo che non esiste un dato che dipende soltanto da p1: è errato p1 (?)
Se si utilizza il codice per rilevare fino a due errori
il messaggio ricevuto è errato!
There are no comments on this page.
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki