Il controllo degli errori

Esistono dei meccanismi che permettono di garantire un certo livello di integrità dei dati, cioè di fornire al destinatario la sicurezza che i dati ricevuti siano effettivamente simili ai dati emessi. La protezione contro gli errori può effettuarsi in due modi:

Sia rendendo affidabile il supporto di trasmissione, cioè basandosi su una protezione fisica. Un collegamento convenzionale ha generalmente un tasso di errore compreso fra 10^-5 e 10 ^-7.

Sia attuando dei meccanismi logici di rilevamento e di correzione degli errori.

La maggior parte dei sistemi di controllo d'errore a livello software sono basati su una somma di informazioni (si parla di «ridondanza») che permette di verificare la validità dei dati. Questa informazione supplementare si chiama somma di controllo (in inglese checksum).

La correzione degli errori

È così che dei sistemi di rilevamento d'errore più perfezionati sono stati messi a punto, questi codici sono chiamati:

Self-correcting codes (codici autocorrettori);

Self-checking codes (codici autoverificatori).

Il controllo di parità

Il controllo di parità (detto talvolta VRC, per Vertical Redundancy Check o Vertical Redundancy Checking) è uno dei sistemi di controllo più semplici. Consiste nell'aggiungere un bit supplementare (detto bit di parità) ad un certo numero di bit di dati chiamato code word (generalmente 7 bit, per formare un byte con il bit di parità) il cui valore (0 o 1) è uguale al numero totale di bit a 1 cioè pari. Per essere più chiari consiste nell'aggiungere un 1 se il numero di bit della code word è dispari, 0 nel caso contrario. Prendiamo l'esempio seguente:

In questo esempio, il numero di bit di dati a 1 è pari, il bit di parità è quindi posto a 0. Nell'esempio seguente, invece, dato che i bit di dati sono dispari, i bit di parità è a 1:

Immaginiamo ormai che dopo la trasmissione il bit di peso minore (il bit posto a destra) del byte precedente sia vittima di un'interferenza:

Il bit di parità non corrisponde più alla parità del byte: un errore è rilevato. Tuttavia, se due bit (o un numero pari di bit) arriva a modificarsi simultaneamente durante il trasporto dei dati, nessun errore sarà allora rilevato:

Il sistema di controllo di parità rileva solo gli errori in numero dispari, pari quindi solamente al 50% degli errori totali. Questo sistema di rilevamento degli errori possiede anche l'inconveniente maggiore di non correggere gli errori rilevati (il solo mezzo è di esigere la ritrasmissione del byte errato).

Il controllo di parità incrociato

Il controllo di parità incrociato (detto anche controllo di ridondanza longitudinale o Longitudinal Redundancy Check, sigla LRC) consiste non nel controllare l'integrità dei dati di un carattere, ma bensì nel controllare l'integrità dei bit di parità di un blocco di caratteri. Sia «HELLO» il messaggio da trasmettere, utilizzando il codice ASCII standard. Ecco i dati che saranno trasmessi con i codici di controllo di parità incrociato:

Lettera	Codice ASCII (su 7 bit)	bit di parità (LRC)
H	1001000	0
E	1000101	1
L	1001100	1
L	1001100	1
0	1001111	1
VRC	1000010	0

Il controllo di ridondanza ciclica

Il controllo di ridondanza ciclica (siglato CRC, o in inglese Cyclic Redundancy Check) è un mezzo di controllo d'integrità dei dati potente e facile da attuare. Rappresenta il metodo principale di rilevazione di errori usato nelle telecomunicazioni.

Principio

Il controllo di ridondanza ciclica consiste nel proteggere dei blocchi di dati, chiamati frames in inglese. Ad ogni frame è associato un blocco di dati, detto codice di controllo (a volte CRC per abuso di linguaggio o FCS per Frame Check Sequence in caso di un codice a 32 bit). Il codice CRC contiene degli elementi ridondanti rispetto al frame, che permettono di rilevare gli errori, ma anche di ripararli:

controllo di ridondanza ciclica (CRC)

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

0*X⁹ + 1*X⁸ + 1*X⁷ + 0*X⁶ + 1*X⁵ + 0*X⁴ + 1*X³ + 0*X² + 0*X¹ + 1*X⁰sia X⁸ + X⁷ + X⁵ + X³ + X⁰o ancora X⁸ + X⁷ + X⁵ + X³ + 1

In questo modo, il bit di peso minore della sequenza (il bit più a destra) rappresenta il grado 0 del polinomio (X⁰ = 1), il ^quarto bit partendo da destra rappresenta il grado 3 del polinomio (X³). Una sequenza di n bit costituisce quindi un polinomio di grado massimo n-1. Tutte le espressioni polinomiali sono manipolate successivamente con un'aritmetica modulo 2.

Nel meccanismo di rilevamento degli errori, un polinomio predefinito detto polinomio generatore e siglato G(X), è conosciuto dall'emettitore e dal ricettore. Il rilevamento d'errore consiste per l'emettitore nell'effettuare un algoritmo sui bit del frame per generare un CRC e di trasmettere questi due elementi al ricettore. Basterà quindi che il ricettore effettui lo stesso calcolo per verificare che il CRC sia valido.

Applicazione pratica

Sia M 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à concatenato il CRC di n bit. Il CRC sarà M'(X)/G(X)=0. Il codice CRC è così uguale al resto della divisione polinomiale di M(X) (al quale sono stati innanzi tutto concatenati n bits nulli corrispondenti alla lunghezza del CRC) per G(X).

Con un esempio risulta ancora più chiaro: prendiamo il seguente messaggio M di 16 bit:

1011 0001 0010 1010 (sigla B1 in esadecimale). Prendiamo G(X) = X³ + 1 (rappresentato in binario da 1001). Dato che G(X) è di grado 3, si tratta di aggiungere 4 bit nulli a M: 10110001001010100000. 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.. 
     ----.. 
      1100. 
      1001. 
      ----. 
    1010 
    1001 
    ---- 
    0011

Per creare M' basta concatenare il CRC così ottenuto ai bit del frame da trasmettere:

M' = 1011000100101010 + 0011 
M' = 10110001001010100011

Così, se il destinatario del messaggio effettua la divisione di M' con G, otterrà un resto nullo se la trasmissione si è effettuata senza errore:

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ù frequentemente impiegati sono:

CRC-12: X¹² + X¹¹ + X³ + X² + X + 1

CRC-16: X¹⁶ + X¹⁵ + X² + 1

CRC CCITT V41: X¹⁶ + X¹² + X⁵ + 1 (Questo codice è utilizzato soprattutto nella procedura HDLC).

CRC-32 (Ethernet): = X³² + X²⁶ + X²³ + X²² + X¹⁶ + X¹² + X¹¹ + X¹⁰ + X⁸ + X⁷ + X⁵ + X⁴ + X² + X + 1

CRC ARPA: X²⁴ + X²³+ X¹⁷ + X¹⁶ + X¹⁵ + X¹³ + X¹¹ + X¹⁰ + X⁹ + X⁸ + X⁵ + X³ + 1.