Controllo degli errori (CRC)

, Author

Il nostro video

caricare il tuo video
“FAQ: Error Control (CRC)”

Error Control

La codifica binaria è molto conveniente per l’uso in dispositivi elettronici come un computer, in cui le informazioni possono essere codificate attraverso la presenza o l’assenza di un segnale elettrico.

Tuttavia, il segnale elettrico può essere soggetto a disturbi (distorsione, presenza di rumore), soprattutto quando si trasportano dati su una lunga distanza. Così, il controllo della validità dei dati
è necessario per certe applicazioni (professionali, bancarie, industriali, confidenziali, legate alla sicurezza, …).

Ecco perché esistono dei meccanismi per garantire un certo livello di integrità dei dati, cioè per dare al destinatario la certezza che i dati ricevuti siano effettivamente simili a quelli trasmessi. La protezione dagli errori può essere ottenuta in due modi:

  • o rendendo affidabile il mezzo di trasmissione, cioè affidandosi alla protezione fisica. Un collegamento convenzionale ha generalmente un tasso di errore tra 10-5 e 10-7.
  • o implementando meccanismi logici di rilevamento e correzione degli errori.

La maggior parte dei sistemi di controllo degli errori a livello logico sono basati sull’aggiunta di informazioni (note come “ridondanza”) per verificare la validità dei dati. Queste informazioni aggiuntive sono chiamate checksum.

Correzione degli errori

Quindi sono stati sviluppati sistemi di rilevamento degli errori più sofisticati, questi codici sono chiamati :

  • Codici autocorrettivi
  • Codici autocontrollati

Controllo di parità

Il controllo di parità (talvolta chiamato VRC, per Vertical Redundancy Check o Vertical Redundancy Checking) è uno dei sistemi di controllo più semplici.
Consiste nell’aggiungere un bit supplementare (chiamato bit di parità) a un numero di bit di dati chiamato codeword
(di solito 7 bit, per formare un byte con il bit di parità) il cui valore (0 o 1) è tale che il numero totale di bit a 1 sia pari. Per essere più esplicito, consiste nell’aggiungere un 1 se il numero di bit nella codifica è dispari, 0 altrimenti.

Prendiamo il seguente esempio:

In questo esempio, il numero di bit di dati a 1 bit è pari, quindi il bit di parità è impostato su 0. Nell’esempio seguente, tuttavia, i bit di dati sono un numero dispari, quindi il bit di parità è impostato su 1 :

Ora immaginiamo che dopo la trasmissione il bit meno significativo (il bit a destra) del byte precedente subisca delle interferenze:

Quindi il bit di parità non corrisponde più alla parità del byte: viene rilevato un errore.

Tuttavia, se due bit (o un numero pari di bit) dovessero cambiare simultaneamente durante il trasporto dei dati, allora nessun errore sarebbe rilevato…

Siccome il sistema di controllo di parità rileva solo gli errori con un numero dispari di bit, rileva solo il 50% degli errori.
Questo sistema di rilevamento degli errori ha anche il grande svantaggio di non permettere di correggere gli errori rilevati (l’unico modo è di richiedere la ritrasmissione del byte errato..).

Controllo di parità incrociata

Il controllo di parità incrociata (noto anche come controllo di ridondanza longitudinale o LRC) non è un controllo dell’integrità dei dati di un carattere, ma un controllo dell’integrità dei bit di parità di un blocco di caratteri.

Quindi “CIAO” il messaggio da trasmettere, utilizzando il codice ASCII standard. Ecco i dati come saranno trasmessi con i codici di controllo a parità incrociata:

Letter Codice ASCII
(7 bit)
Bit di purezza
(LRC)
H 1001000 0
E 1000101 1
L 1001100 1
L 1001100 1
0 1001111 1
VRC 1000010 0

Controllo ciclico di ridondanza

Controllo ciclico di ridondanza (denominato CRC, o Cyclic Redundancy Check) è un mezzo potente e facile da implementare per il controllo dell’integrità dei dati. È il principale metodo di rilevamento degli errori utilizzato nelle telecomunicazioni.

Principio

Il controllo di ridondanza ciclico consiste nel proteggere blocchi di dati, chiamati frame
(cornici in inglese). Ogni frame è associato a un blocco di dati, chiamato codice di controllo
(a volte CRC per abuso di linguaggio o FCS per Frame Check Sequence nel caso di un codice a 32 bit). Il codice CRC contiene elementi ridondanti rispetto alla cornice, rendendo possibile l’individuazione degli errori, ma anche la loro riparazione.

Cyclic Redundancy Check (CRC)

Il principio del CRC è di trattare sequenze binarie come polinomi binari, cioè polinomi i cui coefficienti corrispondono alla sequenza binaria. Così la sequenza binaria 0110101001 può essere rappresentata
nella seguente forma polinomiale:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
soit
X8 + X7 + X5 + X3 + X0
ou encore
X8 + X7 + X5 + X3 + 1

In questo modo, il bit meno significativo della sequenza (il bit più a destra) rappresenta il grado 0 del polinomio (X0 = 1), il 4° bit da destra rappresenta il grado
3 del polinomio (X3)… Una sequenza di n bit costituisce quindi un polinomio di grado massimo n-1. Tutte le espressioni polinomiali sono successivamente gestite con l’aritmetica modulo 2.

In questo meccanismo di rilevamento degli errori,
un polinomio predefinito (chiamato polinomio generatore e denotato G(X)) è noto sia al mittente che al ricevitore. Il rilevamento degli errori consiste nel trasmettitore che esegue un algoritmo sui bit del frame per generare un CRC, e trasmette questi due elementi al ricevitore. Il ricevitore deve solo eseguire lo stesso calcolo per verificare che il CRC sia valido.

Applicazione pratica

Lasciamo che M sia il messaggio corrispondente ai bit del frame da inviare e M(X) il polinomio associato. Chiamiamo M’ il messaggio trasmesso, cioè il messaggio iniziale al quale sarà stato concatenato il CRC di n bit. Il CRC è tale che M'(X)/G(X)=0. Il codice CRC è dunque uguale al resto della divisione polinomiale di M(X) (a cui abbiamo precedentemente concatenato n bit nulli corrispondenti alla lunghezza del CRC) per G(X).

È ancora più semplice fare un esempio: prendiamo il seguente messaggio a 16 bit M: 1011 0001 0010 1010 (denotato B1 in esadecimale). Prendiamo
G(X) = X3 + 1 (rappresentato in binario come 1001).
Siccome G(X) è di grado 3, si tratta di aggiungere 4 bit nulli a M:

Il CRC è uguale al resto della divisione di M per G:

10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001,.....
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..


----.
1010
1001
----
0011

Per creare M’ è sufficiente concatenare il CRC così ottenuto ai bit del frame da trasmettere:

M' = 1011000100101010 + 0011
M' = 10110001001010100011

Quindi, se il destinatario del messaggio esegue la divisione di M’ per G, otterrà un resto di zero se la trasmissione è stata completata senza errori:

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....
----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

Polinomi generatori

I polinomi generatori più comunemente usati sono:

  • CRC-12 : X12 + X11 + X3 + X2 + X + 1
  • CRC-16 : X16 + X15 + X2 + 1
  • CRC CCITT V41 : X16 + X12 + X5 + 1

(Questo codice è utilizzato in particolare nella procedura HDLC.)

  • CRC-32 (Ethernet) : = X32 + X26 + X23 + X22 + X16 + X12 +

X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1

  • CRC ARPA : X24 + X23+ X17 + X16 + X15 +

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *