CYCLIC REDUNDANCY CHECK

Controllo ciclico di ridondanza

La tecnica di rivelazione degli errori di trasmissione si  avvale di due metodi :

 1)     Ridondanza di codice (Character Mode) ottenuta aggiungendo al momento della trasmissione un bit di ridondanza alla stringa da inviare

2)      Ridondanza di blocco (Block Mode) che consiste nell’aggiunta di  n di bit di ridondanza.

Nell’ambito della  ridondanza di blocco, utilizzata prevalentemente nella trasmissione sincrona di gruppi di caratteri, particolare importanza riveste la modalità di rivelazione detta CRC (Cyclic Redundancy Check).   
Il CRC è caratterizzato dalla proprietà di aggiungere alla fine di un blocco una serie di bit in numero di 12 o 16 ( CRC-12 o CRC-16) corrispondenti ai coefficienti di un polinomio ottenuto come resto della divisione tra un polinomio prefissato (detto polinomio generatore  g ) e il blocco di caratteri da  trasmettere. Ovviamente il ricevente deve eseguire un’operazione identica, in modo tale che il confronto tra i due resti fornisca la conferma della correttezza della trasmissione. Il polinomio generatore  g, che  deve essere lo stesso per il ricevente e il trasmittente, usato per rilevare la presenza d’eventuali errori, è standardizzato. Esistono dei polinomi standard normalmente riconosciuti: 

In seguito è  riportata una trattazione matematica del CRC.
Consideriamo una parola di n bit che vogliamo trasmettere ( bn-1,….bo). Fissiamo un polinomio generatore  g(x)  con grado g £ n-1. Alla stringa ( bn-1,….bo) cui corrisponde il Polinomio b(x), sarà aggiunto un blocco di g bits che sono i coefficienti del polinomio resto derivante dalla divisione del polinomio g(x) scelto b(x) ovvero r(x). Il primo passo consiste nell’aggiungere g bit zero in coda al blocco da trasmettere. In termini di polinomio vuol dire moltiplicare b(x) per x^g 

p(x)= x^g * b(x)  

quindi p(x) può essere scritto in funzione di g(x) dove q(x) e r(x) sono il quoziente e il resto della divisione tra p(x) e g(x).

             p(x)=q(x)*g(x)+r(x)

 La stringa che trasmetteremo è l’unione tra il blocco ( bn-1,….bo) e il blocco di g bit ( rg-1, r0). Il che equivale a sostituire in p(x) i g bit a zero introdotti all’inizio. In termini di matematica binaria corrisponde alla funzione xor quindi si trasmetterà la stringa corrispondente al polinomio: 

            m(x) = p(x)+r(x) = q(x)*g(x)+r(x) +r(x) = q(x)*g(x)

 essendo  r(x) +r(x) = 0 ovvero in aritmetica binaria la somma ( xor )di due quantità uguali è zero.
Quindi la stringa trasmessa m(x) è perfettamente divisibile per g(x). Questo significa che il ricevente, dividendo m(x) per g( x) che conosce, dovrà avere un resto nullo se non ci sono errori.
Il successo di questo tipo di codice è legato alla sua efficienza ma anche alla semplicità con cui è possibile implementarlo a livello hardware. Infatti bastano solo porte logiche EX-OR (exclusive OR) e  registri a scorrimento (shift register )   

E' possibile realizzare routine di CRC per microcontrollore come al seguente link