CRC_16 

Routine per il calcolo del CRC (Cyclic Redundancy Check) con  micro Microchip . Essa permette di calcolare il CRC a 16 bit  per una parola dato di 8/16 bit. Il polinomio generatore può essere cambiato e si può scegliere tra quelli standard commentando/s-commentando alcune righe nel file sorgente. La routine utilizza l'indirizzamento indiretto ( mediante i registri FSR e INDF) che permette di ottimizzarla. Inoltre viene fornito una semplice routine per testare la routine del CRC (TEST_CRC.ASM) utilizzando il simulatore presente nel programma MPASM.

CRC (Cyclic Redundancy Check)

 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 per rilevare la presenza d’eventuali errori, è standardizzato. Esistono dei polinomi standard normalmente riconosciuti:

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.

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