b'\n_START_ARTICLE_\nCyclic redundancy check\n_START_PARAGRAPH_\nIl cyclic redundancy check (ovvero controllo di ridondanza ciclico, il cui acronimo CRC \xc3\xa8 pi\xc3\xb9 diffuso) \xc3\xa8 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 \xc3\xa8 molto diffuso perch\xc3\xa9 la sua implementazione binaria \xc3\xa8 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\xc3\xb2 il suo primo lavoro sull\'argomento nel 1961._NEWLINE_Utile per l\'individuazione di errori casuali nella trasmissione dati (a causa di interferenze, rumore di linea, distorsione), il CRC non \xc3\xa8 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\xc3\xb9 robusti seppur computazionalmente meno efficienti.\n_START_SECTION_\nImplementazione\n_START_PARAGRAPH_\nIl CRC prevede la generazione di una stringa di bit di controllo che viene normalmente trasmessa assieme ai dati e il calcolo \xc3\xa8 basato sull\'aritmetica modulare. Un codice CRC \xc3\xa8 definito dal suo polinomio generatore: ad esempio il codice CRC-16-CCITT, molto usato in ambito di telecomunicazioni, \xc3\xa8 definito dal polinomio generatore_NEWLINE_._NEWLINE_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 ._NEWLINE_Per esempio, il messaggio 10011010 () produce il polinomio_NEWLINE_Supponendo che il CRC abbia un polinomio  di grado , si "trasla" a sinistra il polinomio  di  posizioni, ottenendo il polinomio  di grado ()._NEWLINE_Nell\'esempio, supponendo un grado  si ottiene:_NEWLINE_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._NEWLINE_Il messaggio inviato lungo il canale \xc3\xa8 formato dall\'unione del messaggio  meno il resto della divisione ._NEWLINE_Visto che  \xc3\xa8 il resto di una divisione che usa come divisore , questo resto ha un grado strettamente inferiore a quello di ; ricordando inoltre che  \xc3\xa8 ottenuto prendendo il messaggio da inviare  e traslandolo di g posizioni cio\xc3\xa8 del grado del polinomio , si ottiene che i polinomi  e , quando vengono sommati, non si sovrappongono nei termini di ugual grado e si pu\xc3\xb2 quindi assumere che il messaggio  viene inviato "inalterato"._NEWLINE_ \xc3\xa8 definibile anche come_NEWLINE_Cio\xc3\xa8 il polinomio \xc3\xa8 uguale al quoziente per il divisore pi\xc3\xb9 il resto. Sostituendo questa descrizione nella formula precedente otteniamo che  diventa:_NEWLINE_Per le leggi dell\'algebra sui campi finiti, sottraendo un polinomio a se stesso, si ottiene un polinomio nullo, pertanto  diviene:_NEWLINE_Si nota che il messaggio \xc3\xa8 quindi divisibile per il polinomio generatore con resto nullo. La rilevazione degli errori usa questa propriet\xc3\xa0, difatti il ricevitore riceve  e lo divide per il polinomio  che \xc3\xa8 definito precedentemente. Se il messaggio \xc3\xa8 stato ricevuto inalterato la divisione non produce resto mentre se si sono verificati errori di trasmissione la divisione produrr\xc3\xa0 un resto. La presenza di errori multipli potrebbe produrre comunque una divisione senza resto in un messaggio errato. La probabilit\xc3\xa0 che questo accada dipende dal polinomio e dal suo grado e statisticamente si dimostra che questo accade raramente._NEWLINE_Nel caso il messaggio dia resto nullo basta traslare  a destra di un grado g per ottenere il messaggio  di partenza.\n_START_SECTION_\nEsempio\n_START_PARAGRAPH_\nDi seguito una semplice implementazione in Python. Si considerino due dispositivi A e B, dove A \xc3\xa8 il trasmettitore e B il ricevitore._NEWLINE_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._NEWLINE__NEWLINE_Il messaggio da trasmettere quindi sar\xc3\xa0 lungo 64 bit (escluso i trattini)._NEWLINE_ 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 divisori11 \'\'\'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\' corretto14 \'\'\'15 def isCorrect(messaggioRicevuto, divisori):16     temp = messaggioRicevuto17     for idx,valore in enumerate(divisori):18         temp%=valore19         if temp ==0 and idx< len(divisori)-1:20             temp = -121             break22     return temp23 24 #codifico un template del messaggio da trasmettere in formato binario(Es.: 01-01-2000)25 messaggio = int(\'0000000000000001000000000000000100000010000000000000000000000000\',2)26 print ("Valore messaggio: %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 grado31 messaggio = messaggio<<632 print ("Valore messaggio: %d" % messaggio)33 #calcolo il crc che risulta essere il resto della divisione tra il messaggio ed il polinomio34 crc = messaggio % polinomio35 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 trasmettere39 messaggioDaTrasmettere = ((messaggioDaTrasmettere<<5) | crc)40 print ("Valore messaggio da trasmettere: %d" % messaggioDaTrasmettere)41 #Ricavo i divisori per le divisioni polinomiali42 divisori = ricavaDivisoriPolinomiali(polinomio)43 print("Divisori: ", divisori)44 #Verifico il risultato45 risultato = isCorrect(messaggioDaTrasmettere,divisori)46 x = True if risultato == 0 else False47 print("Risultato: %r" % x)48 49 \'\'\'50 Output:51 Valore messaggio: 28147930523238452 Valore polinomio: 3753 Valore messaggio: 1801467553487257654 Valore CRC: 0b1100155 Valore messaggio da trasmettere: 7209305384373480956 Divisori:  [32, 4, 1]57 Risultato: True58 \'\'\''