Cyclic redundancy check: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m Bot: correzione mesi e modifiche minori |
||
Riga 3:
| autore = Peterson, W. Wκ. and Brown, D. T.
| anno = 1961
| mese =
| titolo = Cyclic Codes for Error Detection
| rivista = Proceedings of the IRE
Riga 15:
== 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=7</math>) produce il polinomio
<math> b(x) = x^7 + x^4 + x^3 + x^1</math>
Riga 31:
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>
Riga 37:
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>
| |||