Cyclic Redundancy Check (CRC) – Concetti basilari

crc_00.jpg

Lo scopo di questo articolo è quello di presentare i concetti basilari relativi al CRC (acronimo di Cyclic Redundancy Check), un modo efficiente ed ampiamente utilizzato per proteggere le informazioni da corruzioni di tipo accidentale.

CRC è l’acronimo di Cyclic Redundancy Check, e rappresenta una funzione il cui ingresso è un insieme di byte (detto anche byte stream), e la cui uscita è un valore numerico, solitamente un intero a 16 oppure 32 bit. Il termine CRC viene utilizzato per riferirsi sia alla funzione che al valore da essa calcolato. Il flusso di dati su cui si calcola il CRC può essere di vario tipo: un file appartenente ad un determinato file system, un array di byte memorizzato in memoria (RAM, ROM, oppure NVRAM), un flusso di byte oppure un pacchetto dati che scorre all’interno di una rete, e così via. Lo scopo principale del CRC è quello di permettere il rilevamento di errori in grado di compromettere l’integrità dei dati, agendo in questo modo come un controllo di validità associato ad una specifica struttura dati. Di seguito vengono proposti alcuni esempi:

  • Se il CRC viene associato a ciascun file appartenente ad un file system, il sistema operativo sarà in grado di controllare l’integrità del file stesso prima di consentire qualunque accesso ad esso. Esistono varie ragioni che possono causare la corruzione di un file (penso che la maggior parte di noi abbia vissuto quest’esperienza almeno una volta): un errore che si verifica durante il trasferimento verso/da un dispositivo esterno, un guasto che interessa il dispositivo fisico sul quale è memorizzato il file, uno spegnimento improvviso ed indesiderato del sistema durante un’operazione di scrittura, un virus software (purtroppo anche questo può avvenire), e così via
  • Consideriamo ora l’immagine binaria di un’applicazione in esecuzione su un sistema embedded (se il sistema è recente, essa probabilmente risiederà in una memoria flash, esterna oppure integrata in un microcontrollore; se invece il sistema è più datato, sarà probabilmente contenuta all’interno di una memoria eprom). Se noi calcolassimo il CRC di questa immagine ogni volta che il firmware viene aggiornato e tenessimo traccia di questo valore, avremmo a disposizione uno strumento per controllare, a piacimento, se il firmware stesso corrisponde alla versione che noi ci aspettiamo. Ciò fornisce un potente mezzo sia per verificare l’integrità dell’immagine, sia per individuare se è stata compiuta un’azione di manomissione/contraffazione ad opera di qualche malintenzionato per alterare il codice originale. Questo aspetto è di fondamentale importanza nelle apparecchiature elettroniche di misurazione ed in quelle destinate a varie forme di pagamento elettronico
  • Se il CRC viene associato ad un pacchetto dati scambiato tra due o più nodi appartenenti ad una rete o ad un bus, controllando il CRC di ciascun pacchetto ricevuto sarà possibile rilevare una corruzione dei dati. Come conseguenza, l’errore potrebbe poi essere recuperato tramite una ri-trasmissione del pacchetto, oppure semplicemente fornendo una segnalazione di errore di trasmissione al gestore degli allarmi

Il polinomio generatore

L’idea basilare che sta dietro ogni algoritmo per il calcolo del CRC è abbastanza semplice: trattare il flusso di dati come un enorme numero binario, dividerlo per un altro numero binario fisso (costante), ed utilizzare il resto di questa divisione come valore di CRC.

In realtà, il divisore, il dividendo (il flusso dati), il quoziente, ed il resto non vanno considerati come interi positivi, ma piuttosto come polinomi con coefficienti binari. Questo avviene considerando ciascuno di questi numeri come una sequenza di bit che non sono altro che i coefficienti di un polinomio. Vediamo come ciò avviene con un esempio: ilnumero decimale 35 viene rappresentato come 23H in esadecimale, e 100011 in formato binario. Se ai bit vengono fatti corrispondere i coefficienti di un polinomio, il numero rappresenterebbe anche il seguente polinomio: 1*x5+0*x4+0*x3+0*x2+1*x1+1*x0, that is x5 + x1 + 1.
Al fine di eseguire il calcolo del CRC, la prima cosa da fare è quella di scegliere un divisore, che tecnicamente viene definito come il “polinomio generatore”.

Un’importante proprietà del polinomio generatore è l’ampiezza (width), definite come la posizione del suo bit più significativo con valore 1. Valori tipici per l’ampiezza sono 16 e 32, perchè essi semplificano l’implementazione dell’algoritmo sui normali computer. Per esempio, l’ampiezza del polinomio generatore considerato nell’esempio precedente è 5 (e non 6). Si noti come il bit più significativo del polinomio scelto come divisore venga usualmente omesso nella rappresentazione del divisore stesso; ciò perchè questo bit normalmente ha valore 1.
Alcuni polinomi generatori comunemente usati sono I seguenti:

  • CRC-8-ATM: viene utilizzato per calcolare il valore del campo HEC della cella ATM (Asynchronous Transfer Mode). Il polinomio è x8 + x2 + x + 1, e la corrispondente rappresentazione è 0x07
  • CRC-8-CCITT: viene utilizzato per I dispositive che operano sul bus 1-Wire (Maxim/Dallas ha anche introdotto un altro tipo di CRC leggermente diverso da questo). Il polinomio è x8 + x7 + x3 + x2 + 1, e la corrispondente rappresentazione è 0x8D
  • CRC-16 CCITT: viene impiegato in svariate applicazioni tra cui: Bluetooth, X.25, XMODEM, PPP, ecc. Il polinomio è x16 + x12 + x5 + 1, e la corrispondente rappresentazione è 0x1021

L’algoritmo

Vediamo ora un algoritmo molto semplice in grado di eseguire il calcolo del CRC per ogni valore di ampiezza selezionato. Occorre anzitutto implementare la divisione CRC: una volta risolto questo problema, l’algoritmo è praticamente terminato.

Il calcolo del CRC fa riferimento a un insieme di dati (per esempio un messaggio oppure un array) costituito da una sequenza di byte con il bit 7 di ciascun byte come bit più significativo (MSB). Di conseguenza, avremo a che fare con un flusso di dati composto da una sequenza di bit.
Anzitutto, occorre scegliere un polinomio. Successivamnte, il calcolo consiste in una divisione tra il flusso di bit ed il polinomio. Un numero W di bit uguali a zero deve essere appeso al flusso di bit prima di eseguire la divisione, essendo W l’ampiezza delpolinomio. Il calcolo del CRC viene eseguito in binario senza riporti o prestiti, cioè:

  • 0+0=0
  • 0+1=1
  • 1+0=1
  • 1+1=0 (nessun riporto)

Ciò significa che nella matematica del CRC (o meglio, nella matematica dei polinomi) l’addizione e la sottrazione possono essere eseguite tramite la funzione XOR. Tutte le operazioni sono eseguite tramite un registro a scorrimento a sinistra R con un numero di bit uguale all’ampiezza del polinomio, cioè W.
L’algoritmo consiste dei seguenti passi:

  1. aumento del messaggio aggiungendo W bit 0 alla sua fine
  2. caricare il registro R con bit tutti a 0
  3. se esistono ancora bit da processare eseguire lo step 4, altrimenti saltare allo step 7
  4. far scorrere verso sinistra di 1 bit il registro R, caricando il prossimo bit del messaggio nel bit di posizione 0 del registro
  5. se dal registro esce un bit a 1 (cioè se il bit più significativo del registro prima di eseguire lo shift era un 1) porre: R = R XOR polinomio
  6. saltare allo step 3
  7. il registro R contiene ora il resto, cioè il CRC

Sovente, nelle applicazioni relative ai protocolli di comunicazione (come l’Ethernet), il CRC viene aggiunto alla fine del messaggio prima di eseguire la trasmissione. Lato ricevente, è possible sia ricalcolare il CRC e confrontarlo con quello ricevuto, o più semplicemente calcolare il CRC su tutto il messaggio ricevuto: se non si sono verificati errori, il risultato sarà uguale a 0.

Un esempio

Si consideri il seguente esempio:

  • messaggio composto di soli due byte: 0x32,0x24
  • polinomio generatore: 10011, cioè W=4
  • messaggio in formato binario, aumentato con W bit a 0: 0011 0010 0010 0100 0000

Appicando l’algoritmo, otterremo un CRC (il resto) uguale a 1101 (0x0D)

Conclusioni

Questo semplice algoritmo è stato presentato perchè può essere facilmente implementato con blocchi hardware. Dal punto di vista software, esso non è molto efficente poichè richiede molte operazioni sui bit (XOR e shift). Esiste un altro algoritmo che è più veloce e richiede meno risorse, e si basa su una lookup table pre-formattata. Noi siamo maggiormente interessati alla versione basata sullo shift register perchè in un successivo articolo vedremo che questo è il metodo usato per implementare il calcolo del CRC, a livello hardware, nella famiglia di microcontrollori Freescale Flexis AC.

6 Comments

  1. linus 9 febbraio 2011
  2. Fabrizio87 9 febbraio 2011
  3. giuskina 10 febbraio 2011
  4. NIck_BG 10 febbraio 2011
  5. Alex87ai 9 febbraio 2011
  6. Alex87ai 9 febbraio 2011

Leave a Reply