Controllo e correzione degli errori

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria

Università degli Studi di Udine

Controllo e correzione degli errori

Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte dell’autore.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono

mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Ridondanza

• La memorizzazione/trasmissione dei dati è soggetta ad errori

• Si possono aggiungere ai dati informazioni ridondanti per:

– controllarne la correttezza

– correggere (quando possibile) gli errori

dati

in fase di codifica (o memorizzazione o trasmissione)

CRC

dati CRC

Nell’esempio:

Cyclic Redundancy Check = f (dati)

f (dati)

f (dati)

dati CRC

CRC

= ?

i dati ricevuti sono corretti se possibile si correggono

i bit errati, altrimenti si segnale l’errore

in fase di decodifica (o lettura o ricezione)

NO SÌ

Alcune tecniche

• Parità

– solo controllo

• Somma di blocco

– controllo e correzione

• Codici polinomiali

– solo controllo

• Codici di Hamming

– controllo e correzione

• Codici a convoluzione

– controllo e correzione

Parità

• Ad ogni dato (es. 1 codice ASCII su 7 bit) viene aggiunto un bit tale che il

numero totale di bit a 1 sia sempre pari

(“parità pari”) o sempre dispari (“parità

dispari”)

Esempio: parità pari

0000000 0 0000001 1 1001101 0 0111011 1

bit di parità 0 1 1 1 0 1 1 1

P = A ₁ A ₂ ... A _n

Distanza di Hamming

• Numero minimo di bit in cui differiscono due parole del codice (dato +

informazione ridondante) valide

• Nella tecnica di parità:

– distanza di Hamming = 2 (almeno due bit differenti)

– quindi lo schema individua errori singoli e

non doppi

Distanza di Hamming

• Distanza di Hamming dell’intero codice:

HD = min { HD di tutte le possibili coppie di parole del codice }

• Per rilevare k errori HD del codice deve essere k+1

• Per correggere k errori HD del codice

deve essere 2k+1

Somma di blocco

• Opera su blocchi di dati con parità

(detta trasversale o “di riga”, relativa a ciascun dato)

• Si aggiunge al termine del blocco una serie di di bit di parità relativi ai bit di una data posizione in tutti i dati del blocco (parità longitudinale o “di

colonna”)

Esempio: parità pari

0000000 0 0000001 1 1001101 0 0111011 1 0001100 0 1010101 0 1111101 0 1111111 1 0101100 1

bit di parità di riga

bit di parità di colonna

(con errore di lettura e correzione)

0000000 0 0000001 1 1001101 0 0111011 1 0101100 0 1010101 0 1111101 0 1111111 1 0101100 1

errore

errore

0000000 0

0000001 1

1001101 0

0111011 1

0101100 0

1010101 0

1111101 0

1111111 1

0101100 1

• Codici adatti nel caso di errori “a burst”

(danneggiano più bit consecutivi)

– Si definisce uno schema di n+1 bit detto generatore (G), comune a trasmettitore e ricevitore

– Si aggiungono al messaggio M (lungo k bit) n bit tali che i k+n bit trasmessi siano

divisibili per G (in aritmetica modulo 2)

Gli r bit aggiunti sono detti FCS (Frame Check

Sequence) o CRC (Cyclic Redundancy Check)

Codici polinomiali

• Il calcolo del CRC si basa su alcune proprietà dell’aritmetica modulo 2:

– non ci sono riporti nelle addizioni – non ci sono prestiti nelle sottrazioni

– addizioni e sottrazioni sono identiche e coincidono con l’operazione di EXOR

• Di conseguenza, A + A = 0

Divisione modulo 2

• La divisione in aritmetica modulo due procede come in aritmetica decimale, ma con EXOR al posto delle sottrazioni

• Il divisore “sta dentro” il dividendo se il

dividendo ha tanti bit quanti il divisore

Divisione modulo 2

1011 : 10 = 101 10

-- 0011

10 --

01 resto

il parziale corrente (001) ha meno bit significativi del divisore:

aggiungo uno zero al quoziente

NOTA: in generale, il

risultato di una divisione modulo due non coincide con il risultato

della divisione

normale

Proprietà della divisione modulo 2

) (

) ) (

) ( (

2 )

(

x G

x x R

x Q G

x

M ⁿ

+

⋅ = nell’aritmetica modulo

2 la somma di due

numeri uguali dà zero, quindi:

) (

) ( )

( ) ) (

) ( (

) ( )

(

2 )

(

x G

x R x

G x x R

x Q G

x R x

G x

M ⁿ

+ +

=

⋅ +

) ) (

(

) ( 2

)

( Q x

x G

x R x

M ⁿ

+ =

⋅

• Sia:

– M(x) il messaggio da trasmettere (su k bit) – G(x) il numero “generatore” che sarà usato

come divisore (su n+1 bit)

– R(x) il resto (su n<k bit) di M(x)•2 ⁿ /G(x)

• Si genera la parola di codice appendendo R(x) al messaggio

• Se il messaggio comprensivo di R(x) è

corretto, la divisione per il numero generatore

deve dare resto zero

Esempio

111000 : 101 = 1101 101

--- 0100

101 --- 00100

101 --- 001

G(x): 101 (quindi CRC su 2 bit, uno in meno dei bit di G(x)) M(x): 1110

bit a zero equivalenti alla moltiplicazione per 2

verranno sostituiti da R(x) (il CRC)

il quoziente viene

ignorato ai fini del calcolo del CRC

CRC

messaggio con CRC: 111001

CRC

M(x)

Esempio

ricezione corretta:

111001

111001 : 101 = 1101 101

--- 0100

101 --- 00101

101 ---

000 resto zero: OK

esempio di ricezione errata:

100001

100001 : 101 = 101 101

--- 00100

101 ---

00011 resto non zero: errore!

Codici polinomiali

• Polinomi generatori standard:

CRC-8: X ⁸ +X ² +X ¹ +1 (1 0000 0111)

CRC-16: X ¹⁶ +X ¹⁵ +X ² +1 (1 1000 0000 0000 0101)

CRC-CCITT: X ¹⁶ +X ¹² +X ⁵ +1

CRC-32: X ³² +X ²⁶ +X ²³ +X ¹⁶ +X ¹² +X ¹¹ +

+X ¹⁰ +X ⁸ +X ⁷ +X ⁵ +X ⁴ +X ² +X+1

Codici di Hamming

• Un semplice codice di Hamming (a 1 bit) aggiunge al messaggio la somma modulo due delle posizioni dei bit a 1 del messaggio stesso

• Tale somma occupa nel messaggio le posizioni corrispondenti al peso di ogni singolo bit della somma stessa

• Consente la correzione di errori singoli

Esempio

1 0 0 x 1 1 0 x 1 x x

11 10 9 8 7 6 5 4 3 2 1

11 = 1011 + 7 = 0111 + 6 = 0110 + 3 = 0011 ---

1001

1 0 0 1 1 1 0 0 1 0 1

11 10 9 8 7 6 5 4 3 2 1

Esempio

• In ricezione si sommano (modulo 2) le posizioni in cui ci sono dei bit a 1

– se la somma è zero il messaggio è (probabilmente) corretto

– se la somma è diversa da zero il valore ottenuto è la posizione del bit errato (è infatti il valore - posizione di un bit a 1 - che manca o che è di troppo nella

somma)

Esempio

1 0 0 1 1 1 0 0 1 0 1

11 10 9 8 7 6 5 4 3 2 1

11 = 1011 + 8 = 1000 + 7 = 0111 + 6 = 0110 + 3 = 0011 + 1 = 0001 ---

0000

messaggio corretto

Esempio

1 0 0 1 0 1 0 0 1 0 1

11 10 9 8 7 6 5 4 3 2 1

11 = 1011 + 8 = 1000 + 6 = 0110 + 3 = 0011 + 1 = 0001 ---

0111

errore al bit 7

Codici a convoluzione

• Molto utilizzati nella trasmissione dei dati

• Non sono limitati al singolo blocco di dato: viene elaborato l’intero flusso

• Si basano su un sistema con memoria in cui il risultato della decodifica di un dato è funzione dei dati ricevuti in

precedenza