Sequenza CRC

Come detto il CRC Field `e composto da 16 bit, i primi 15 costituiscono la sequenza CRC, l’ultimo `e un bit recessivo chiamato CRC Delimiter.

Il Cyclic Redundancy Code o codice polinomiale (CRC) `e una tecnica di codifica dei bit che consente di ottenere un elevato grado di protezione del messaggio spedito (`e in grado di rilevare un’elevata percentuale di errori) usando una ridondanza non troppo elevata, dove per ridondanza si indica il numero di bit di controllo (Check-bit) da aggiungere al messaggio originale (nel caso del CAN i bit sono 15) per ottenere questa protezione. Il CRC `e un codice di rilevamento degli errori e non di correzione a differenza di altri algoritmi come il codice di Hamming.

3.1.2.1 Concetti base

In apparenza si tratta di un meccanismo abbastanza complesso ma si basa su meccanismi algebrici (Teoria Algebrica dei Campi) piuttosto semplici da implementare via hardware e che di seguito si riepilogano:

• addizioni e sottrazioni sono eseguite modulo 2 cio`e sensa riporti per l’addizione e prestiti per la sottrazione. Somme e sottrazioni tra se- quenze di bit si eseguono facendo uno XOR;

• la divisione viene effettuata come in binario ma con sottrazioni modulo

2 (XOR).

L’algoritmo considera i bit in arrivo dalla rete come i coefficienti di un polinomio di grado (K − 1) fatto in questo modo:

M(x) = m(K − 1)x(K−1)+ m(K − 2)x(K−2)+ · · · + m(2)x2+ m(1)x + m(0)

dove:

K : `e il numero di bit che compongono la parte del messaggio sottoposto a codifica CRC;

m(i) : `e il coefficiente di grado i e vale 0 o 1, corrisponde al valore del bit in posizione i-ma della sequenza in arrivo.

Ad esempio una sequenza di bit:

101101 corrisponde al polinomio:

Capitolo 3. Informazioni preliminari 66

Viene poi definito un secondo polinomio detto generatore G(x) di grado (R < K) e struttura prefissata, noto sia all’interfaccia trasmittente che al ricevitore; ad esempio potrebbe essere fatto in questo modo:

G(x) = x4+ x + 1

corrispondente alla sequenza binaria: 10011

La tecnica CRC si preoccupa di calcolare una sequenza di R bit di controllo da accodare al messaggio originale ottenendo cos`ı una sequenza di K + R bit detta codeword in modo tale che il polino- mio corrispondete T (x) sia divisibile per il polinomio generatore

G(x). Se uno o pi`u errori di trasmissione modificano la parola

di codice il polinomio corrispondente non sar`a pi`u divisibile, con elevata probabilit`a, per il polinomio generatore G(x) e l’errore verr`a rilevato.

3.1.2.2 Calcolo del CRC

Di seguito viene descritta la procedura di calcolo.

1. Il polinomio “originario” M(x) viene moltiplicato per xR_{, l’operazio-} ne equivale ad accodare alla sequenza del messaggio da codificare un numero R di bit a 0.

1011010000

2. Si divide xR_{M(x) per G(x) come mostrato in figura 3.11.} 3. Il resto della precedente divisione viene sottratto a xR_M(x):

1011010000 XOR 0000001110 = 1011011110

ottenendo il polinomio T (x) i cui coefficienti costituiscono la sequenza di bit da trasmettere:

1011011110 dove i bit evidenziati sono la sequenza CRC.

Il ricevitore si costruisce il polinomio T0_{(x) con i K + R bit che riceve, lo} divide per il generatore G(x) ed accetta il messaggio solo se il resto della divisione `e zero.

Il calcolo della sequenza CRC pu`o essere implementato via soft- ware e/o hardware mediante operazioni/registri di shift e attra- verso operazioni/porte XOR.

1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 Sequenza CRC Sequenza aggiuntiva xR_{T(x) G(x)}

Figura 3.11: Calcolo del CRC: divisione binaria modulo 2 tra xRT (x) e G(x).

3.1.2.3 Errori rilevati da CRC

Il polinomio che costruisce il ricevitore possiamo scriverlo anche in questo modo:

T0(x) = T (x) + E(x)

dove E(x) `e il polinomio di errore: ogni coefficiente non nullo di E(x) cor- risponde ad un bit invertito per errore nella trasmissione di T (x). Se la di- visione che esegue il ricevitore restituisce resto nullo ci sono due alternative possibili:

E(x) = 0 : non ci sono errori;

E(x) `e multiplo di G(x): la trasmissione ha generato degli errori ma questi non vengono rilevati dal nostro sistema di codifica.

Ne consegue che la scelta del polinomio generatore `e critica, le sue caratte- ristiche determinano la capacit`a dell’algoritmo di rilevare certe tipologie di errori.

Il generatore deve essere scelto in modo tale da non dividere esattamente il polinomio di errore. Si pu`o dimostrare che un

Capitolo 3. Informazioni preliminari 68 Bus Idle S O F Arbitration Field Control

Field Data Field

CRC sequ.

ACK

Field EOF Int.

Bus Idle CRC Area

DATA/REMOTE frame structure

C R C d e l.

Coefficienti del polinomio

M(x) = SOFx(k-1)_+ID28x(k-2)_+…+D2x2_+D1x+D0

Figura 3.12: “CRC Area” e coefficienti del polinomio di calcolo M (x).

polinomio G(x) che ha due o pi`u termini rileva tutti gli errori

singoli, se ha grado R rileva tutti i burst13 _{composti al pi`u da}

R errori ecc. . . . Alcuni polinomi generatori sono diventati degli

standard internazionali come a titolo esemplificativo il “CRC-16” sotto riportato:

G(x) = x16+ x15+ x2+ 1

3.1.2.4 La sequenza CRC del protocollo CAN

Il polinomio M(x) descritto in precedenza viene costruito dal trasmettito- re utilizzando come coefficienti i bit dell’area evidenziata in figura 3.12 ed indicata con il termine “CRC Area”; esemplificando possiamo dire che:

m(K − 1) = SOF , m(K − 2) = ID28, m(K − 2) = ID27 . . .

Come generatore il CAN utilizza il seguente polinomio:

G(x) = x15_{+ x}14_{+ x}10_{+ x}8_{+ x}7_{+ x}4_{+ x}3_{+ 1}

che consente di rilevare:

• la presenza al massimo di 5 errori singoli casualmente distribuiti14 _nella “CRC Area”;

• errori di tipo burst con lunghezza massima pari a 15 bit.

13_{L’errore di tipo burst `e una sequenza di bit che inizia e termina con un errore anche se}

i bit tra un errore e l’altro sono esatti. La dimensione che viene assegnata e caratterizza il burst corrisponde alla lunghezza della sequenza.

Nel listato 3.1 `e descritto in un linguaggio pseudopascal la procedura di calcolo della sequenza CRC. Allo scopo di implementare questa funzionalit`a viene impiegato uno shift register a 15 bit CRC RG(14:0) e una variabile NXTBIT utilizzata per contenere il valore del bit successivo nello stream da codificare.

1 CRC_RG = 0 \\ init shift reg .

2 REPEAT 3 CRCNXT = NXTBIT EXOR CRC_RG (14) 4 CRC_RG (14:1) = CRC_RG (13:0) \\ shift left by ... 5 CRC_RG (0) = 0 \\... one position 6 IF CRCNXT THEN 7 CRC_RG (14:0) = CRC_RG (14:0) EXOR (4599 hex ) 8 ENDIF

9 UNTIL ( CRC SEQUENCE starts or ERROR condition )

Listato 3.1: Algoritmo di calcolo della sequenza CRC implementato nel protocollo CAN.

Il nodo ricevente dopo aver eseguito il destuffing del frame calcola anch’es- so la sequenza CRC, la confronta con quella trasmessa ed in presenza di una qualche difformit`a rileva una condizione di errore di tipo CRC Error ; successivamente al ricevimento dell’ACK Delimiter invia un ERROR Flag.