Rilevazione errori con CRC – come funziona

Vi è mai capitato di incappare in qualche errore durante il salvataggio o il trasferimento di un file e provando ad aprirlo o utilizzarlo esso risultasse corrotto? Se la risposta è sì allora la prossima domanda è: vi siete mai chiesti come si riesca a rilevare l’errore?

Benvenuti nel mondo dei codici rilevatori!

Da sempre si è dovuto far fronte al problema della corruzione dei dati, in quanto l’errore può capitare. Le tecniche che vengono utilizzate sono diverse: bit di parità, checksum, codici di Hamming, CRC, ecc.

Nello specifico vedremo come si calcola e come si utilizzata il CRC.

Innanzitutto il CRC (Ciclic Redundancy Check) o codice a ridondanza ciclica è un codice adatto a riscontrare errori di tipo “burst” o a raffica, ovvero errori che compromettono più bit consecutivi. Questo tipo di codice viene anche chiamato codice polinomiale in quanto i bit di dati da controllare possono essere considerati come coefficienti (di valore 0 o 1) di un polinomio che chiameremo M(x). Per calcolare il CRC, oltre al polinomio che rappresenta l’informazione da trasmettere, abbiamo bisogno di un polinomio detto generatore che chiameremo G(x) e che dovrà rispettare alcune regole:

• G(x) deve essere noto sia al mittente che al destinatario
• I bit di G(x) di ordine più alto e più basso devono essere a 1
• il grado di M(x) deve essere maggiore di quello di G(x).

Calcolare CRC

Definiamo le sequenze di bit che utilizzeremo (dati e generatore) e i rispettivi polinomi:

M(x) = 1110

M(x) = (1⋅x³) + (1⋅x²) + (1⋅x¹) + (0⋅x⁰) = x³ + x² + x¹ → Grado 3

 

G(x) = 101

G(x) = (1⋅x²) + (0⋅x¹) + (1⋅x⁰) = x² + 1 → Grado 2

 

A questo punto “appendiamo” ai bit di M(x) un numero di zeri pari al grado del polinomio G(x):

 

Fatto ciò dividiamo la nuova sequenza per G(x). La parte che ci interessa è il resto. Per fare questa divisione possiamo avvalerci della tabella di verità dell’operatore logico XOR (OR esclusivo):

Aggiungere il CRC alla parte dati

Dopo aver calcolato il codice di controllo CRC appendiamolo alla nostra sequenza di dati:

La sequenza ottenuta verrà spedita al destinatario.

Verifica integrità dati

Una volta che la sequenza è arrivata a destinazione dobbiamo verificarne la correttezza, quindi dividiamo la sequenza per il generatore G(x), che come abbiamo detto prima è noto sia al mittente che al destinatario. Per questa operazione valgono le stesse regole che abbiamo usato in precedenza.

Anche in questo caso dobbiamo porre la nostra attenzione sul resto della divisione. Se il resto è diverso da 0 si è verificato un errore.

Il risultato è privo di resto, di conseguenza i dati ricevuti sono corretti.

Ora proviamo a vedere cosa succederebbe se la sequenza subisse delle modifiche durante l’invio (in rosso sono evidenziate le modifiche):

Come possiamo notare la divisione ci darebbe un resto, quindi i dati ricevuti sarebbero erronei.

Inoltre volevo sottolineare che per la bontà del metodo la scelta del polinomio generatore è molto importante e negli anni si sono affermati diversi tipi di standard. Se vuoi dare un’occhiata clicca qui.

Siamo arrivati alla fine! Se sei interessato a fare altri calcoli prova a vedere come calcolare la subnet mask e gli indirizzi di sottorete, oppure lascia un commento e fammi sapere cosa ne pensi dei codici rilevatori.

A presto,

Gabriele