Rilevazione errori con CRC – come funziona

rilevazioni errori CRC copertina 1024
rilevazioni errori CRC copertina 1024
5
(2)

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⋅x3) + (1⋅x2) + (1⋅x1) + (0⋅x0) = x3 + x2 + x1 → Grado 3

 

G(x) = 101

G(x) = (1⋅x2) + (0⋅x1) + (1⋅x0) = x2 + 1 → Grado 2

 

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

Sequenza dati e aggiunta dei bit a zero

 

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

Calcolo del codice rilvatore CRC

Aggiungere il CRC alla parte dati

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

Sequenza con dati e CRC

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.

Calcolo per la verifica della correttezza dei dati ricevuti

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

Calcolo per la verifica dei dati ricevuti con errore

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

Votalo e aiutami a migliorare!

Rating medio 5 / 5. Numero di voti 2

Nessun voto per il momento, vuoi essere il primo?

Clicca sul tuo social preferito.

Cosa ho sbagliato?

Hai qualche consiglio per migliorare la qualità?

Potrebbero interessarti anche...

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.