|
Il '''''cyclic redundancy check''''' (ovvero '''controllo a ridondanza ciclica''', il cui acronimo '''CRC''' è invece ben più diffuso) è un metodo per il calcolo di [[somma di controllo|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]].<ref>
{{Cita pubblicazione
| autore = Peterson, W. Wκ. and Brown, D. T.
| anno = 1961
| mese = gennaio
| titolo = Cyclic Codes for Error Detection
| rivista = Proceedings of the IRE
| doi = 10.1109/JRPROC.1961.287814
| issn = 0096-8390
}} - The original paper on CRCs
</ref>
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 [[hash|algoritmi di hash]] quali MD5 e SHA1, più robusti seppur computazionalmente meno efficienti.
== Implementazione ==
[[File:CRC8-gen.gif|right|thumb|250px|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
<math> x^{16} + x^{12} + x^5 + 1</math>.
Il calcolo del CRC inizia con il messaggio che viene associato a un polinomio <math>b(x)</math> di grado pari al numero di bit del messaggio meno uno, grado che indicheremo con <math>n-1</math>.
Per esempio, il messaggio 10011010 (<math>n-1=7</math>) produce il polinomio
<math> b(x) = x^7 + x^4 + x^3 + x^1</math>
Supponendo che il CRC abbia un polinomio <math>g(x)</math> di grado <math>g</math>, si "trasla" a sinistra il polinomio <math>b(x)</math> di <math>g</math> posizioni, ottenendo il polinomio <math>p(x)</math> di grado (<math>h=n-1+g</math>).
Nell'esempio, supponendo un grado <math>g=4</math> si ottiene:
<math>p(x)=x^g * b(x)</math>
Si esegue ora la divisione <math>p(x)/g(x)</math> ottenendo un quoziente <math>q(x)</math> e un resto <math>r(x)</math>. Tale divisione viene svolta con la ''[[Divisione dei polinomi|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 [[Disgiunzione esclusiva|XOR]].
Il messaggio inviato lungo il canale è formato dall'unione del messaggio <math>p(x)</math> meno il resto della divisione <math>r(x)</math>.
<math>m(x) = p(x) - r(x) </math>
Visto che <math>r(x)</math> è il resto di una divisione che usa come divisore <math>g(x)</math>, questo resto ha un grado strettamente inferiore a quello di <math>g(x)</math>; ricordando inoltre che <math>p(x)</math> è ottenuto prendendo il messaggio da inviare <math>b(x)</math> e traslandolo di g posizioni cioè del grado del polinomio <math>g(x)</math>, si ottiene che i polinomi <math>p(x)</math> e <math>r(x)</math>, quando vengono sommati, non si sovrappongono nei termini di ugual grado e si può quindi assumere che il messaggio <math>b(x)</math> viene inviato "inalterato".
<math>p(x)</math> è definibile anche come
<math>p(x)= q(x)*g(x)+r(x)</math>
Cioè il polinomio è uguale al quoziente per il divisore più il resto. Sostituendo questa descrizione nella formula precedente otteniamo che <math>m(x)</math> diventa:
<math>m(x) = q(x) * g(x) + r(x) - r(x)</math>
Per le leggi dell'algebra sui [[campo (matematica)|campi finiti]], sottraendo un polinomio a se stesso, si ottiene un polinomio nullo, pertanto <math>m(x)</math> diviene:
<math>m(x) = q(x) * g(x) </math>
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 <math>m(x)</math> e lo divide per il polinomio <math>g(x)</math> 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 <math>m(x)</math> a destra di un grado g per ottenere il messaggio <math>b(x)</math> di partenza.
== Note ==
<references/>
== Voci correlate ==
*[[Livello di collegamento dati#Controllo di errore|Livello di collegamento dati]]
{{portale|informatica|matematica|telematica}}
[[Categoria:File system]]
[[Categoria:Teoria dei codici]]
| 