|
LA
CORREZIONE
DEGLI
ERRORI
NEL
MONDO
DIGITALE
 |
|
|
Avete
mai sentito parlare di
codice
"red Solomon"?
E
dei bit di parita'?
Ad
esempio, nelle trasmissioni
via
modem ...
Quali
sono i mezzi per evitare
che
una trasmissione digitale
(ad
esempio, da satellite) venga interrotta?
|
A tutti coloro che maneggiano dei dischetti per computer sarà capitato di vedere prima o poi un messaggio di errore sullo schermo, del tipo: "bad CRC". Il dischetto ha dei problemi. In effetti gli errori nel trasferimento dei dati digitali si riscontrano spesso sui dischetti, ed è strano constatare che mentre quasi tutti i supporti (hard disc, nastri audio o video) sono diventati economici ed affidabili, i dischetti sono divenuti economici anche loro, ma sono restati del tutto inaffidabili: se conservate un'immagine o un programma su un dischetto non siete mai sicuri di poterlo recuperare dopo un mese o sei mesi... In ogni caso, cosa significano quelle misteriose sigle? CRC sta per "cyclic redundance control", ed è un sistema di controllo degli errori molto diffuso, anche se nel mondo delle immagini in movimento (ad esempio, sui compact disc o nello standard di videoregistrazione digitale DV) si utilizzano sistemi ben più raffinati. Ma per spiegare cosa siano questi sistemi di controllo degli errori forse è bene fare un passo indietro, e partire dai cosiddetti "bit di parità.". |
 |
Nella
figura, la serie di 0 e di 1 rappresenta i dati corrispondenti ad una ipotetica
immagine. Naturalmente di solito ... le immagini hanno un numero di pixel
maggiore, ma il concetto è lo stesso; basta prendere all'interno
dell'immagine (con trecento o tre milioni di pixel) dei gruppetti di pixel
come quello illustrato qui.
Prendiamo dunque questa questa matrice, e proviamo ad aggiungere i "bit di parità". Nella prima riga 1+1 dà una cifra pari, e quindi a destra (fuori dalla tabella) aggiungiamo il numero 0. Per la seconda riga lo stesso. La terza riga dà un risultato dispari, ed aggiungiamo un 1 per renderlo pari. Abbiamo aggiunto un bit di parità, perchè abbiamo reso pari una somma che sarebbe stata dispari. Facciamo lo stesso per le colonne. Se si verifica un errore (vedete che nella terza figura c'è un 1 al posto dello zero che c'era sopra) noi siamo in grado di identificare la cifra sbagliata. Infatti la prima e la seconda riga vanno bene, le cose non quadrano sulla terza riga, dove a destra dovrebbe esserci 0 e invece c'è 1... Ma quale delle tre cifre della terza riga contiene l'errore? basta guardare alle colonne: quella a destra e a sinistra hanno il bit di parità giusto, quella al centro contiene l'errore. Nella figura più in basso, l'errore viene corretto e i bit di parità tornano ad essere giusti... |
--------------- |
| Immaginiamo di dover leggere o scrivere dei numeri come quelli nella
tabellina in alto. Sono numeri importanti, ed abbiamo paura che si verifichino
degli errori in lettura o in scrittura: ci sarebbero dei disturbi, o addirittura
parte delle immagini o del programma (video od audio) potrebbe divenire
illeggibile. Per evitare questa evenienza, si possono aggiungere altri
bit, che sono un po' come dei gendarmi che controllano gli altri. Notate
che nelle righe in cui vi sono due 1 e uno zero si aggiunge uno 0, e nelle
righe in cui vi è un solo 1 viene aggiunto un 1. Questo perchè
la somma binaria delle tre cifre (0+0+1) dà 1. E quindi viene messo
un altro uno come "sentinella". L'uno aggiunto indica che la cifra ottenuta
dalla somma delle altre cifre è un a cifra dispari. Con questo 1
la cifra diviene pari. Viene insomma aggiunto uno 0 per lasciare pari la
somma quando è pari, e un 1 per rendere pari una somma dispari.
Procedendo in questo modo si ottengono tutte cifre pari, e quindi questo
bit aggiunto è detto "bit di parità". Se si verifica un errore
(come quello esemplificato in figura) ecco che il bit di parità
sta lì a dire che quella somma doveva inizialmente essere dispari,
e non pari come è diventata. L'assenza del bit sta ad indicare che
la somma dovrebbe essere pari, e quindi se è dispari vuol dire che
vi è un errore. Come si fa a capire in quale delle tre caselle si
è verificato l'errore? Lo si può fare mettendo un bit disparità
per ciascuna riga, e uno per ciascuna colonna. In questo modo si individua
la riga (con il bit di parità destra) , e poi la casella sulla riga
(con il bit di parità in fondo alla colonna che non quadra). L'aggiunta
di bit comporta uno svantaggio molto forte: aumentano notevolmente la quantità
di dati che occorre trasferire. E quindi il programma occupa uno spazio
su disco o su nastro maggiore. Si sono studiati dei metodi per consentire
la massima sicurezza contro gli errori con il minimo dispendio di bit.
Il sistema già citato (CRC) utilizza la possibilità di esprimere
i dati sotto forma di polinomio. Si crea un "polinomio generatore" costruito
da ciascuna tecnica in modo da preservare il più possibile dagli
errori. Questi polinomi vengono costruiti sfruttando le caratteristiche
del mezzo su ci va effettuata la registrazione (es. nastro magnetico o
disco ottico...).Il programma viene diviso per questi polinomi generatori,
e sul nastro o sul disco vengono registrati dei bit di parità (chiamati
appunto bit CRC). In sede di lettura si effettua di nuovo la divisione,
e se i bit CRC sono uguali, si ha una ragionevole probabilità che
non vi siano errori. Il sistema così come è stato descritto
contribuisce ad assicurarci che non vi siano errori, ma forse è
un po' poco. L'ideale sarebbe disporre di un trattamento che non solo ci
consenta di verificare l'errore, ma di impedire che si verifichi, oppure
che consente la sua correzione. A questo proposito si rivelano utili i
cosiddetti "codici Hamming".
- I bit vengono espressi
con due cifre tra parentesi,
- La differenza è costituita dai bit di parità. Ad
esempio, l'espressione (7,4)
Il codice Hamming dev'essere diviso esattamente per il polinomio generatore.
Se dalla divisione esce un resto, significa che in quei dati si è
verificato un errore.
Vediamo quindi (anche se sommariamente) di cosa si tratta.
Nei comuni compact disc (sistema ECC) i dati vengono raggruppati in
blocchi con 8 bit ciascuno. Una serie di 24 blocchi viene "impacchettata"
assieme ad altri 4 blocchi che costituiscono dei dati di controllo. Quindi,
si hanno dei gruppi di 28 blocchi, di cui 24 sono di dati e 4 di controllo.
Questi gruppi vengono cambiati di posto (interallacciati) . Se si verifica
un errore a raffica che colpisce dei gruppi vicini tra di loro, questo
errore colpisce dei blocchi che alla fine andranno distanziati di nuovo,
e quindi gli errori non saranno più vicini l'uno all'altro, ma saranno
errori casuali, dispersi singolarmente,e come tali correggibili con sistemi
tipo Hammer.
Il trattamento dei
dati dei compact disc
Il codice red-Solomon usato nei compact
|
***  *** |
Immaginate
che
vi siano dei blocchi di dati numerati da 1 a 8, che devono essere registrati. Nella seconda striscia viene cambiato loro posto: il blocco 2 va la posto dell'8, l'8 al posto del 2, il 7 al posto del 4, e così via. Se
si crea un disturbo "a raffica"
|
| vai in cima alla pagina | scrivi a (web@serenoeditore.com) | torna all'indice |