Il CRC: i polinomi di bit

Avete in mente i segnali di fumo usati dagli indiani per comunicare? Ecco la comunicazione seriale tra un pc e un dispositivo può essere facilmente assimilata alle nuvole di fumo (1) intervallate da buchi (0) bianchi.  Il problema è quello di verificare che la sequenza di 1 e 0 arrivi al destinatario esattamente come il mittente l'aveva prevista. Sono molte infatti le cause per cui un messaggio potrebbe arrivare corrotto al ricevente e ovviamente le conseguenze, specie nei sistemi elettronici di sicurezza, potrebbero essere dannose e pericolose.

Una possibilità è di inviare insieme al messaggio anche un codice di verifica, generato a partire dal messaggio, e che possa essere utilizzato per verificarne l'integrità. Questo codice di controllo prende il nome di CRC ovvero cyclic redundant code: è ciclico per il modo in cui viene calcolato su tutti i byte che compongono il messaggio ed è ridondante perché all'interno del codice non ci sono informazioni nuove rispetto al messaggio e quindi se vogliamo è uno spreco di risorse, se non fosse che ci garantisce l'integrità del resto del messaggio.



Vi parlo di queste cose perché la scorsa settimana in laboratorio abbiamo collegato due famiglie di strumenti al computer per la prima volta; la comunicazione era per via seriale (RS485 su ethernet) e in entrambi i casi insieme al messaggio era inviato anche un checksum, ovvero il codice di controllo, e ovviamente era calcolato in modo differente nei due strumenti. Ogni manuale che si rispetti, deve fornire le istruzioni su come calcolare questo codice, ma è altrettanto importante fornire anche un esempio per verificare che lo si sta facendo bene. Manco a dirlo, per il primo strumento avevamo trovato un esempio, mentre per il secondo si diceva che il CRC era calcolato usando - cito testualmente - SDLC CRC polynomial e forniva uno stralcio di codice C che non compila se non dopo essere stato un po' rimaneggiato. Il codice modificato e commentato è riportato qui sotto.

unsigned short get_crc( unsigned char * buffer, int count ) {

 // algoritmo per il calcolo del CRC
 // usando lo standard CRC-CCITT (XMODEM)
 // polinomio generatore G(x) = 0x8408

 unsigned short code;
 unsigned short crc ;
 
 crc = 0;
 
 while ( count-- ) {

  // code è una variabile di supporto utilizzata
  // per i calcoli.
  // crc contiene il valore del codice di controllo 
  // ed è di 16 bit. 
  code = ( crc >> 8 ) &  0xFF;

  // buffer è il puntatore al byte di cui si sta calcolando
  // il crc. E' a 8 bit, mentre le altre variabili sono a 16.
  code ^= ( *buffer++ & 0xFF );
  
  // l'operatore ^ è XOR mentre
  // gli operatori >> e << sono gli shift a destra
  // e a sinistra rispettivamente

  code ^= code >> 4;
  crc <<= 8;
  crc ^= code ;
  code <<= 5 ;
  crc ^= code;
  code <<= 7;
  crc ^= code;
 }
 return crc;
}

Come vedete il codice è scritto in modo da essere molto compresso e tutti quegli operatori binari lo rendono particolarmente ostico a chi non è troppo addentro. Così è forse meglio se facciamo una pausa per costruirci le basi prima di continuare.

I polinomi

E' inevitabile cadere nelle grinfie di Thot, la divinità egizia della matematica. Sappiamo che ogni elemento di un messaggio da trasmettere può essere suddiviso in byte e che ognuno di essi è composto da 8 bit che possono assumere solo i valori 1 e 0. Ogni byte è quindi una sequenza di 1 e 0 tipo: 01000101 (corrisponde al decimale 69, all'esadecimale 0x45 e al carattere ASCII E). A questa sequenza di bit possiamo associare un polinomio in cui i coefficienti dei vari ordini sono proprio questi numeri. Come nella formula sotto:

  
Nella seconda riga, abbiamo semplificato il polinomio, rimuovendo gli ordini con coefficienti nulli e ricordando che qualunque numero elevato alla 0 è uguale a 1. La tecnica per il calcolo del CRC si basa sulla divisione divisione di due polinomi, il messaggio vero e proprio e il cosiddetto polinomio generatore dell'algoritmo. In formula, possiamo esprimere questo concetto scrivendo:


Come prima cosa moltiplichiamo il messaggio per x alla n, che equivale ad aggiungere n bit a sinistra del messaggio per fare spazio al CRC. A destra dell'uguale abbiamo il risultato della divisione, infatti Q rappresenta il quoziente, G il polinomio generatore ed R è l'eventuale resto. E' proprio R che ci interessa e che contiene il codice di controllo da aggiungere al messaggio.

Due polinomi generatori G e G' differenti generano resti e quindi codici di controllo differenti. Per questo motivo, non basta dire di aver calcolato il CRC di un messaggio, ma bisogna anche specificare il polinomio generatore.

Nel caso di un messaggio multi-byte, le cose si complicano ulteriormente per colpa dell'endianess, ovvero l'ordine dei byte all'interno della parola

Ma non è troppo difficile?

La prima reazione di fronte a queste formule potrebbe essere di spavento. Fare moltiplicazioni e divisioni tra polinomi non è certo una cosa facile, a meno che, questi polinomi non siano in realtà delle sequenze di bit e che i polinomi abbiano coefficienti all'interno della classe di modulo resto 2 (che è il modo matematicamente corretto per definire l'algebra dei numeri binari). In questo caso, moltiplicare un numero per un altro significa spostare verso i posti alti i bit, mentre per dividere basta spostare verso i posti meno significativi. Adesso vi saranno più chiare le operazioni << e >> nel pezzetto di codice riportato sopra.

Da fare a mano, sulla carta queste traslazioni di bit (moltiplicazioni e divisioni) sarebbero comunque troppo difficili, ma nei computer esistono apposite porte logiche, chiamate registro a scorrimento realizzati apposta per eseguire queste operazioni.

Due consigli

Il primo è imprescindibile. Lo ragione di esistere di un CRC è quella di essere controllata, quindi quando state scrivendo un programma e non vi prendete la briga di controllare sempre il CRC dei dati in arrivo, non lamentatevi se poi dopo finite nei guai.

La seconda è munitevi di tanta pazienza e se non avete voglia di riprendere in mano l'algebra, memorizzatevi tra i preferiti questo sito internet, almeno potrete fare tutte le prove che volete.