A prova d’errore

Controllo di Ridondanza Ciclico

Per tanti utenti di computer, l’espressione Controllo di Ridondanza Ciclico è come un mantra. O forse sarebbe più realistico dire una maledizione.
Tale espressione appare infatti tutte le volte che il sistema operativo, nel tentativo di leggere i dati da un supporto, tipicamente un CD, non riesca a correggere gli errori che possono insorgere durante la lettura.
La persona chiave per l’argomento che andiamo ad affrontare è W. Wesley Peterson rappresentato nella foto a lato.
Wesley Peterson lavorava in IBM nello stesso periodo in cui Madelbrot faceva i suoi studi sulle linee di trasmissione e il suo contributo in questo campo fu la creazione del già menzionato metodo detto “Controllo di Ridondanza Ciclico”, utile per affrontare praticamente i problemi causati dal deterioramento dei segnali.

Per capire il funzionamento del CRC bisogna fare un piccolo sforzo per capire alcune proprieta della divisione fra polinomi.
L’intuizione di Peterson fu infatti quella di considerare i pacchetti di dati che costituiscono una trasmissione digitale come coefficienti di polinomi di grado n-1 dove n è il numero di bit (meno uno perchè le potenze si iniziano a contare da zero) che lo costitusicono. Cioè se i dati che vengono trasmessi sono costiuiti da singoli bytes da 8 bit, a ciascun byte può essere associato un polinomio di grado 7 in cui sono presenti tutte le potenze di x, da 0 a 7, che corrispondono ai bit diversi da 0 nel byte considerato. Per esempio:

Una volta stabilita questa equivalenza fra messaggio e polinomi, si possono fare una serie di ragionamenti sui polinomi stessi.
Se chiamiamo M il messaggio da trasmettere, possiamo pensare di effettuare una divisione fra M, che diventa il polinomio dividendo, e un particolare polinomio divisore che chiamiamo G. Come in qualsiasi divisione, il risultato sarà un polinomio quoziente, che chiameremo Q, e un resto, che chiameremo R.

Il trucco consiste nel mettere d’accordo il trasmettitore e il ricevitore nell’effettuare la divisione nello stesso modo, utilizzando un polinomio G, detto generatore, che sia standardizzato e noto a entrambi, e trasmettere, oltre al messaggio M anche il resto della divisione R.

Il messaggio trasmesso non sarà più M ma un qualcosa di più corposo che chiameremo T, che sarà quindi composto dalle cifre di M più delle cifre ridondanti, che sono appunto il resto della divisione cui abbiamo accennato.

Per far funzionare questo sistema è necessario che il polinomio G e la divisione stessa vengano effettuati con alcuni accorgimenti.
Innanzitutto il grado del polinomio G deve essere strettamente minore di M. Questo significa che, se vogliamo trasmettere messaggi da 8 bit dobbiamo scegliere dei polinomi generatori con al massimo 7 bit. Inoltre il polinomio generatore deve avere sempre il termine noto uguale a 1, per evitare di introdurre un inutile fattore comune x.
Sotto queste ipotesi, e indicando con p il grado del polinomio generatore, l’operazione che che viene effettuata è la seguente:

E il messaggio che viene effettivamente trasmesso è:

Tutto ciò ha un significato pratico ben preciso.
Da un punto di vista matematico, moltiplicare per x^p significa spostare la virgola a destra di p posizioni. In pratica aggiungere p zeri a destra del messaggio. E questa è un’operazione banale, sia per un essere umano che per una macchina di trasmissione.
Effettuare la sottrazione di R a questo punto, siccome R può contenere al massimo p cifre perchè è ottenuto mediante una divisione con un polinomio G di grado p, significa semplicemente sostituire R al posto degli zeri che abbiamo aggiunto. Quindi T non è altro che M e R messi uno di seguito all’altro.
Quando il messaggio trasmesso T raggiunge il ricevitore, questi può facilmente separare il resto dal messaggio perchè sa già quante sono le cifre p da considerare come resto.
Inoltre, dall’espressione di sopra possiamo renderci conto che, se il ricevitore effettua nuovamente la divisione di T diviso G, otterrà un risultato che ha resto nullo, indipendentemente da quale sia questo risultato. Infatti:

Questo ci permette, tra l’altro, di trascurare completamente l’esistenza di Q.
In altre parole, tutti i codici trasmessi con questo sistema sono multipli del polinomio generatore utilizzato per crearli.
Per utilizzare efficacemente queste proprietà delle operazioni fra polinomi nell’ambito della trasmissione dei segnali e, in particolare, per la correzione degli errori, è necessario aggiungere qualche dettaglio.
Le operazioni matematiche finora descritte, sottrazioni e divisioni, saranno da intendersi in modulo 2. Nella matematica in modulo 2 la somma e la sottrazione sono eseguite senza generare riporti o prestiti. In questo modo somma e sottrazione diventano equivalenti e sono implementabili in hardware tramite l’utilizzo di una porta .

La generazione del polinomio T da trasmettere si trasforma in una sequenza di operazioni XOR fra il messaggio e il polinomio generatore effettuato facendo scorrere opportunamente verso destra il polinomio G. Quando il polinomio G ha fatto n spostamenti verso destra, ciò che sarà rimasto del messaggio iniziale M sarà il resto della divisione modulo 2.
Nell’esempio seguente proviamo a codificare una parola binaria di 7 bit M=1000100 utilizando il polinomio generatore G=x³+1, cioè G=1001.

Nella parte sinistra dell’immagine si vede la divisione del messaggio M cui sono stati aggiunti 3 bit uguali a 0 destinati al resto dal momento che si sta usando un polinomio generatore di grado 3. Questo equivale a moltiplicare il polinomio per x³.
La divisione produce come risultato R=101.
Nella parte destra dell’immagine si vede l’operazione di di verifica in ricezione. Si prova a dividere il messaggio T, composto da M più il resto, ancora per il polinomio G e si trova resto nullo.

Questo significa che il messaggio è stato ricevuto senza errori.

Il sistema di trasmissione con CRC ha quindi il grande vantaggio di fornire un modo per individuare in maniera molto semplice se il messaggio ha subito un’alterazione.
Inoltre, attraverso una scelta opportuna del polinomio G è possibile anche individuare e correggere alcune categorie di errori e ricostruire il messaggio originale senza che sia necessario richiederne la ri-trasmissione.
Un poliniomio generatore a 16 bit, infatti, permette di individuare e correggere errori singoli e doppi, errori costituiti da un numero dispari di bit, errori a raffica (burst) di lungezza <= 16, 99.997% di errori a raffica lunghi 17, 99.998% di errori a raffica lunghi 18. Oggigiorno i codici CRC sono largamente usati e standardizzati. Ve ne sono una grande quantità e si differenziano principalmente per il tipo di polinomio generatore utilizzato, essendo questo scelto in funzione del tipo di dati che bisogna trasmettere. Alcuni formati in uso sono:

G=x¹⁶+x¹²+x⁵+1 (CRC CCITT)
G=x¹⁶+x¹⁶+x²+1 (CRC 16)
G=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1 (CRC 32 Ethernet FDDI)

Per esempio lo standard UMTS prevede l’uso, a seconda dei contesti, di 4 tipi di polinomio generatore a 8, 12, 16 e 24 bit.

Anche se, attraverso l’utilizzo dei codici CRC, abbiamo conseguito una vittoria notevole nei confronti degli errori, c’è stato un prezzo da pagare!
Infatti la possibilità di individuare e correggere gli errori di trasmissione ci costringe ad inserire nel messaggio un certo grado di ridondanza. Nell’esempio precedente, per trasmettere 8 bit di messaggio, abbiamo aggiunto 3 bit di codice CRC. Quindi la trasmissione in sè è leggermente meno efficiente perchè richiede la trasmissione di 11 bit per essere sicuri di riceverne 8.
Anche in questo caso siamo stati costretti a scendere a patti con l’errore!