1 of 24

Cyclic Redundancy Check

Sistemi di Misura Distribuiti, AA 2025-2026

Francesco Santoni

2 of 24

Aritmetica modulare

 

L’orologio è l’esempio classico di congruenza modulo 12

3 of 24

Aritmetica modulare

 

L’orologio è l’esempio classico di congruenza modulo 12

4 of 24

Aritmetica modulo 2

 

 

5 of 24

Aritmetica modulo 2

 

6 of 24

Rappresentazione polinomiale dei bit

 

7 of 24

Rappresentazione polinomiale dei bit

 

8 of 24

Divisione tra polinomi (richiami)

 

9 of 24

Divisione tra polinomi modulo 2

  • Se passiamo all’aritmetica modulo 2, allora somme e sottrazioni sono tutti XOR

​

10 of 24

Divisione tra polinomi modulo 2

  • Semplifichiamo ancora la notazione passando ai bit
  • Il resto si ottiene facendo lo XOR tra dividendo e divisore

​

11 of 24

Divisione tra polinomi modulo 2

  • Per il CRC avremo bisogno solamente del resto, quindi semplifichiamo ancora la notazione
  • L’ultimo algoritmo permette dunque di calcolare facilmente il resto della divisione fra due polinomi, calcolando lo XOR tra i resti parziali e il divisore

​

12 of 24

Definizione del CRC

 

13 of 24

Definizione del CRC

 

14 of 24

Definizione del CRC

 

101000110011011000000000

110100111 =

11100001011011000000000

110100111 =

110010111011000000000

110100111 =

110000011000000000

110100111 =

100100000000000

110100111 =

10000111000000

110100111 =

1010100100000

110100111 =

111101010000

110100111 =

1001101000

110100111 =

100100110

110100111=

10000001

15 of 24

Definizione del CRC

 

16 of 24

Definizione del CRC

 

17 of 24

Calcolo del CRC

 

MSB

LSB

DATI

18 of 24

Calcolo del CRC

  • Prima sottrazione. Non appena il primo bit 1 dei dati si allinea su MSB, le porte XOR eseguono la sottrazione

​

​

​

​

  • Seconda fase, sui registri troviamo caricato il risultato dello XOR, e viene subito eseguita la seconda sottrazione

​

​

​

1

1

1

0

0

0

0

1

DATI

101000110011011000000000

110100111 =

11100001011011000000000

110100111 =

110010111011000000000

110100111 =

110000011000000000

110100111 =

100100000000000

110100111 =

10000111000000

110100111 =

1010100100000

110100111 =

111101010000

110100111 =

1001101000

110100111 =

100100110

110100111=

10000001

1

0

1

0

0

1

0

1

DATI

19 of 24

Calcolo del CRC

  • La seconda sottrazione produce uno 0 su MSB. Le porte XOR tornano ad essere ininfluenti, ed i dati scorrono avanti soltanto

​

​

​

​

  • Una volta che i dati sono riallineati in modo che MSB=1, le porte XOR si riattivano ed eseguono la sottrazione

​

​

​

​

  • Si continua in questo modo fino ad ottenere il resto, ovvero il CRC cercato

1

1

0

0

1

1

0

1

DATI

101000110011011000000000

110100111 =

11100001011011000000000

110100111 =

110010111011000000000

110100111 =

110000011000000000

110100111 =

100100000000000

110100111 =

10000111000000

110100111 =

1010100100000

110100111 =

111101010000

110100111 =

1001101000

110100111 =

100100110

110100111=

10000001

0

1

1

0

0

0

1

1

DATI

20 of 24

Calcolo del CRC

 

MSB

LSB

DATI

21 of 24

Calcolo del CRC

 

 

 

 

 

 

 

 

 

DATI

22 of 24

Calcolo del CRC

 

 

 

 

 

 

 

 

 

DATI

23 of 24

Calcolo del CRC

 

 

 

 

 

 

 

 

 

DATI

24 of 24

Calcolo del CRC

 

 

 

 

 

 

 

 

DATI

C7

C6

C5

C4

C3

C2

C1

C0

S(X)

0

0

0

0

0

0

0

0

1

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

1

0

1

0

0

1

1

1

1

0

​

​

​

​

​

​

​

​

​

​

​

​

​

​

1

1

1

0

1

0

0

1

1

0

1

​

​

​

​

​

​

​

​

​

​

​

​

​

1

1

0

1

0

0

1

0

1

0

1

0

​

​

​

​

​

​

​

​

​

​

​

​

0

0

0

0

0

0

1

1

1

0

1

0

0

​

​

​

​

​

​

​

​

​

​

​

0

0

0

0

0

1

1

0

1

0

1

0

0

0

​

​

​

​

​

​

​

​

​

​

0

0

0

0

1

1

0

0

1

0

1

0

0

0

1

​

​

​

​

​

​

​

​

​

1

0

1

1

1

1

1

1

1

0

1

0

0

0

1

1

​

​

​

​

​

​

​

​

0

1

1

1

1

1

1

0

1

0

1

0

0

0

1

1

0

​

​

​

​

​

​

​

1

1

1

1

1

1

0

0

1

0

1

0

0

0

1

1

0

0

​

​

​

​

​

​

0

1

0

1

1

1

1

1

1

0

1

0

0

0

1

1

0

0

1

​

​

​

​

​

0

0

0

1

1

0

0

1

1

0

1

0

0

0

1

1

0

0

1

1

​

​

​

​

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

1

0

0

1

1

0

​

​

​

1

0

0

0

1

1

0

1

1

0

1

0

0

0

1

1

0

0

1

1

0

1

​

​

0

0

0

1

1

0

1

0

1

0

1

0

0

0

1

1

0

0

1

1

0

1

1

​

1

0

0

1

0

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

0

1

1

0

1

0

0

0

0

0

0

1

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​