Reti di Calcolatori a.a. 2005/06 Lezione 7

Reti di Calcolatori Andrea Frosini 1

Reti di Calcolatoria.a. 2005/06

Lezione 7


Nel modello di riferimento:

Application

Transport

Network

Data Link

Fisico


Rilevare errori - schema

Host1: messaggio M + bit di controllo R

= parola di codice CHost2: riceve parola C’

C’ è una parola del codice

NO Errore rilevato!

SIHost2: trasmette OK

ma …

C == C’SI NO

Errore non rilevato!

Nessunerrore!


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

Codici per la correzione di errori


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


2 3

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:

a m a r e an

p e p t i ed

i n a l id

f r o s i

e t t e ar

r

in

l

1 2 3 …

1

a m a X e an

p e p X i ed

i n X l id

f r X s i

e X t e ar

r

in

l

…

XXXXX


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


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%

Bit di parità

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


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

Codice polinomiale


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

Rappresentazione di polinomi con sequenze di bit


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


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


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

Calcolo del CRC - Esempio


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)

Errori catturati dal CRC I


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è?)

Errori catturati dal CRC II


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)

Errori catturati dal CRC III


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)


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

CRC standard II

Reti di Calcolatori a.a. 2005/06 Lezione 7

Documents

Transcript of Reti di Calcolatori a.a. 2005/06 Lezione 7