Reti di Calcolatori
a.a. 2005/06
Lezione 7
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Fisico
Reti di Calcolatori
Andrea Frosini
2
Rilevare errori - schema
Host1: messaggio M +
bit di controllo R
= parola di codice C
Host2: riceve parola C’
SI
Host2:
trasmette OK
C’ è una parola
del codice
NO
Errore
rilevato!
ma …
C == C’
SI
Nessun
errore!
Reti di Calcolatori
NO
Errore non
rilevato!
Andrea Frosini
3
Codici per la correzione di errori
Per correggere un singolo errore su m bit si devono impiegare almeno r bit di
check, con
2r  m + r + 1
ossia sono necessari circa log2 m bit
Esiste un codice (codice di Hamming) che raggiunge tale limite teorico
Esiste una semplice tecnica che consente di impiegare il codice di Hamming per
correggere burst di errori (cioè gruppi contigui di errori, come usualmente accade nelle
trasmissioni reali).
Reti di Calcolatori
Andrea Frosini
4
Codice di Hamming per burst di errori
Il codice di Hamming corregge un singolo errore su stringhe di m bit
Supponiamo di voler invece correggere un burst di al più k errori (ma non tutti i k bit
sono necessariamente sbagliati!)
1. codificare k messaggi consecutivi di lunghezza m, ottenendo k parole di codice di
lunghezza n
2. organizzare le k parole di codice in una matrice
3. inviare i k bit della prima colonna, poi i k bit della seconda colonna, . . . , infine i k
bit della n-esima colonna
Se il burst di errori è lungo al più k, ciascuna riga della matrice può avere al più 1 bit
errato, quindi il codice è in grado di correggerlo
Reti di Calcolatori
Andrea Frosini
5
Codice di Hamming per burst di errori - idea
Supponiamo di voler trasmettere parole di 7 lettere ( m = 7 ) su una linea con burst di
errori di al più 5 lettere ( k = 5 ). La situazione è la seguente:
1
2
3
…
a m a r e n a
a m a X e n a
p e p t
i d e
p e p X i d e
r
i n a
l d i
r
f r o s
i n i
f r X s
l e t
1
2
t e r a
3
i n X l d i
i n i
l e X t e r a
…
XXXXX
Reti di Calcolatori
Andrea Frosini
6
Codici per il rilevamento 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)
Il più semplice codice per il rilevamento di errori è il bit di parità
Tale codice ha distanza di Hamming pari a 2, quindi garantisce solo il rilevamento
del singolo errore
Reti di Calcolatori
Andrea Frosini
7
Bit di parità
Un solo bit di controllo è sufficiente per blocchi di qualunque dimensione
I burst di errori vengono rilevati solo quando il numero effettivo di bit sbagliati è
dispari, ossia con probabilità 50%
Un metodo per rilevare 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
Reti di Calcolatori
Andrea Frosini
8
Codice polinomiale
Il codice polinomiale, detto anche cyclic redundancy code (CRC), è il codice per il
rilevamento di errori più diffuso
In apparenza è complesso, ma esistono circuiti hardware abbastanza semplici che lo
calcolano efficientemente
E’ basato sulla teoria dei campi algebrici:
• le addizioni e sottrazioni sono sempre effettuate modulo 2 (XOR), quindi non
esiste riporto o prestito
• la divisione è effettuata come in binario, ma con sottrazioni modulo 2; inoltre
un divisore “sta” nel dividendo se il dividendo ha tanti bit significativi quanti il
divisore, ossia se il resto ha strettamente meno bit significativi del divisore
Reti di Calcolatori
Andrea Frosini
9
Rappresentazione di polinomi con sequenze di bit
Il codice polinomiale è basato sulla rappresentazione di polinomi algebrici a coefficienti
in {0, 1} con sequenze di bit
Una sequenza di m bit rappresenta un polinomio di grado (al più) m – 1; ciascun bit è il
valore di un coefficiente. Ad esempio:
10001001001
corrisponde al polinomio
x10 +x6 +x3 +1
Reti di Calcolatori
Andrea Frosini
10
Polinomio generatore
Il polinomio generatore G(x) è un polinomio algebrico prefissato di grado r (la stringa
ha r + 1 bit). E’ conosciuto sia dal trasmittente che dal ricevente. Il primo e l’ultimo bit
devono essere “1”.
Il messaggio da trasmettere è rappresentato da un altro polinomio M(x) di grado al più
n - 1 (n > r)
Idea chiave: appendere al messaggio una stringa di bit di controllo in modo tale
che il polinomio corrispondente alla parola di codice sia divisibile per G(x)
Se uno o più errori di trasmissione modificano la parola di codice, il polinomio
corrispondente non sarà divisibile, con alta probabilità, per G(x).
Reti di Calcolatori
Andrea Frosini
11
Algoritmo di calcolo del CRC
1. Mittente e destinatario si mettono d'accordo su un polinomio generatore G(x), con
bit più significativo e meno significativo uguali ad 1
2. Il mittente aggiunge al frame un checksum di r bit “0” in coda agli m bit del
messaggio (la nuova stringa rappresenta il polinomio xr M(x))
3. Dividere la stringa corrispondente a xr M(x) per la stringa corrispondente a G(x)
4. Sottrarre il resto (che ha sempre al più r bit) dalla stringa corrispondente a xr M(x)
5. Il risultato è il polinomio T(x) da trasmettere: è divisibile per G(x) ed i primi m bit
sono uguali a quelli di M(x)
Il polinomio T ’(x) ricevuto viene diviso per G(x): il messaggio viene accettato se e solo
se il resto della divisione è zero
Reti di Calcolatori
Andrea Frosini
12
Calcolo del CRC - Esempio
Fissiamo il polinomio generatore: G(x) = x4 +x+1 (corrispondente a 10011)
Sia il messaggio = 101101 (corrispondente a M(x) = x5 +x3 +x2 +1)
Passo 1: aggiungiamo r = 4 bit “0” al messaggio: 1011010000
Passo 2: dividiamo x4 M(x) per G(x): scartiamo il risultato e teniamo il resto
(la divisione sarà 1011010000 : 10011 = 101010 con resto 1110 )
Passo 3: calcoliamo 1011010000 – 1110 = 101101 1110
Passo 4: trasmettiamo la sequenza ottenuta 1011011110
Reti di Calcolatori
Andrea Frosini
13
Errori catturati dal CRC I
Sia T(x) il polinomio trasmesso, e sia T(x)+E(x) il polinomio ricevuto
Ogni bit “1” in E(x) corrisponde ad un bit invertito per errore
T(x)+E(x) diviso G(x) ha resto zero se e solo se
E(x) è nullo (trasmissione senza errori), oppure
E(x) è un multiplo di G(x)
Reti di Calcolatori
Andrea Frosini
14
Errori catturati dal CRC II
Se G(x) ha due o più termini, il codice polinomiale rileva tutti gli errori singoli
(E(x) = xi non può essere multiplo di G(x), perché G(x) contiene sempre almeno
due termini)
Se G(x) non è divisibile per x e non divide alcun xk+1, con k = 1, . . . , n, il codice
polinomiale rileva tutti gli errori in parole di codice da n bit consistenti in due bit
invertiti (cioè tali che E(x) = xi+xj) (?perché?)
Ad es. x15+x14+1 non divide xk+1 per ogni k < 32.768
Se G(x) ha come fattore x + 1, il codice polinomiale rileva tutti gli errori consistenti
di un numero dispari di bit (?perchè?)
Reti di Calcolatori
Andrea Frosini
15
Errori catturati dal CRC III
Se G(x) ha grado r (r bit di controllo), il codice polinomiale rileva tutti i burst di al
più r errori
Infatti, un burst di k errori è rappresentato da
E(x) = xi (xk-1 +. . .+1)
Dato che G(x) contiene il termine x0, G(x) non può avere xi come fattore;
se k - 1 < r, l’altro fattore di E(x) non può essere multiplo di G(x) (aggiungo
qualcosa che è più piccolo di G(x)).
Perciò il resto di E(x)/G(x) non può essere nullo
Dato un burst di r + 1 errori, la probabilità che esso non sia rilevato è 1/2r-1 (solo
quando gli r+1 bits sono uguali a G(x)); la probabilità di non rilevare un burst di più
di r + 1 errori è 1/2r (assumendo che all’interno del burst gli errori si distribuiscano
in modo casuale)
Reti di Calcolatori
Andrea Frosini
16
CRC standard I
Alcuni polinomi generatori sono diventati standard internazionali:
• CRC-8: x8 +x2 +x+1 (usato in reti ATM)
• CRC-10: x10 +x9 +x5 +x4 +x+1 (usato in reti ATM)
• CRC-12: x12+x11+x3+x2+x+1 (usato per caratteri codificati con 6 bit)
• CRC-16: x16 +x15 +x2 +1 (usato per caratteri ad 8 bit)
• CRC-CCITT: x16 +x12 +x5 +1 (usato da HDLC)
• CRC-32: x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 + x4 +x2 +x +1
(usato in IEEE 802 e in reti ATM)
Reti di Calcolatori
Andrea Frosini
17
CRC standard II
Il codice a 32 bit CRC-32 rileva:
• tutti gli errori singoli e doppi
• tutti gli errori con numero dispari di bit
• tutti i burst di errori di lunghezza al più 32
• teoricamente, il 99.9999999% di tutti i burst di errori lunghi più di 32 bit
In realtà la stima teorica per i burst lunghi 33 o più bit è troppo ottimistica, in quanto i
bit erronei non sono distribuiti all’interno del burst in modo veramente casuale
Reti di Calcolatori
Andrea Frosini
18