Il controllo degli errori
La codifica binaria è molto pratica da utilizzare negli apparecchi elettronici 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).
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:
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.
Foto: © Pixabay.
Potrebbe anche interessarti
- Crc informatica
- Bit di parità - Migliori risposte
- Controllo di parità - Migliori risposte
- Eide informatica - Astuzie - Computer
- Polimorfismo informatica - Astuzie - Programmazione Orientata Oggetto
- Bus informatica - Astuzie - Computer
- Colori informatica - Astuzie - Video
- Incapsulamento informatica - Astuzie - Programmazione Orientata Oggetto
Il documento intitolato « Il controllo degli errori » dal sito CCM (it.ccm.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.