CODICI
Si ringrazia il prof. Di Santo per aver gentilmente messo a disposizione il proprio materiale per la preparazione di alcune delle
slides presenti in questa dispensa.
Codici Ridondanti
Codici Ridondanti
• Per consentire la rilevazione e la correzione di
errori si ricorre frequentemente a codici
ridondanti, ovvero che utilizzano un numero
maggiore di bit rispetto al numero strettamente
necessario per codificare l’insieme sorgente. Ad
esempio:
– m bit di dati (l’informazione da trasmettere)
– r bit di controllo (bit ridondanti)
– ciascuna parola codice utilizza n = m+r bit
Distanza di Hamming
• La distanza di Hamming di due parole di codice
w1 e w2 è il numero di bit “1” in w1 XOR w2
• Rappresenta il numero di bit da invertire per
trasformare una parola di codice nell’altra
• Ad esempio, se
w1 10001001
w2 10110001
w1 XOR w2 00111000
• la distanza di Hamming tra w1 e w2 è pari a 3
Distanza di Hamming (2)
• Se un codice deve rilevare d errori, la sua distanza di
Hamming deve essere almeno pari a d+1
• Se la distanza fosse minore, un burst di d errori potrebbe
trasformare una parola di codice in un’altra parola di
codice: l’errore non sarebbe rilevato
• Se un codice deve correggere d errori, la sua distanza di
Hamming deve essere almeno pari a 2d+1
• Un burst di d errori al massimo trasforma una parola di
codice in una sequenza di bit a distanza al più d dalla
parola di codice corretta e a distanza almeno d+1 da
tutte le altre parole di codice
Distanza di Hamming (3)
Quante sono le parole codice di 8 bit aventi distanza di Hamming 2 da una
parola di codice assegnata avente la stessa lunghezza?
Occorre numerare tutte le possibili combinazioni semplici di 2 bit su 8.
“Combinazione Semplice”: (fonte Manabile di Matematica :-)
Dati n oggetti distinti e un numero intero positivo k≤n,si dicono combinazioni
semplici di classe k tutti i gruppi che si possonno formare con k degli n oggetti
considerando diversi due gruppi quando differiscono di almeno un elemento.
Numero di combinazioni semplici di k oggetti su n:
n
n!
8
=
k
8!
=
k!(n-k)!
2
7*8
=
2!∙6!
= 28
2
Codici per la correzione degli errori
Replicare i bit di controllo
• Un modo semplice per creare codici a correzione
d’errore consiste nel replicare l’informazione.
• Dato un messaggio di m bit si costruisce una parola di
codice con 2d copie di ciascuno dei bit del messaggio (r
= 2d*m).
• La distanza di Hamming del codice è 2d+1, quindi può
correggere d errori
• Il codice non è efficiente: se d = 2, l’80% dei bit sono
ridondanti.
Codice di Hamming
• Il codice di Hamming (1950) è un
particolare codice a correzione d’errore:
• Consente di correggere 1 singolo errore
• Ha un numero di bit di controllo pari al
limite teorico inferiore (m+1≤2r-r)
• Funziona con qualunque dimensione del
messaggio m
Codice di Hamming (2)
• I bit della parola di codice vengono numerati da sinistra
verso destra cominciando con l’indice 1
• I bit di controllo sono quelli aventi come indice una
potenza di due (1, 2, 4,8, 16, . . . )
• I bit del messaggio sono tutti gli altri bit della parola di
codice, nell’ordine il bit di controllo con indice 2k è il bit di
parità dei bit del messaggio i cui indici hanno il termine
2k nella loro scomposizione in somma di potenze di due
Codice di Hamming (3)
• In ricezione, ciascun bit di controllo viene
ricalcolato:
– Se tutti i valori dei bit di controllo sono corretti,
la parola di codice viene accettata
– Se alcuni bit di controllo hanno valori non
corretti, l’indice del bit in cui si è verificato
l’errore è dato dalla somma degli indici dei bit
di controllo con valore sbagliato
Codice di Hamming – Esempio 1
Codice di Hamming – Esempio 1
Codice di Hamming – Esempio 2
Codice di Hamming – Esempio 3
Codice di Hamming – Esempio 4
Codice di Hamming – Esempio 5
Codice di Hamming – Esempio 6
Codice di Hamming – Esempio 7
Codice di Hamming per burst di errori
Codici per il rilevamento degli errori
• I codici per il rilevamento di errori sono in pratica
più diffusi dei codici per la correzione di errori:
• i codici per il rilevamento sono molto più
efficienti dei codici per la correzione (meno
ridondanza nei bit trasmessi)
• se un codice per la correzione di 1 errore indica
che un bit è errato, vi è una probabilità non
trascurabile che si sia verificato un intero burst di
errori (gli errori tendono ad addensarsi)
Codici per il rilevamento degli errori
Bit di parità per burst di errori
Un metodo per rilevare interi burst di al più k errori basato
sul bit di parità è il seguente:
1. distribuire i bit da trasmettere in una matrice con righe
di k bit
2. per ciascuna colonna, calcolare il relativo bit di parità
3. inviare la prima riga, poi la seconda riga, eccetera
4. inviare come ultima riga i bit di controllo
•
Un burst di al più k errori è sempre rilevato, perchè
modifica al più un bit per ciascuna colonna
•
La probabilità che un burst di p errori (p > k) non venga
rilevato è 1/2p
Il codice fallisce nell’inviduare gli errori doppi che modificano i bit di parità sulla riga i e
colonna j, rilevando erroneamente un errore singolo in posizione i,j.
Al contrario consente di :
• rilevare errori doppi sulla stessa riga (rispettivamente colonna): in tal caso si
rilevano due errori di parità sulle relative colonne (rispettivamente righe).
• correggere errori doppi in posizioni appartenenti a righe e colonne differenti: 4
errori di parità