CRC

di

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

  • si calcola la checksum di M tramite G
  • si trasmette P=M+checksum
  • il destinatario riceve P e ricalcola la checksum tramite G
  • se checksum=0 il messaggio è corretto

Applico i principi del codice CRC ma in base 10…

Siano

  • M=25
  • G=7

allora

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

Ricezione corretta

  1. Ricezione di P’=253
  2. Calcolo di R
    1. P’/G = 253/7 = 36
    2. R’ = 0
  3. Il messaggio P’ è corretto
    • M = P’/10 = 253/10 = 25.

Ricezione scorretta

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

Polinomio generatore

Due polinomi sono diventati standard internazionali

CRC-16 x16+x15+x2+1 11000000000000101
CRC-CCITT x16+x12+x5+1 10001000000100001

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
    1. M/G=…
    2. R=…
  4. P=M << … | R =
  5. Spedizione del messaggio P
  6. Ricezione di P’=…
    1. Calcolo di R’
    2. P’/G=…
    3. Il messaggio P’ è corretto, M=P’ >> r.
  7. Ricezione di P”=
    1. Calcolo di R
    2. P”/G=…
      R”=
    3. Il messaggio P” è scorretto.