12A-Controllo degli errori.pdf

   195 3D Controllo degli errori 3.9 Bit di parità 3.10 Checksum 3.11 Codice a ridondanza ciclica Le strategie che si possono adottare in linea di principio per il controllo degli errori sono sostanzialmente due: • correzione degli errori in avanti, o forward error correction (FEC), • richiest...

   195 3D Controllo degli errori 3.9 Bit di parità 3.10 Checksum 3.11 Codice a ridondanza ciclica Le strategie che si possono adottare in linea di principio per il controllo degli errori sono sostanzialmente due: • correzione degli errori in avanti, o forward error correction (FEC), • richiesta di ripetizione automatica, o automatic repeat request (ARQ). Nella strategia FEC, all’unità informativa da trasmettere viene associato un campo addizionale, generalmente a lunghezza variabile, che rappresenta un codice a correzione di errore. Il nome stesso della procedura indica che l’informazione di controllo di errore viaggia “in avanti”, cioè nella stessa direzione dei dati dell’utente. L’apparecchiatura ricevente utilizza questa informazione aggiuntiva per correggere eventuali errori che possono avere colpito uno o più bit dell’UI. In questo caso non è previsto alcun riscontro di corretta ricezione, con la conseguenza che per una comunicazione unidirezionale è sufficiente un canale trasmissivo di tipo unidirezionale e che le UI trasmesse vengono immediatamente cancellate dal buffer che le conteneva. La trasmissione del codice di controllo utilizzerà necessariamente una percentuale aggiuntiva della capacità del canale trasmissivo rispetto ai dati dell’utente (in genere dell’ordine di qualche unità percentuale). Si deve osservare che più i codici sono complessi, maggiore è questa percentuale aggiuntiva e maggiore è quindi la quantità di elaborazione richiesta per attuare la procedura di controllo e di correzione degli errori su ogni UI. Si noti che, adottando questo meccanismo, la quantità di informazione che viene trasferita globalmente sul collegamento dati è indipendente dal tasso d’errore. Nella strategia ARQ ai dati di utente si aggiunge in trasmissione un insieme di bit che costituiscono un codice a rivelazione di errore, capace cioè di rivelare la presenza di errori, ma non di correggerli. Una volta rivelato l’errore, l’apparecchiatura ricevente deve comunicarlo all’apparecchiatura trasmittente, che dovrà provvedere alla ritrasmissione delle unità informative per le quali l’errore è stato rivelato. Per questo motivo, con la tecnica ARQ anche per comunicazioni unidirezionali si richiede sempre la disponibilità di un canale di ritorno dal ricevitore al trasmettitore. Il codice a rivelazione di errore ha in generale una lunghezza predeterminata, indipendente dalla sequenza dei bit di informazione da proteggere. Il trasferimento senza successo di un’unità informativa dal trasmettitore al ricevitore implica che la stessa venga ritrasmessa una o più volte in presenza di errori. Ne consegue che, se si utilizzano tecniche ARQ, la quantità di informazione trasmessa non è più indipendente dal tasso di errore. Si può ancora osservare che le strategie ARQ richiedono la disponibilità di unità di memoria dal lato trasmissione, dove vengono immagazzinate temporaneamente le UI trasmesse in attesa di riceverne il relativo riscontro. Questa unità viene denominata memoria di ritrasmissione e può anche fisicamente coincidere con lo stesso buffer di trasmissione. I protocolli che implementano la strategia ARQ sono descritti nel Paragrafo 3.2. Le procedure di controllo degli errori che vengono qui descritte sono basate sulla generazione di bit o stringhe di bit che vengono aggiunti alla sequenza di bit di informazione da PattavinaReti2021.indb 195 14/01/2022 16:08:58 196  Capitolo 3 – Teoria dei protocolli 3D Controllo degli errori inviare, così che il ricevitore possa svolgere una procedura di controllo sulla correttezza della sequenza informativa ricevuta. Si farà riferimento alle tre principali procedure utilizzate nell’ambito della rete Internet per svolgere questa funzione: (i) bit di parità; (ii) checksum; (iii) codice a ridondanza ciclica. Nel primo caso, nella sequenza trasmessa vengono inseriti singoli bit intercalati con i bit di informazione, mentre negli altri due casi viene generato un codice di controllo generalmente trasmesso dopo la stringa informativa. 3.9 Bit di parità Il metodo più semplice per la rivelazione di errori in una sequenza di bit trasmessa consiste nell’inserire nella sequenza stessa un bit di parità ogni k bit di informazione, in modo tale che la stringa di k + 1 bit contenga sempre un numero pari22 di bit “1”. Un esempio è riportato in Figura 3.74a in cui n = 36 bit di informazione sono stati protetti con un bit di parità ogni k = 6 bit. La Figura 3.74b mostra l’intera sequenza trasmessa che include i bit di parità. Naturalmente la capacità di rivelazione degli errori di questa tecnica è molto limitata, dato che sono rilevabili solo errori che colpiscano un numero dispari di bit di ogni stringa di k + 1 bit, sostituendo il bit “0” con il bit “1” e viceversa. Una maggiore capacità di rivelazione di errori viene ottenuta con un codice di parità bidimensionale (2-d), in cui ogni blocco di m stringhe di k + 1 bit, ognuna protetta da un bit di parità “orizzontale”, viene protetto con un’ulteriore stringa di k + 1 bit di parità “verticale”. Il primo bit di questa nuova stringa indica la parità del primo bit delle m stringhe, il secondo bit la parità del secondo bit, e così via fino all’ultimo bit, che indica la parità verticale degli m bit di parità orizzontale. È interessante osservare allora come quest’ultimo bit di parità verticale rappresenti anche la parità orizzontale dei primi k bit di parità verticale. La Figura 3.75a mostra un esempio di controllo di parità bidimensionale con k = 6 e m = 6. Viene prima aggiunto il bit di parità orizzontale di ognuna delle k stringhe, così che ognuna di esse è ora composta da k + 1 bit. Vengono quindi aggiunti altri k + 1 bit di parità “verticale”, ognuno dei quali indica la parità di uno specifico bit di tutte le m stringhe di k + 1 bit. La sequenza complessiva trasmessa è mostrata in Figura 3.75b. La rivelazione di errore basata sui bit di parità è particolarmente semplice e si presta molto bene a essere utilizzata con implementazioni di tipo hardware, cosi da consentire controlli di errore su flussi trasmessi ad altissima velocità, anche dell’ordine di decine di Gbit/s. Per questo motivo la loro applicazione nella rete Internet avviene prevalentemente nell’ambito dello strato fisico. 010011 110110 001000 111111 001100 000000 1 0 1 0 0 0 0100111 1101100 0010001 1111110 0011000 0000000 Figura 3.74 (a) (b) Controllo di parità: bit di parità (a) e sequenza trasmessa (b). 22  In questo testo si farà riferimento esclusivamente al controllo di parità “pari”, in cui cioè la stringa di k + 1 bit contiene sempre un numero pari di bit “1”. Un controllo di parità “dispari” richiede invece di determinare il bit di parità in modo che la stringa di k + 1 bit contenga sempre un numero dispari di bit “1”. PattavinaReti2021.indb 196 14/01/2022 16:08:58 3.10 010011 110110 001000 111111 001100 000000 011110 Checksum  197 1 0 1 0 0 0 0 (a) 0100111 1101100 0010001 1111110 0011000 0000000 0111100 Figura 3.75 (b) Controllo di parità bidimensionale: bit di parità (a) e sequenza trasmessa (b). Esempio 3.25 Si vuole determinare il codice di parità bidimensionale per la stringa di sette lettere “Routing” adottando una codifica ASCII a 7 bit. La Figura 3.76a mostra la codifica relativa ai singoli caratteri in formato esadecimale, i sette bit di parità orizzontale associati ai singoli caratteri, nonché i bit di parità verticale relativi ai bit di uguale posizione nei sette caratteri. La sequenza complessiva trasmessa è riportata in Figura 3.76b. 3.10 Checksum Il metodo checksum di rivelazione di errori si basa sul principio di generare una stringa di controllo di k bit per verificare l’integrità di una serie di stringhe binarie di uguale dimensione, cioè di k bit ognuna. Seguendo l’approccio riportato in [Leon-Garcia] si assume che la sequenza di bit di informazione contenga n·k bit. Si suddivide allora la sequenza in n stringhe di k bit, delle quali l’i-esima (0 ≤ i ≤ n _ 1) viene qui indicata come vettore bi. Si effettua quindi la somma modulo-(2k _ 1) di tutte le stringhe per ottenere la somma s = (b0 + b1 + ... + bn–1)mod(2k– 1). (3.50) La stringa di checksum bn si ottiene come l’intero negativo di s in modulo-(2k _ 1), cioè bn = -s. Ipotizzando che la stringa di checksum venga inviata dopo la sequenza da proteggere, allora l’intera sequenza inviata sarà b0b1... bn–1bn. In assenza di errori il ricevitore potrà ovviamente verificare la condizione R o u t i n g 52 6F 75 74 69 6E 67 101 110 111 111 110 110 110 101 0010 1111 0101 0100 1001 1110 0111 1100 1 0 1 0 0 1 1 0 10100101 11011110 11101011 11101000 11010010 11011101 11001111 10111000 Figura 3.76 PattavinaReti2021.indb 197 (a) (b) Parità 2-d: bit di parità (a) e stringa trasmessa (b) secondo l’Esempio 3.25. 14/01/2022 16:08:59 198  Capitolo 3 – Teoria dei protocolli 3D Controllo degli errori (b0 + b1 + ... + bn–1 + bn)mod(2k – 1) = 0 A titolo di esempio assumiamo k = 4, così le somme saranno effettuate modulo-15. Se n = 2 e le due sequenze sono 1011 e 0111, la loro somma modulo-15 sarà 0011 (infatti 11 + 7 = 18mod‑15 = 3). L’inversione modulo-15 di 0011 genera 1100, cioè 12. In assenza di errori, la sequenza che si riceve è 101101111100 e la somma in aritmetica in complemento a 1 delle tre sequenze 1011, 0111, 1100 fornisce 1111, che modulo-15 corrisponde23 a 0. Nella rete Internet la rivelazione di errore con checksum è adottata nello strato di trasporto utilizzando sequenze di k = 16 bit (vedi Paragrafo 5.3.2) e la sua implementazione si basa sull’aritmetica in complemento a 1. In questo caso la somma descritta dall’Equazione (3.50) consiste nel sommare tutte le sequenze binarie di 16 bit e gli eventuali bit di riporto vengono sommati ai bit meno significativi della somma. Ciò corrisponde a effettuare l’operazione di somma modulo-(216 – 1). Il complemento a 1 del risultato ottenuto, sostituendo cioè il bit 0 con il bit 1 e viceversa, fornisce la stringa di checksum. Esempio 3.26 Per la stringa esadecimale 0xC5CB0C0783AFC90E4F4B si chiede di determinare la stringa di checksum sapendo che questa è costituita da k = 16 bit. Come mostrato in Figura 3.77, si suddivide la sequenza assegnata in stringhe di 16 bit ognuna che vengono quindi sommate (sum). Secondo l’aritmetica in complemento a 1, i due bit 10 del riporto (carries) vanno sommati ai bit meno significativi della somma, ottenendo una nuova stringa di 16 bit (sum with carries, SwC). Infine, la stringa di checksum si ottiene come complemento a 1 della sequenza SwC. La sequenza di n·k bit di informazione viene quindi trasmessa seguita dai k = 16 bit della checksum. Data la procedura seguita per il calcolo della stringa di checksum, risulta evidente che la somma in complemento a 1 dell’intera sequenza ricevuta genera in assenza di errori la stringa 0xFFFF e quindi il suo complemento a 1 sarà 0x0000. Esempio 3.27 Si vuole mostrare come si effettua l’operazione di verifica sulla eventuale presenza di errori nella ricezione della sequenza di 80 bit definita nell’Esempio 3.26 che viene seguita dall’invio della checksum. La sequenza ricevuta in assenza di errore è 0xC5CB0C0783AFC90E4F4B9223. Vengono ripetute le stesse operazioni svolte per il calcolo della checksum, considerando questa volta anche la stessa sequenza di 16 bit della checksum, come mostrato in Figura 3.78a. Come atteso, la verifica genera una stringa finale 0x0000 indicando assenza di errori. Se invece nella sequenza trasmessa si verificano errori, che consistono in due bit “1” trasmessi ma ricevuti come bit “0”, la verifica genera una stringa finale diversa da 0x0000, come riportato in Figura 3.78b. 23  È importante osservare che nell’aritmetica in complemento a 1 modulo-15 entrambe le stringhe 0000 e 1111 corrispondono al valore decimale 0. PattavinaReti2021.indb 198 14/01/2022 16:08:59 3.11 Codice a ridondanza ciclica   199 Figura 3.77 11000101 11001011 00001100 00000111 10000011 10101111 11001001 00001110 01001111 01001011 C5 CB 0C 07 83 AF C9 0E 4F 4B 10 01101101 11011010 10 Sum Carries 01101101 11011100 SwC 10010010 00100011 Checksum Calcolo della checksum secondo l’Esempio 3.26. 11000101 11001011 00001100 00000111 10000011 10101111 11001001 00001110 01001111 01001011 10010010 00100011 C5 CB 0C 07 83 AF C9 0E 4F 4B 92 23 11000101 11001011 00001100 00000111 10000011 10101111 11001001 00001110 01000011 01001011 10010010 00100011 C5 CB 0C 07 83 AF C9 0E 43 4B 92 23 10 11111111 11111101 10 Sum Carries 10 11110011 11111101 10 Sum Carries 11111111 11111111 SwC 11110011 11111111 SwC 00000000 00000000 Check 00001100 00000000 Check (a) Figura 3.78 3.11 (b) Verifica della checksum senza (a) e con (b) errori secondo l’Esempio 3.27. Codice a ridondanza ciclica La procedura che genera il codice di rivelazione degli errori a ridondanza ciclica si basa sull’uso dei codici polinomiali per generare un codice di controllo denominato cyclic redundancy check (CRC). Si consideri una generica stringa di n bit da cui possiamo ricavare il polinomio P(x) di grado n – 1 nella variabile ausiliaria x dove i coefficienti sono dati dagli n bit della stringa. Se per ipotesi avessimo la stringa di 10 bit 1001000111, il polinomio P(x) corrispondente sarebbe P(x) = x9 + x6 + x2 + x + 1. Il codice di rivelazione di errore viene generato avendo prima definito un polinomio generatore G(x) di grado k le cui caratteristiche determinano le proprietà di rivelazione degli errori del codice CRC. Questo codice sarà costituito da una sequenza di k bit. I k bit del codice CRC vengono ricavati da un’operazione di divisione tra polinomi in aritmetica24 modulo-2, in cui il polinomio dividendo è dato da P(x) moltiplicato per xk e il polinomio divisore è dato dal polinomio generatore G(x) di grado k. Questa divisione darà luogo a un quoziente Q(x) e a un resto R(x), che soddisfa la seguente espressione k P( x ) ⋅ x R (x) --------------------- = Q ( x ) + ------------ . G(x) G(x) (3.51) 24 Si ricorda che in aritmetica modulo-2, addizioni e sottrazioni non danno luogo a riporti né a prestiti. PattavinaReti2021.indb 199 14/01/2022 16:09:00 200  Capitolo 3 – Teoria dei protocolli 3D Controllo degli errori Il polinomio R(x) ha grado massimo k – 1, poiché la divisione è stata effettuata in aritmetica modulo 2, e quindi R(x) esprime k coefficienti, ognuno dei quali assume il valore binario 0 o 1, e questi bit costituiscono il codice di controllo CRC. Gli n + k bit che vengono inviati, dei quali i primi n sono i bit di informazione e gli ultimi k sono i bit di controllo di errore, possono essere considerati i coefficienti di un nuovo polinomio P'(x) dato da k P′ ( x ) = P ( x ) ⋅ x + R ( x ) . (3.52) Esempio 3.28 Per la stringa di 10 bit 1001000101 si vuole determinare il codice CRC per la rivelazione di errore, sapendo che il polinomio generatore è G(x) = x4 + x3 + 1. Alla stringa assegnata corrisponde il polinomio P(x) = x9 + x6 + x2 + 1. Considerando che il polinomio generatore assegnato implica k = 4, si ottiene P'(x) = P(x)·x4 = x13 + x10 + x6 + x4. La divisione di quest’ultimo polinomio con G(x) è mostrata in Figura 3.79; si ricorda che in aritmetica modulo-2 la somma di due polinomi fornisce lo stesso risultato della loro differenza. In conclusione, si ottiene Q(x) = x9 + x8 + x7 +x5 + x3 + x, R(x) = x3 + x e quindi la stringa di controllo di errore è CRC = 1010. La procedura di rivelazione di errore in ricezione è particolarmente semplice: se la divisione del polinomio P'(x), derivato dalla sequenza di bit ricevuta, per lo stesso polinomio generatore G(x) genera resto nullo, allora si assume che la sequenza ricevuta non sia errata, compatibilmente con le capacità di rivelare errori del meccanismo adottato. Infatti, utilizzando le Equax13 + x10 + x6 x13 + x12 + x9 x12 + x10 + x9 x12 + x11 + x4 x4 + x3 + 1 x9 + x8 + x7 + x5 + x3 + x + x6 + x4 + x6 + x4 x9 + x8 + x7 + x6 + x4 + x8 x11 + x10 + x9 + x8 x11 + x10 +x7 x9 + x8 + x5 x7 + x6 + x5 + x4 x7 + x6 + x3 x5 + x4 + x3 x5 + x4 +x x3 + Figura 3.79 PattavinaReti2021.indb 200 x Generazione del codice CRC secondo l’Esempio 3.28. 14/01/2022 16:09:00 3.11 Codice a ridondanza ciclica   201 zioni (3.52) e (3.51) e considerando che in aritmetica modulo-2 moltiplicare un numero per 2 fornisce 0 come risultato, si può verificare che k P′ ( x )- = -------------------P ( x ) ⋅ x + ----------R ( x )- = Q ( x ) + 2 ⋅ ----------R ( x )- = Q ( x ) -----------. G(x) G(x) G(x ) G(x ) (3.53) Un resto R(x) diverso da zero indica dunque la presenza di errori. Esempio 3.29 Si vuole verificare se la stringa di 14 bit 10001010010010, comprensiva di CRC negli ultimi bit, rivela la presenza di errori, sapendo che il polinomio generatore è G(x) = x5 + x3 + x2 + 1. La divisione del polinomio P'(x) = x13 + x9 + x7 + x4 + x ricavato dalla stringa ricevuta per il polinomio G(x) fornisce un resto R(x) = x4 + x3 + x, come mostrato in Figura 3.80, consentendoci di affermare la presenza di errori. L’Equazione (3.53), riscritta come P′ ( x ) = Q ( x )G ( x ) . indica che, in assenza di errori, il polinomio P'(x) che rappresenta la sequenza di bit trasmessa è un multiplo del polinomio generatore G(x). L’occorrenza di errori sulla sequenza trasmessa si manifesta attraverso l’inversione di uno o più bit rispetto al valore originario, cioè bit 1 vengono ricevuti come bit 0 e viceversa. In questo caso il polinomio P''(x) che rappresenta la sequenza errata ricevuta può essere rappresentato come P″ ( x ) = P′ ( x ) + E ( x ) = Q ( x )G ( x ) + E ( x ) . Quindi, se il polinomio di errore E(x) che rappresenta con i suoi termini i bit errati è divisibile per il polinomio generatore G(x), gli errori verificatisi non sono rilevabili. x13 + x9 x13 + x11 + x10 + x7 + x4 + x8 + x9 + x8 x10 x10 + x4 +x + x4 +x + x5 + x4 +x + x6 + x7 + x6 + x8 x5 + x3 + x2 + 1 x8 + x6 + x5 + x3 x11 + x10 + x9 + x8 + x7 x11 +x + x7 + x6 x5 x8 + x8 + x6 + x5 + x3 x4 + x3 + x Figura 3.80 PattavinaReti2021.indb 201 Verifica dell’occorrenza di errori secondo l’Esempio 3.29. 14/01/2022 16:09:01 202  Capitolo 3 – Teoria dei protocolli 3D Controllo degli errori Esempio 3.30 Per la stringa di 10 bit 1001000101 il codice CRC = 1010 per la rivelazione di errore è stato derivato nell’Esempio 3.28 in base al polinomio generatore G(x) = x4 + x3 + 1. La sequenza di 14 bit costituita dai 10 bit di informazione e dai 4 bit di controllo inviata lungo un collegamento punto-punto viene ricevuta affetta da errori rappresentabili tramite il polinomio E(x) = x7 + x6 + x3. Si vuole verificare la capacità del codice di rivelare errori. La sequenza di bit inviata è espressa come P'(x) = P(x)·x4 = x13 + x10 + x6 + x4 + x3 + x, mentre quella ricevuta è rappresentata come P"(x) = P'(x) + E(x) = x13 + x10 + x7 + x4 + x. La divisione del polinomio P"(x) per il polinomio generatore G(x), riportata in Figura 3.81, genera un resto nullo, contraddicendo apparentemente l’occorrenza di errori sulla sequenza di bit durante il loro trasferimento. Tuttavia, ciò può essere spiegato considerando che il polinomio di errore E(x) è un multiplo del polinomio generatore e quindi, come tale, determina errori non rilevabili dal codice adottato. Si può dimostrare che, scegliendo opportunamente il polinomio generatore G(x), i seguenti eventi di errore sono sempre rilevabili: • errori su un singolo bit, se G(x) ha almeno due termini; • errori su due bit, se xm + 1 non è divisibile per G(x) per ogni valore di m minore della lunghezza della sequenza trasmessa ( 1 ≤ m < n + k ) ; • errori su un numero dispari di bit, se G(x) è esprimibile come fattore di x + 1; • errori a “burst” (cioè consecutivi), in cui la lunghezza del burst sia inferiore o uguale a quella del codice CRC, cioè a k bit. x13 + x10 + x7 x13 + x12 + x9 x12 + x10 + x9 x12 + x11 + x4 + x x4 + x3 + 1 x9 + x8 + x7 + x5 + x3 + x + x7 + x4 + x + x8 x11 + x10 + x9 + x8 + x7 x11 + x10 + x4 + x +x7 x9 + x8 x9 + x8 + x4 + x + x5 x5 + x4 + x x5 + x4 + x ---- Figura 3.81 PattavinaReti2021.indb 202 Verifica dell’occorrenza di errori secondo l’Esempio 3.30. 14/01/2022 16:09:01 3.11 Codice a ridondanza ciclica   203 Per quanto riguarda gli errori singoli, il polinomio di errore sarà del tipo j E ( x ) = x , ( 0 ≤ j < n + k ) . Se il polinomio generatore G(x) ha almeno due termini, ne consegue che la divisione di E(x) per G(x) non può dare resto nullo, consentendo quindi sempre la rivelazione dell’errore occorso. Dimostrazioni analoghe possono essere sviluppate per gli altri tipi di errore rilevabili sopra elencati. I protocolli della rete Internet che adottano i codici a ridondanza ciclica per la rivelazione di errore si trovano tipicamente nello strato di collegamento dati. La Tabella 3.5 mostra i polinomi generatori adottati in alcuni dei protocolli descritti in questo testo. Il codice a 8 bit CRC-8 è stato adottato per la rivelazione degli errori sull’header nel campo HEC della cella ATM (vedi Paragrafo 6.9.2). I due codici a 16 bit CRC-16 USA e CRC-16 ITU-T sono stati utilizzati nei protocolli di linea Bisync e HDLC (vedi Paragrafo 7.3.3), rispettivamente. Il codice a 32 bit CRC-32 è stato adottato nelle reti Ethernet (vedi Paragrafo 9.1.3). Tabella 3.5 Polinomi generatori adottati in diversi ambienti di rete. Nome Protocollo Polinomio G(x) CRC-8 ITU-T ATM x8 + x2 + x + 1 CRC-16 USA Bisync x16 + x15 + x2 + 1 CRC-16 ITU-T HDLC x16 + x12 + x5 + 1 CRC-32 PattavinaReti2021.indb 203 IEEE 802.3 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 14/01/2022 16:09:01