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)

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 8! 7*8 = = = = 28k k!(n-k)! 2 2!∙6! 2

Quante sono le parole codice di 8 bit aventi distanza di Hamming 2 da una parola di codice assegnata avente la stessa lunghezza?

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

• 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

Codici per il rilevamento degli errori

Bit di parità per burst di erroriUn 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à