SlashCode

Ridondanza: I vantaggi del doppio

Posted on 17. Nov, 2009 by THeK3nger in Generale, Reti

La maggior parte dell’opera non consiste nel vedere se una cosa smetterà di funzionare bensì nel pensare a cosa fare quando quella cosa smetterà sicuramente di funzionare.

Questa cosa è presente anche nell’informatica e nelle telecomunicazioni: ad esempio non possiamo garantire che le trasmissioni attraverso un canale siano perfettamente prive di errori, anzi, gli errori sono sempre dannatamente frequenti se paragonati alla quantità di dati che attraversano la rete e alla precisione che ci aspettiamo in uscita.

Scarichiamo solitamente file di un paio di mega, circa 2 milioni di byte che corrispondono a 16 milioni di bit. Anche solo un errore su 100.000 bit inviati (una percentuale di errore dello 0.001%) si ripercuoterebbe nel file per 160 volte e sappiamo che, specialmente in file eseguibili, basta anche un solo bit fuori posto per mandare all’aria l’intera applicazione.

Il metodo più utilizzato per ovviare al problema è senza dubbio la ridondanza ovvero la ripetizione delle informazioni nella speranza che, anche nel caso in cui un pacchetto di informazioni venga danneggiato da un errore di trasferimento, il ricevente abbia sempre a disposizione una “copia di riserva” da cui recuperare l’informazione.

La ridondanza viene solitamente applicata su più livelli e nella pila protocollare ci sono almeno 2-3 meccanismi di ridondanza più un meccanismo di “rinvio”. Quindi possiamo dire che nel traffico di rete l’informazione utile è meno della metà del totale dei bit in transito.

Al livello più basso il meccanismo di codifica più basso e semplice che possiamo immaginare è quello di duplicare brutalmente l’informazione: se dobbiamo inviare la sequenza di bit 011010 invieremo, per sicurezza, 000111111000111000. In questo modo anche se abbiamo un errore all’interno della tripletta di bit sapremo sempre qual’era il messaggio originale. Infatti se riceviamo la tripletta 010 sappiamo che in realtà la tripletta originale era 000 e non 111 per il semplice fatto che la probabilità di un errore è molto più alta che la probabilità di due errori nella stessa tripletta! Ovviamente non abbiamo la garanzia assoluta ed è per questo che ci sono meccanismi di ridondanza anche ad alto livello.

Ma perché abbiamo messo triplette invece di coppie? Semplicemente perché la tripletta ci permette di eseguire sia la rilevazione che il recupero dell’errore. Supponendo infatti di inviare coppie quali 00 o 11 alla presenza di un errore, mettiamo 01, non possiamo distinguere se ci sia stato un errore nel primo bit (e quindi l’originale era 11) oppure l’errore fosse del secondo bit (e quindi l’originale era 00). In questo caso possiamo solamente rilevare l’errore ma non possiamo recuperarlo.

Questo fatto è indicato dalla distanza di Hamming la quale indica il numero di “errori” necessari per convertire una stringa di bit in un altra. Il primo codice che abbiamo usato ha una distanza fra i suoi elementi (ovvero fra 000 e 111) di 3. Il sistema quindi sceglierà, in caso di errore, la stringa che dista di meno da quella ricevuta. Nel nostro esempio la stringa 010 dista 1 da 000 e dista 2 da 111. Scegliendo quella a distanza minore scegliamo proprio 000.

Notiamo quindi che scegliere un codice che abbia distanza di Hamming dispari fra i propri elementi garantisce sempre il recupero dell’errore perché il sistema ha sempre una parola di codice più vicina di un altra. Una distanza di Hamming pari fra le parole invece presenta sempre, seppure improbabili, delle stringhe ricevute che distano in egual misura da due parole distinte. In questo caso il sistema è solo in grado di rilevare l’errore e non di correggerlo.

Ma la ridondanza non viene solamente utilizzata per rilevare e correggere errori. Anche le prestazioni di un programma possono beneficiarne. Supponiamo ad esempio una classe Triangolo che mantiene al suo interno informazioni sui tre angoli interni dello stesso. Notiamo subito che potremmo operare in due modi: creare tre attributi che mantengono i tre angoli, oppure mantenere solo 2 angoli e ricavare il 3° tramite una funzione. Se scegliamo di inserire il terzo angolo inseriamo una ridondanza. Se abbiamo un triangolo con due angoli di 45°sappiamo automaticamente che il terzo dovrà essere di 90°. Facendo così risparmieremo sì spazio ma renderemo la classe triangolo più onerosa dal punto di vista della CPU.

Questa cosa è sempre vera, anche nel caso della rilevazione dell’errore. Quando scegliamo di utilizzare la ridondanza scegliamo di sacrificare lo spazio per guadagnare tempo. E’ questa la grande coperta dell’informatica: dobbiamo sempre saper scegliere se il sacrificio di spazio dia guadagni in tempo significativi o, viceversa, se risparmiare spazio non faccia perdere troppo tempo.

E’ un concetto sottile ma essenziale per progettare sistemi ad alta efficenza e soprattutto adatti all’ambiente che vogliamo utilizzare.

Tags: featured, hamming, Reti, ridondanza