Il controllo degli errori

Aprile 2015

Il controllo degli errori


La codifica binaria è molto pratica per un'utilizzazione nelle apparecchiature elettroniche come i computer, nei quali l'informazione può essere codificata grazie alla presenza o meno di un segnale elettrico.

Il segnale può tuttavia subire dei disturbi (distorsione, presenza di rumore), soprattutto al momento del trasporto dei dati su un lungo tragitto. Così, è necessario il controllo della validità dei dati per alcune applicazioni (professionali, bancarie, industriali, confidenziali, relative alla sicurezza, ...).

Ecco perché 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 maggiorparte 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


E' 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 :
LetteraCodice ASCII
(su 7 bit)
bit di parità
(LRC)
H10010000
E10001011
L10011001
L10011001
010011111
VRC10000100

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*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0sia X8 + X7 + X5 + X3 + X0o ancora X8 + X7 + X5 + X3 + 1


In questo modo, il bit di peso minore della sequenza (il bit più a destra) rappresenta il grado 0 del polinomio (X0 = 1), il quarto bit partendo 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 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) = X3 + 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 : X12 + X11 + X3 + X2 + X + 1
  • CRC-16 : X16 + X15 + X2 + 1
  • CRC CCITT V41 : X16 + X12 + X5 + 1

(Questo codice è utilizzato soprattutto 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 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1
Per poter consultare questo documento offline, ne potete scaricare gratuitamente una versione in formato PDF:
Il-controllo-degli-errori.pdf

Vedi anche


Error checking
Error checking
Verificación de errores
Verificación de errores
Die Fehlerkontrolle
Die Fehlerkontrolle
Contrôle d'erreur (CRC)
Contrôle d'erreur (CRC)
O controlo de erros
O controlo de erros
Il documento intitolato « Il controllo degli errori » da Kioskea (it.kioskea.net) è reso disponibile sotto i termini della licenza Creative Commons. È possibile copiare, modificare delle copie di questa pagina, nelle condizioni previste dalla licenza, finché questa nota appaia chiaramente.