8 ottobre 2008  6

La correzione degli errori: il codice Hamming

Sicurezza / Storia / Tecnologia 

Insiemi di Hamming Nell’ambito delle telecomunicazioni e più genericamente nella trasmissione dati su mezzo fisico, i meccanismi più banali per verificare la consistenza (o correttezza) dei blocchi di dati inviati sono quelli del controllo di parità e di checksum. Questi strumenti non consentono però la correzione degli errori. Per ovviare al problema è possibile ricorrere ai codici Hamming.

Il cheksum

Generalmente le informazioni trasferite vengono trattate come blocchi di 128 byte: di questi, l’ultimo byte viene utilizzato come valore di checksum per controllare la validità dei 127 precedenti. Il controllo è molto semplice: il byte di checksum deve contenere il resto della divisione intera ottenuta sommando tutti i valori precedenti e dividendone il risultato per 256.

Supponiamo ad esempio che la somma del blocco di 127 byte sia pari a 16.673: il byte numero 128 dovrà contenere il valore 33 che è appunto uguale al resto della divisione intera per 256 (16.673 = 256 * 65 + 33 o  anche 16.673 mod 256 = 33).

Quando viene ricevuto il blocco di dati, viene effettuato un controllo sul byte di checksum. Se questo ha esito negativo, evidentemente uno o più dei byte trasmessi sono errati, ed è pertanto necessario richiedere nuovamente alla fonte trasmissiva l’invio del pacchetto.

Questo meccanismo consente di verificare la presenza di errori, ma non la loro individuazione ed eventuale correzione.

La ridondanza

Un sistema ancora molto valido per ovviare alla problematica evidenziata, impiega l’utilizzo dei codici Hamming, che prendono il nome dal loro inventore, ovvero Richard Wesley Hamming, un matematico americano che lavorò per lungo tempo presso i famosi laboratori Bell Telephone.

I sistemi di controllo degli errori si basano sul principio della “ridondanza”. I linguaggi naturali (come  l’italiano, un pò meno l’inglese, e altri ancora) ad esempio, contengono un alto grado di ridondanza. Se dalla lettura di un testo, o da una conversazione telefonica o diretta, non si riescono ad interpretare alcune lettere, o anche alcune parole, è possibile dedurre e correggere gli errori di trascrizione o “acquisizione”, semplicemente interpretando il contesto della frase.

Un codice Hamming opera in maniera stanzialmente analoga, sfruttando il principio dell’inserimento di alcuni bit ridondanti alla fine della “parola” di X bit di lunghezza complessiva, che costituisce la singola informazione da inviare all’interno di un pacchetto trasmissivo.

Supponiamo che tale parola sia composta da Y bit reali (cioè significativi ai fini dell’interpretazione dell’informazione stessa) e da Z bit ridondanti. La parola avrà una lunghezza complessiva X pari a Y più Z (X = Y + Z). L’errore si potrebbe verificare in uno qualunque degli X bit componenti la parola stessa, ivi inclusi gli Z bit ridondanti.

Il meccanismo dei bit ridondanti può essere accomunato ad un controllo di parità evoluto: una volta che la parola viene ricevuta ed esaminata si potranno verificare X + 1 probabilità di errore (da 0 a X, per cui, X + 1). Quindi, sempre tenendo a mente il meccanismo usato per il controllo di parità, con Z bit ridondanti sarà possibile rappresentare 2Z possibili situazioni. Quindi perchè la parola sia a prova di errore si dovrà verificare la seguente formula:

2Z >= Y + Z + 1

Dalla medesima è possibile dedurre quanti bit ridondanti sono necessari per la parola di lunghezza stabilita. Se, ad esempio Y vale 7, allora Z dovrà essere 4. Se invece, Y è pari a 4, Z sarà uguale a 3. Ancora, se Y è 16, allora per Z saranno sufficienti solo 5 bit.

Dagli esempi formulati si deduce che l’uso dei codici Hamming è maggiormente efficiente per parole lunghe piuttosto che per quelle corte, poiché richiede proporzionalmente un numero minore di bit ridondanti.

Un controllo di parità multiplo

Ciascuno dei bit ridondanti agisce come una verifica di parità pari su una differente combinazione di bit nella parola. Se si verifica un errore di bit durante la trasmissione, vuol dire che uno o più bit di controllo risulteranno errati e la combinazione di questi ultimi indicherà il bit incriminato. Per effettuarne la correzione sarà sufficiente quindi invertirne il valore, dato che lo stato di un bit è solo binario.

In maniera molto grossolana è possibile affermare che i codici Hamming lavorano sostanzialmente per sovrapposizione di insiemi; il numero complessivo di bit da cui è composta la parola (bit reali più bit ridondanti) e suddiviso in insiemi (composti da un numero di bit pari a quello di bit reali) costruiti in maniera tale che nessuna coppia di bit compaia nella stessa combinazione degli insiemi medesimi.

Se durante la trasmissione della parola si danneggia uno qualunque dei bit, inclusi quelli ridondanti, allora uno o più degli insiemi considerati sarà errato al controllo di parità: la sovrapposizione degli insiemi errati consentirà di individuare univocamente l’errore e quindi di correggerlo invertendone lo stato.

Esprimi il tuo giudizio

Commenti (6) -

notoriousxl
notoriousxl
08 ott 2008 alle 19:22  01
Anche io parteciperò al carnevale della Matematica, dal basso delle mie conoscenze... Laughing
(spiegherò come scrivere una dimostrazione di analisi con OpenOffice Math) ;)
Paolo Bee
Paolo Bee
08 ott 2008 alle 21:00  02
Articolo divulgativo eccellente.
Ottimo lavoro! Smile
Cristiano
Cristiano
09 ott 2008 alle 13:33  03
notoriousxl ha scritto:
Anche io parteciperò al carnevale della Matematica, dal basso delle mie conoscenze
Modesto Smile
Al contrario credo che l'argomento che proporrai sarà molto interessante (perlomeno a me interessa molto)

@ Paolo Bee:
Grazie, collega :-D

annarita
annarita
09 ott 2008 alle 21:56  04
Un vero gioiellino! Grazie CristianoSmile
Davide Espertini
Davide Espertini
10 ott 2008 alle 10:08  05
Davvoro ottimo post! Grazie a te oggi ho imparato qualcosa di nuovo.. Sono ancora un bimbo io ( XD 26 anni = bimbo XD vero?!?!? )
Cristiano
Cristiano
10 ott 2008 alle 22:39  06
@ annarita:
Troppo buona :-D

@ Davide Espertini:
No, sei già sufficientemente adulto Wink
Il primo codice Hamming risale al 1950 (se non ricordo male operava su parole a 7 bit di cui 3 di parità o ridondanza): molti addetti del settore non lo conoscono, anche perchè è più diffuso nell'ambito delle telecomunicazioni, quindi sei ampiamente giustificato Smile

Pingbacks and trackbacks (1)+

Aggiungi Commento

biucitecode
  • Commento
  • Anteprima
Loading


| |   |  

Codice QR

Codice QR - cristianofino.net

Ultimi Commenti