01. Il CRC

Il controllo ciclico di ridondanza (CRC) è una tecnica di controllo degli errori molto usata, ad esempio nelle reti Ethernet.

Essa consiste nel proteggere i dati da trasmettere con un codice di controllo (detto CRC), calcolato con l'ausilio dell'aritmetica modulare (che prevede l'analisi dei resti) tra polinomi.

Ad ogni sequenze binaria è associato un polinomio i cui coefficienti corrispondono alla sequenza binaria. Così, per esempio, la sequenza di dieci cifre binarie  0110101001 può essere associata al polinomio di grado 9:

0*x9 + 1*x8 + 1*x7 + 0*x6 + 1*x5 + 0*x4 + 1*x3 + 0*x2 + 0*x1 + 1*x0 

Sia M una sequenza di bit di lunghezza predefinita, con M(x) rappresentiamo il polinomio associato. 

Sia ancora G(x) un polinomio predefinito (detto polinomio generatore) di grado inferiore a M(x). Per fissare le idee sia

 G(x) = 1*x3 + 0*x2 + 0*x1 + 1*x0

Sia M' un messaggio ottenuto da M aggiungendo alcuni bit (il codice CRC) tale che il resto della divisione polinomiale tra M'(x) e G(x) sia uguale a 0; cioè:

Resto[M'(x) / G(x)] = 0

Il messaggio M' corrisponde alla sequenza da spedire.

Il ricevente del messaggio M' può verificarne la correttezza semplicemente controllando il resto della divisione tra i polinomi M'(x) e G(x).

Nella pratica i polinomi generatori sono standardizzati e sono di grado 12, 16 o 32.  

Calcolo del CRC

Il calcolo del CRC, come detto, utilizza l'aritmetica modulare tra i polinomi. Questa operazione è estremamente semplice e si implementa eseguendo in cascata una successione di XOR termine a termine, come illustra il seguente esempio:

Consideriamo un generico polinomio M(x) e un secondo polinomio G(x) di grado inferiore.

M(x)=0*x9 + 1*x8 + 1*x7 + 0*x6 + 1*x5 + 0*x4 + 1*x3 + 0*x2 + 0*x1 + 1*x0

G(x) = 1*x3 + 0*x2 + 0*x1 + 1*x0

Per effettuare la divisione modulare tra i due polinomi si procede in modo simile a come si opera con i numeri con le seguenti differenze:

• si valuta che il divisore ci sta nel dividendo non quando il dividendo è realmente maggiore del divisore, ma quando ha lo stesso ordine di grandezza, vale a dire quando il suo bit più significativo vale 1;

• la sottrazione per ridurre il dividendo deve essere fatta senza riporti, utilizzando l'operatore XOR.

Procedendo con l'esempio si ha:

In rosso sono mostrati i valori ottenuti applicando l'operatore XOR tra i termini in colonna.

Da evidenziare che il risultato che interessa  ai fini del CRC è esclusivamente il resto.

R(x) =  1*x1 + 0*x0

Un esempio numerico

Il procedimento utilizzato per il calcolo del CRC potrebbe funzionare in modo analogo con sequenze numeriche qualsiasi, senza necessità di richiamare l'aritmetica modulare tra i polinomi.

Il vantaggio introdotto dalla divisione modulare tra polinomi è algoritmico, in quanto si tratta di un'operazione estremamente meno complessa della divisione ordinaria.  

Proseguendo nell'analogia fissiamo un numero G che chiameremo generatore (ad esempio 999) e un numero molto più grande M (ad esempio 345678912) per il quale calcoleremo un CRCn (analogo al CRC per procedimento ma utilizzando la divisione ordinaria tra numeri decimali).

Il massimo resto che può produrre la divisione M/G è di 3 cifre, quindi estendiamo M di 3 cifre

Me = 345678912000

R = Me % G = 936

La sequenza numerica M estesa con il CRCn (evidenziato in verde) sarà:

M' = Me + (G - R) = 345678912000 + (999 - 936) = 345678912063

Osserviamo esplicitamente che:

M' % G = 345678912063 % 999 = 0

Cambiando una o più cifre casualmente a M' è altamente improbabile (all'incirca 1 su 1000) riuscire ad ottenere una sequenza che continui a godere di tale proprietà.

Sito:  7ecnologie

Sezione: 13. Reti

Capitolo: 01. Le telecomunicazioni

Paragrafo:  06. Rilevazione degli errori

Approfondimento: 01. Il CRC

Indice dei capitoli: 00. Risorse - 01. Le telecomunicazioni - 02. Il modello OSI - 03. La suite TCP/IP - 04. Il cablaggio strutturato - 05. LAB - 07. Tutorial - 98. Esercizi

Indice dei paragrafi: 01. La standardizzazione - 02. Classificazione per estensione - 03. Tipologie di comunicazione - 04. Modalità di interconnessione - 05. I segnali - 06. Rilevazione degli errori

Indice degli approfondimenti: 01. Il CRC