CRC


Cyclic Redundancy Check.
Si tratta di un codice rilevatore d'errore tramite controllo a ridondanza ciclica.

Dato il messaggio M e un polinomio generatore G
Applico i principi del codice CRC ma in base 10...

Siano
M=25
G=7
allora
  1. calcolo checksum
  2. M/G = 25/7 = 3
    R = 4
    checksum = G-R = 7-4 = 3
  3. P = M*10+checksum = 250+3 = 253
  4. spedizione del messaggio P

Ricezione corretta
  1. Ricezione di P'=253
  2. Calcolo di R
  3. P'/G = 253/7 = 36
    R' = 0
  4. Il messaggio P' corretto
  5. M = P'/10 = 253/10 = 25.

Ricezione scorretta
  1. Ricezione di P''=263
  2. Calcolo di R
  3. P''/G = 263/7 = 37
    R'' = 4
  4. Il messaggio P'' scorretto.

Polinomio generatore

Due polinomi sono diventati standard internazionali
CRC-16x16+x15+x2+111000000000000101
CRC-CCITTx16+x12+x5+110001000000100001


Checksum

Dato il messaggio M(x) di m bit e un polinomio generatore G(x) di grado r (r+1 bit)
  1. Il messaggio M(x) viene shiftato a sinistra di r bit, con r=grado(G(x))
    In pratica: P(x)=xr*M(x)
  2. Si calcola R(x), il resto della divisione tra P(x) e G(x)
  3. Si sottrae(somma) al messaggio: P(x)=P(x)+R(x)
Le operazioni di divisione/resto/somma/sottrazione sono soltanto simili a quelle svolte in base 10...

Rilevamento

  1. Ricezione di P'
  2. Si calcola R(x), il resto della divisione tra P'(x) e G(x)
  3. se R(x)=0 il messaggio P'(x) corretto e M(x)=P'(x) >> r.




Esempio

Consideriamo la trasmissione di un numero in base 2
  1. M=...
  2. G=...
  3. Calcolo la checksum
  4. M/G=...
    R=...
  5. P=M << ... | R =
  6. Spedizione del messaggio P
  1. Ricezione di P'=...
  2. Calcolo di R'
  3. P'/G=...
  4. Il messaggio P' corretto, M=P' >> r.
  1. Ricezione di P''=
  2. Calcolo di R
  3. P''/G=...
    R''=
  4. Il messaggio P'' scorretto.
There are no comments on this page.
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki