Nota di Copyright

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2 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.

Nota di Copyright

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 3

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 4

Controllo e correzione degli errori

dati

in fase di codifica (o memorizzazione o trasmissione)

CRC

dati CRC

Nell’esempio:

Cyclic Redundancy Check = f (dati) f (dati)

Fondamenti di Informatica - Controllo e correzione degli errori

Controllo e correzione degli errori

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Ì

Fondamenti di Informatica - Controllo e correzione degli errori

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

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 7

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”)

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 8

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 9

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 10

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 11

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”)

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 12

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

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 13

Esempio: parità pari

(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

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 14

Codici polinomiali

• 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)

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 15

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 16

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

Fondamenti di Informatica - Controllo e correzione degli errori

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 e “abbasso” un’altra cifra

NOTA: in generale, il risultato di una divisione modulo due non coincide con il risultato della divisione normale

Fondamenti di Informatica - Controllo e correzione degli errori

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 ⋅ ⁿ + =

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 19

Codici polinomiali

• 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

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 20

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)

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 21

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!

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 22

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 23

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 24

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

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 25

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)

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 26

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 27

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

Fondamenti di Informatica - Controllo e correzione degli errori

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 28

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