Cyclic redundancy check

Da Wikipedia, l'enciclopedia libera.

Il cyclic redundancy check (ovvero controllo a ridondanza ciclica, il cui acronimo CRC è invece ben più diffuso) è un metodo per il calcolo di somme di controllo (checksum in inglese). Il nome deriva dal fatto che i dati d'uscita sono ottenuti elaborando i dati di ingresso i quali vengono fatti scorrere ciclicamente in una rete logica. Il controllo CRC è molto diffuso perché la sua implementazione binaria è semplice da realizzare, richiede conoscenze matematiche modeste per la stima degli errori e si presta bene a rilevare errori di trasmissione su linee affette da elevato rumore di fondo. Le tecniche CRC furono inventate da W. Wesley Peterson che pubblicò il suo primo lavoro sull'argomento nel 1961.[1]

Utile per l'individuazione di errori casuali nella trasmissione dati (a causa di interferenze, rumore di linea, distorsione), il CRC non è invece affidabile per verificare la completa correttezza dei dati contro tentativi intenzionali di manomissione. A tal fine sono utilizzati algoritmi di hash quali MD5 e SHA1, più robusti seppur computazionalmente meno efficienti.

Implementazione[modifica | modifica wikitesto]

Rappresentazione del meccanismo interno del CRC-8.

Il CRC prevede la generazione di una stringa di bit di controllo che viene normalmente trasmessa assieme ai dati e il calcolo è basato sull'aritmetica modulare. Un codice CRC è definito dal suo polinomio generatore: ad esempio il codice CRC-16-CCITT, molto usato in ambito di telecomunicazioni, è definito dal polinomio generatore  x^{16} + x^{12} + x^5 + 1.

Il calcolo del CRC inizia con il messaggio che viene associato a un polinomio b(x) di grado pari al numero di bit del messaggio meno uno, grado che indicheremo con n-1.

Per esempio, il messaggio 10011010 (n-1=7) produce il polinomio

 b(x) = x^7 + x^4 + x^3 + x^1

Supponendo che il CRC abbia un polinomio g(x) di grado g, si "trasla" a sinistra il polinomio b(x) di g posizioni, ottenendo il polinomio p(x) di grado (h=n-1+g).

Nell'esempio, supponendo un grado g=4 si ottiene:

p(x)=x^g * b(x)

Si esegue ora la divisione p(x)/g(x) ottenendo un quoziente q(x) e un resto r(x). Tale divisione viene svolta con la lunga divisione dell'aritmetica modulo 2, ovvero non si fanno riporti: ricordiamo che nell'aritmetica modulo 2 la somma e la sottrazione sono eseguibili utilizzando la funzione logica XOR. Il messaggio inviato lungo il canale è formato dall'unione del messaggio p(x) meno il resto della divisione r(x).

m(x) = p(x) - r(x)

Visto che r(x) è il resto di una divisione che usa come divisore g(x), questo resto ha un grado strettamente inferiore a quello di g(x); ricordando inoltre che p(x) è ottenuto prendendo il messaggio da inviare b(x) e traslandolo di g posizioni cioè del grado del polinomio g(x), si ottiene che i polinomi p(x) e r(x), quando vengono sommati, non si sovrappongono nei termini di ugual grado e si può quindi assumere che il messaggio b(x) viene inviato "inalterato".

p(x) è definibile anche come

p(x)= q(x)*g(x)+r(x)

Cioè il polinomio è uguale al quoziente per il divisore più il resto. Sostituendo questa descrizione nella formula precedente otteniamo che m(x) diventa:

m(x) = q(x) * g(x) + r(x) - r(x)

Per le leggi dell'algebra sui campi finiti, sottraendo un polinomio a se stesso, si ottiene un polinomio nullo, pertanto m(x) diviene:

m(x) = q(x) * g(x)

Si nota che il messaggio è quindi divisibile per il polinomio generatore con resto nullo. La rilevazione degli errori usa questa proprietà, difatti il ricevitore riceve m(x) e lo divide per il polinomio g(x) che è definito precedentemente. Se il messaggio è stato ricevuto inalterato la divisione non produce resto mentre se si sono verificati errori di trasmissione la divisione produrrà un resto. La presenza di errori multipli potrebbe produrre comunque una divisione senza resto in un messaggio errato. La probabilità che questo accada dipende dal polinomio e dal suo grado e statisticamente si dimostra che questo accade raramente.

Nel caso il messaggio dia resto nullo basta traslare m(x) a destra di un grado g per ottenere il messaggio b(x) di partenza.

Note[modifica | modifica wikitesto]

  1. ^ Peterson, W. Wκ. and Brown, D. T., Cyclic Codes for Error Detection in Proceedings of the IRE, gennaio 1961, DOI:10.1109/JRPROC.1961.287814, ISSN 0096-8390. - The original paper on CRCs

Voci correlate[modifica | modifica wikitesto]