Cyclic redundancy check

Da Wikipedia, l'enciclopedia libera.

Il cyclic redundancy check (ovvero controllo a ridondanza ciclica, il cui acronimo CRC è 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 .

Il calcolo del CRC inizia con il messaggio che viene associato a un polinomio di grado pari al numero di bit del messaggio meno uno, grado che indicheremo con .

Per esempio, il messaggio 10011010 () produce il polinomio

Supponendo che il CRC abbia un polinomio di grado , si "trasla" a sinistra il polinomio di posizioni, ottenendo il polinomio di grado ().

Nell'esempio, supponendo un grado si ottiene:

Si esegue ora la divisione ottenendo un quoziente e un resto . 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 meno il resto della divisione .

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

è definibile anche come

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

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

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 e lo divide per il polinomio 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 a destra di un grado g per ottenere il messaggio di partenza.

Esempio[modifica | modifica wikitesto]

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 64bit(escluso i trattini)

 1 '''
 2 Estrapola i divisori dal polinomio
 3 '''
 4 def ricavaDivisoriPolinomiali(polinomio):
 5     polinomioBin = bin(polinomio)
 6     divisori = []
 7     for idx,b in enumerate(polinomioBin[2:],start=1):
 8         if b =='1':
 9             divisori.append(1<<((len(polinomioBin[2:])-idx)))
10     return divisori
11 '''
12 Ricava il resto delle divisioni di ogni divisore estrapolato dal polinomio.
13 Se il resto della divisione con l'ultimo divisore e' 0 allora e' corretto
14 '''
15 def isCorrect(messaggioRicevuto, divisori):
16     temp = messaggioRicevuto
17     for idx,valore in enumerate(divisori):
18         temp%=valore
19         if temp ==0 and idx< len(divisori)-1:
20             temp = -1
21             break
22     return temp
23 
24 #codifico un template del messaggio da trasmettere in formato binario(Es.: 01-01-2000)
25 messaggio = int('0000000000000001000000000000000100000010000000000000000000000000',2)
26 print ("Valore mesaggio: %d" % messaggio)
27 #trasformo il polinomio scelto nella sua rappresentazione binaria(x^5 + x^2 + 1)
28 polinomio = int('100101',2)
29 print ("Valore polinomio: %d" % polinomio)
30 #effettuo lo shift del messaggio verso sinistra di 6 posizioni perche' il polinomio e' di quinto grado
31 messaggio = messaggio<<6
32 print ("Valore mesaggio: %d" % messaggio)
33 #calcolo il crc che risulta essere il risultato della divisione tra il messaggio ed il polinomio
34 crc = messaggio % polinomio
35 print ("Valore CRC: %s" % bin(crc))
36 #codifico il messaggio da trasmettere in formato binario(Es: 08-12-1988)
37 messaggioDaTrasmettere = int('0000000000001000000000010000001000000001000010010000100000001000',2)
38 #accodo il crc alla sequenza di bit da trasmettere
39 messaggioDaTrasmettere = ((messaggioDaTrasmettere<<5) | crc)
40 print ("Valore mesaggio da trasmettere: %d" % messaggioDaTrasmettere)
41 #Ricavo i divisori per le divisioni polinomiali
42 divisori = ricavaDivisoriPolinomiali(polinomio)
43 print("Divisori: ", divisori)
44 #Verifico il risultato
45 risultato = isCorrect(messaggioDaTrasmettere,divisori)
46 x = True if risultato == 0 else False
47 print("Risultato: %r" % x)
48 
49 '''
50 Output:
51 Valore mesaggio: 281479305232384
52 Valore polinomio: 37
53 Valore mesaggio: 18014675534872576
54 Valore CRC: 0b11001
55 Valore mesaggio da trasmettere: 72093053843734809
56 Divisori:  [32, 4, 1]
57 Risultato: True
58 '''

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]