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.^[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

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^{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 (è 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).

'''
Estrapola i divisori dal polinomio
'''
def ricavaDivisoriPolinomiali(polinomio):
    polinomioBin = bin(polinomio)
    divisori = []
    for idx,b in enumerate(polinomioBin[2:],start=1):
        if b =='1':
            divisori.append(1<<((len(polinomioBin[2:])-idx)))
    return divisori

'''
Ricava il resto delle divisioni di ogni divisore estrapolato dal polinomio.
Se il resto della divisione con l'ultimo divisore e' 0 allora e' corretto
'''
def isCorrect(messaggioRicevuto, divisori):
    temp = messaggioRicevuto
    for idx,valore in enumerate(divisori):
        temp%=valore
        if temp ==0 and idx< len(divisori)-1:
            temp = -1
            break
    return temp

#codifico un template del messaggio da trasmettere in formato binario(Es.: 01-01-2000)
messaggio = int('0000000000000001000000000000000100000010000000000000000000000000',2)
print ("Valore messaggio: %d" % messaggio)

#trasformo il polinomio scelto nella sua rappresentazione binaria(x^5 + x^2 + 1)
polinomio = int('100101',2)
print ("Valore polinomio: %d" % polinomio)

#effettuo lo shift del messaggio verso sinistra di 5 posizioni perche' il polinomio e' di quinto grado
messaggio = messaggio<<5
print ("Valore messaggio: %d" % messaggio)

#calcolo il crc che risulta essere il resto della divisione tra il messaggio ed il polinomio
#NOTA: L'operatore % esegue la divisione classica, mentre nel CRC viene utilizzata la 
#divisione binaria modulo 2 (tramite XOR)
crc = messaggio % polinomio
print ("Valore CRC: %s" % bin(crc))

#codifico il messaggio da trasmettere in formato binario(Es: 08-12-1988)
messaggioDaTrasmettere = int('0000000000001000000000010000001000000001000010010000100000001000',2)

#accodo il crc alla sequenza di bit da trasmettere
messaggioDaTrasmettere = ((messaggioDaTrasmettere<<5) | crc)
print ("Valore messaggio da trasmettere: %d" % messaggioDaTrasmettere)

#Ricavo i divisori per le divisioni polinomiali
divisori = ricavaDivisoriPolinomiali(polinomio)
print("Divisori: ", divisori)

#Verifico il risultato
risultato = isCorrect(messaggioDaTrasmettere,divisori)
x = True if risultato == 0 else False
print("Risultato: %r" % x)

'''
Output:
Valore messaggio: 281479305232384
Valore polinomio: 37
Valore messaggio: 9007337767436288
Valore CRC: 0b11111
Valore messaggio da trasmettere: 72093053843734815
Divisori:  [32, 4, 1]
Risultato: True
'''

Note

^ 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 (WC · ACNP). - The original paper on CRCs