Cyclic redundancy check
# Cyclic redundancy check

Il controllo di ridondanza ciclico o cyclic redundancy check (CRC) è un metodo per il calcolo di somme di controllo (checksum). 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 Wesley Peterson che pubblicò il suo primo lavoro sull'argomento nel 1961.

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

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^{4}*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' dimostrabile) ma, 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.

## Esempio

Di seguito una semplice implementazione in Python. Si considerino due dispositivi A e B, dove A è il trasmettitore e B il ricevitore.

Supponiamo di voler trasmettere da A a B una data di nascita in formato dd-mm-yyyy dove, ogni cifra della data corrisponde un byte.

Il messaggio da trasmettere quindi sarà lungo 64 bit (escluso i trattini).

