Sistemi e Tecnologie della
Comunicazione
Lezione 11: data link layer: codici di rilevazione di errore, gestione degli errori
1
La rilevazione di errore




Un codice a rilevazione di errore ha lo scopo di
permettere al ricevente di determinare se vi sono
stati errori in trasmissione
Il codice non ha la finalita’ di correggere l’errore,
ma solo di rilevare che c’e’ stato
Per raggiungere lo scopo si utilizzano bit di
controllo in aggiunta ai bit dei dati
La tecnica utilizzata e’ di assegnare in
trasmissione ai bit di controllo un valore
opportuno in funzione dei bit dei dati; in ricezione
si calcolano nuovamente i valori dei bit di
controllo e si fa la verifica con quelli ricevuti
2
Tecniche di codifica

Abbiamo gia’ visto un esempio: il bit di parita’







questa codifica permette la rilevazione di qualunque errore
singolo, ed in generale di un numero dispari di errori
un numero pari di errori non potra’ essere rilevato
la codifica sara’ quindi in grado di identificare burst di errori con
probabilita’ del 50%
Anche in questo caso si puo’ utilizzare la tecnica di trasmettere K
codeword in colonna per identificare errori burst di lunghezza non
superiore a K; errori piu’ estesi, o piccole serie multiple di errori
produrranno un valore valido per ogni riga con probabilita’ 0.5
la probabilita’ che l’errore non venga rilevato sara’
complessivamente pari a 2  k
il vantaggio di questa codifica e’ il basso overhead (1 bit per ogni
frame)
Generalmente si utilizza una tecnica piu’ efficiente, detta
CRC (Cyclic Redundancy Check), o codifica polinomiale
3
Rappresentazione di sequenze di bit
tramite polinomi



Una sequenza di N bit puo’ essere rappresentata tramite
un polinomio a coefficienti binari, di grado pari a N-1, tale
che i suoi coefficienti siano uguali ai valori dei bit della
sequenza
Il bit piu’ a sinistra rappresenta il coefficiente del termine
di grado N-1, mentre il bit piu’ a destra rappresenta il
termine noto (di grado 0)
Ad esempio, la sequenza 1001011011 puo’ essere
rappresentata dal polinomio
x9  x6  x4  x3  x 1

Il grado del polinomio e’ determinato dal primo bit a
sinistra di valore 1 presente nella sequenza
4
Aritmetica dei polinomi in modulo 2

L’aritmetica dei polinomi a coefficienti binari si gestisce
con le regole della aritmetica modulo 2:

le somme e le sottrazioni non prevedono riporti; sono pertanto
coincidenti ed equivalenti all’OR esclusivo:
10011011 
11001010 
01010001

00110011 
11001101 
11111110
le divisioni sono eseguite normalmente, tranne che le sottrazioni
seguono la regola sopra detta; in questi termini, il divisore “sta”
nel dividendo quando il dividendo ha grado maggiore o uguale al
divisore, mentre non si puo’ dividere quando il dividendo ha grado
inferiore al divisore
5
Divisione binaria di polinomi

Ad esempio:
x6  x3  x2 1
x x
2

x4  x3  x2 1
con resto
x 1
6
Codifica polinomiale (CRC)



La tecnica consiste nel considerare i dati (m bit) da
inviare come un polinomio di grado m-1
Trasmettitore e ricevitore si accordano sull’utilizzo di un
polinomio generatore G(x) di grado r
Il trasmettitore aggiunge in coda al messaggio una
sequenza di bit di controllo (CRC) in modo che il
polinomio associato ai bit del frame trasmesso, costituito
dall’insieme di dati e CRC, sia divisibile per G(x)


e’ sempre possibile trovare tale polinomio
In ricezione si divide il polinomio associato ai dati ricevuti
per G(X)


se la divisione ha resto nullo, si assume che la trasmissione sia
avvenuta senza errori
se la divisione ha resto non nullo, sono certamente avvenuti errori
7
Codifica polinomiale (cont.)

Dal punto di vista logico, la generazione del codice CRC
avviene nel seguente modo:






Sia M(x) il polinomio associato agli m bit di dati
Sia G(x) il polinomio generatore di grado r
Si aggiungono r bit a valore 0 in fondo ai bitr di dati; il polinomio
associato all’insieme di m+r bit e’ quindi x M(x)
Si calcola il resto della divisione x r M(x)/G(x), che sara’ un
polinomio R(x) di grado inferiore ad r, quindi rappresentativo di
una sequenza di r bit
Si costruisce
la sequenza di bit associata al polinomio
r
T(x) = x M(x)-R(x), che equivale ad aggiungere i bit
corrispondenti a R(x) in coda ai dati da inviare: vanno riportati
tutti gli r bit associati ad R(x), quindi anche eventuali zeri in testa
al resto; questa e’ una sequenza di m+r bit
E’ evidente che il polinomio T(x) risultera’ divisibile per G(x) con
resto nullo
8
Esempio di calcolo di CRC

Supponiamo di voler trasmettere con CRC la sequenza
1101011011, utilizzando il polinomio generatore
x4  x 1




equivalente alla sequenza di bit 10011
Si costruisce la sequenza 11010110110000, e la si divide
per 10011
Il resto della divisione e’ 1110
Il frame che verra’ trasmesso sara’ quindi
11010110111110
In ricezione si divide la sequenza ricevuta per lo stesso
polinomio, e si verifica che il resto sia nullo
9
Caratteristiche del polinomio generatore



Le caratteristiche del polinomio generatore determinano
quali errori saranno rilevabili e quali invece potranno
passare inosservati
Detto T(x) il polinomio associato al frame trasmesso, il
polinomio associato al frame ricevuto puo’ essere
espresso come T(x)+E(x), dove E(x) avra’ coefficiente 1
per ogni bit che e’ stato modificato da errori trasmissivi
Risulta chiaro che un errore passera’ inosservato solo se
T(x)+E(x) sara’ divisibile per G(x), ma essendo per
definizione T(x)/G(x) = 0, l’errore passera’ inosservato se
E(x) sara’ divisibile per G(x)
10
Caratteristiche del polinomio generatore (cont.)

Errori di singolo bit: il polinomio E(x) avra’ la forma
E( x)  xi

dove i e’ il bit errato; un polinomio G(x) costituito da piu’ di un termine non
potra’ dividere E(x)
Errori di coppie di bit: il polinomio ha la forma

E ( x )  x i  x k  x k  x ik  1

con i  k
in questo caso G(x) non potra’ essere divisore di E(x) se

G(x) non divide x k per ogni k: gia’ visto

G(x) non divide ( x k+1) per ogni k possibile (cioe’ fino a k pari al numero di bit del
frame): esistono ink letteratura molti polinomi semplici e di basso grado che non
sono divisori di (x +1) fino a valori di K molto elevati; ad esempio, il polinomio
G ( x )  x 15  x 14  1
non divide (x k+1) per K<32768
11
Caratteristiche del polinomio generatore (cont.)

Errori in numero dispari di bit:

se G(x) contiene a fattore (x+1) non puo’ essere
divisore di un polinomio con numero dispari di
elementi:





Per assurdo, supponiamo che E(x) sia divisibile per (x+1)
si puo’ scrivere E(x) = (x+1)Q(x)
calcoliamo E(1) = (1+1)Q(1) ma 1+1 = 0, quindi E(1) = 0
Pero’ se E(x) ha un numero dispari di elementi, E(1) e’ la
somma di un numero dispari di 1, che fa 1
si ha quindi un assurdo che nega l’ipotesi di partenza
12
Caratteristiche del polinomio generatore (cont.)

Sequenze di errori di lunghezza ≤ r




un burst di errori lungo K si puo’ rappresentare
come E(x) = xj (xk-1+xk-2+…+1)
j determina la distanza dell’ultimo bit errato
dall’ultimo bit del frame
come detto, G(x) non divide xj
la restante parte di E(x) non potra’ essere
divisibile per G(x) se K ≤ r
13
Caratteristiche del polinomio generatore (cont.)

Sequenze di errori di lunghezza r+1



in questo caso E(x) sara’ divisibile per G(x)
solo se il burst genera una sequenza identica
al polinomio generatore
la probabilita’ che questo accada e’ (½)r-1
Sequenze di errori di lunghezza maggiore

si puo’ dimostrare, nella assunzione che tutti i
bit possano essere errati con uguale
probabilita’, che negli altri casi la probabilita’
che E(x) sia divisibile per G(x) e’ pari a (½)r
14
Polinomi standard


Viste le caratteristiche dei polinomi, si sono identificati
diversi polinomi opportuni per rendere molto improbabile
la mancata rilevazione di errori
I piu’ comuni a 16 bit sono
x 16  x 15  x 2  1
x 16  x 12  x 5  1

CRC - 16
CRC - CCITT
Un polinomio standard a 32 bit utilizzato in molte
applicazioni (tra cui IEEE 802) e’ il CRC-32:
x 32  x 26  x 23  x 22  x 16  x 12  x 11 
x 10  x 8  x 7  x 5  x 4  x 2  x  1
15
Gestione degli errori

I protocolli a rilevazione di errore devono gestire due tipi
di evento:



dove la perdita puo’ essere un evento noto (ricezione di
un frame errato) o un evento ignoto (distruzione del
frame in trasmissione)
Generalmente si utilizzano una o piu’ delle seguenti
tecniche:




perdita di un frame
perdita di un riscontro
riscontro positivo
attesa di timeout per la ricezione dell’ACK e ritrasmissione
riscontro negativo
Questi meccanismi si chiamano ARQ (Automatic Repeat
reQuest)
16
Gestione degli errori

Esistono diversi meccanismi di ARQ, che si
basano sulle funzionalita’ dei diversi
protocolli di controllo di flusso




ARQ stop-and-wait
ARQ go-back N
ARQ selective reject
Poiche’ il loro funzionamento dipende da
questi protocolli, li vedremo assieme
all’analisi del controllo di flusso
17