Codice Hamming

Stampa
( 1 Vote ) 
Valutazione attuale:  / 1
ScarsoOttimo 
Categoria: Informatica
Data pubblicazione
Scritto da Magellano Visite: 4699

Codice Hamming

Il codice Hamming è un codice a correzione d'errore, permette cioè di individuare la posizione di un bit alterato nel codice e quindi di correggerlo.  

Un codice è una rappresentazione simbolica dell’informazione che permette la sua trasmissione da un trasmettitore ad un ricevitore attraverso un canale di comunicazione. Ad esempio, le parole del dizionario costituiscono un codice e il canale di informazione può essere di tipo visivo se le parole vengono scritte, o di tipo uditivo se esse vengono pronunciate.
Consideriamo un codice binario costituito da stringhe di 4 bit per ciascuna combinazione. Si hanno perciò 16 possibili simboli codificabili con le 16 combinazioni dei 4 bit, che possono essere rappresentate con le 16 celle di una mappa di Karnaugh. Si sa che nel passare da una cella ad un’altra adiacente nella mappa (considerando la ciclicità delle mappe di Karnaugh), si ha la modifica di un solo bit nella combinazione dei 4 bit di partenza. Si dice allora che la distanza tra codici dei simboli è pari a uno in quanto la differenza minima nei bit è pari a uno. Nel codice non vi è quindi alcuna ‘ridondanza’. Ciò comporta il problema che se si ha una trasmissione di informazione utilizzando tale codice, un eventuale errore in un bit (un solo errore) dovuto ai disturbi introdotti dal canale rende impossibile la corretta interpretazione del messaggio ricevuto. Se invece avessimo un codice con distanza 2, cioè ad esempio si usassero solo 8 combinazioni delle 16 possibili con 4 bit, disponendoli in una mappa di Karnaugh in posizioni alterne come in una scacchiera, l’introduzione di un errore (su un solo bit) nel messaggio farebbe passare da una cella che contiene un codice valido ad una che contiene invece una combinazione di 4 bit non valida. Da ciò possiamo allora dedurre la presenza dell’errore nel codice ma non siamo in grado di sapere qual è il bit corrotto; in altri termini, non sappiamo da quale cella ci si è ‘spostati’ con l’introduzione dell’errore: si hanno ben quattro possibili combinazioni che possono dar luogo a quella ricevuta, tutte quelle corrispondenti alla modifica di uno dei quattro bit.
Si parla in questo caso di ‘codici a rivelazione di errore’. Questi codici sono ridondanti in quanto il bit aggiuntivo non è necesssario per la codifica dell’informazione ma serve per il controllo di parità.
(la nostra lingua ha una forte ridondanza: infatti se cancelliamo alcuni caratteri da un testo o addirittura intere frasi, siamo ancora in grado di decodificare il testo)
Questo è ciò che si fa introducendo il cosiddetto bit di parità, col risultato di raddoppiare il numero di stringhe possibili, di cui però solo la metà sono quelle corrette e appartenenti al codice, cioè al dizionario delle combinazioni necessarie e sufficienti per la codifica dell’informazione.
Si parla di codice a rivelazione di parità: si contano i bit a 1 presenti nella stringa (o, se si preferisce, quelli a 0), e si porta a parità o a disparità tale numero ponendo il bit di parità al valore opportuno. Il bit di parità si può inserire dove si vuole all’interno della stringa ma generalmente si aggiunge in coda. Il ricevitore, controllando la stringa ricevuta e sapendo che la parità è di un tipo ben preciso (ciò fa parte del cosiddetto ‘protocollo di comunicazione’, cioè dell’insieme delle regole stabilite a priori fra trasmettitore e ricevitore per un corretto colloquio), si accorge, contando i bit, se tale stringa è affetta da errore oppure no; se sì, la scarterà e potrà ad esempio richiedere al trasmettitore di ripetere la trasmissione.
Naturalmente questo meccanismo di controllo di parità non permette di scoprire la presenza di un numero dispari di errori.
Per riuscire nell’intento di scoprire anche qual è il codice corretto da cui proviene la stringa difettosa, occorre aumentare a 3 la distanza tra i simboli, in modo che certamente il codice corretto è quello che, tra tutti i codici possibili, è il più vicino alla stringa ricevuta (sempre nell’ipotesi di un solo errore presente). In tal caso si parla di codici a correzione di errore. Un esempio molto interessante è il codice Hamming, in cui vengono aggiunti più bit di parità che permettono di ricavare l’informazione sulla posizione del bit corrotto.
Se ad esempio si parte da un codice a 4 bit, occorre aggiungerne 3 per ottenere un codice a 7 bit, nel quale i tre bit di parità possono dare la posizione del bit modificato, partendo da 000 per l’assenza di errore, a 111 per la posizione di un errore al 7° bit.
(con 4 bit di parità si può arrivare fino a 15 bit di codice (1111), partendo da un massimo di 11 bit di un codice senza correzione di errore)
Il problema sta nel capire come vanno posizionati i bit di parità.
Facciamo una breve pausa citando un simpatico indovinello che ha molto a che fare col nostro discorso:



Un oste ha una cantina con 64 botti. Un giorno una telefonata anonima lo avverte che il vino di una botte è stato avvelenato. Per non dover buttar via tutto il vino deve far fare delle analisi chimiche molto accurate che possono rivelare la presenza del veleno anche in minima traccia; queste costano parecchio ed oltrettutto il laboratorio è molto distante dal luogo della cantina. Per non spendere un patrimonio in analisi chimiche di tutte le botti deve escogitare la migliore strategia per risolvere il suo problema. Come può fare?  


Ragionando da informatico, bisognerebbe dire che il minimo numero di bit necessari per codificare la posizione della botte è pari a 6 (2^6=64, il caso dell’assenza di veleno non è contemplato); ogni risultato delle analisi è una variabile booleana (c’è o non c’è veleno). Non è pensabile di usare una ricerca dicotomica, cioè dividere a metà le botti, controllare se c’è veleno mescolando un po’ di vino di ciascuna in un’unica provetta e poi dividere ripetutamente ancora per due altre cinque volte fino ad avere solo due botti; questo perché il laboratorio è molto distante. L’ideale sarebbe andarci una sola volta. Ma come?
La soluzione sta nel considerare i codici in binario delle botti, partendo da zero; essi hanno sei bit ed il bit meno significativo è pari a 1 per tutte le botti di numero dispari. Perciò si prende del vino una botte sì ed una no e si mette nella provetta che corrisponde al bit meno significativo.
Analogamente, per la seconda provetta si saltano le botti 0 e 1 (codici 000000 e 000001), si prende del vino dalle botti 2 e 3 (000010 e 000011), e così via prendendo due botti sì e due no. Cioè la seconda provetta corrisponde al secondo bit da destra del codice della botte.
Continuando in questo modo si arriva a mettere un po’ di vino delle ultime 32 botti, quelle che hanno il bit più significativo pari a 1, nell’ultima provetta.
Si noti che in ogni caso sono state prese in considerazione 32 botti.
In base ai risultati delle analisi, si contrassegnano con 1 quelle provette che contengono veleno; il codice che ne risulta individua perfettametne l’unica botte col vino avvelenato.


Nel caso dell’indovinello, le provette non fanno parte del set delle botti; nel codice Hamming invece, i bit di parità fanno parte del codice e possono a loro volta essere alterati. La soluzione è perciò più complicata.

Proviamo a codificare le posizioni dei 7 bit:
(000 indica l’assenza di errore)

1.    001
2.    010
3.    011
4.    100
5.    101
6.    110
7.    111

Si può notare che il 1°, il 2° e il 4° bit hanno solo un 1 nel codice; questi saranno i tre bit di parità.
- Il primo bit di parità controllerà la parità su quei bit tra i sette che hanno nel codice di posizione il bit meno significativo pari a 1, quindi controllerà se stesso più altri tre bit.
- Il secondo bit di parità controllerà la parità su quei bit tra i sette che hanno nel codice di posizione il bit centrale pari a 1, quindi controllerà se stesso più altri tre bit.
- Il terzo bit di parità controllerà la parità su quei bit tra i sette che hanno nel codice di posizione il bit più significativo pari a 1, quindi controllerà se stesso più altri tre bit.
(la parità sarà dispari o pari a seconda dei gusti)
Supponiamo di voler trasmettere la stringa 1101. Inseriamo i bit di parità nella stringa:
110x1yz
x,y,z indicano i bit di parità:

x: ooox---
y: oo--oy-
z: o-o-o-z
le o indicano i bit coinvolti nel test di parità

usando la parità di tipo pari otteniamo:
x=0, y=1, z=0
e quindi la combinazione sarà:
1100110
Se il ricevitore riceve la stringa senza errori, facendo il test di parità avrà esito negativo su tutti i tre bit, quindi il codice di errore sarà 000, cioè assenza di errore.
Supponiamo ora che sia presente un errore nel 5° bit: la stringa è cioè 1110110. Facendo i tre test di parità, poichè tale bit fa parte di due test (x,z), si otterrà come codice di errore 101, cioè 5.
Supponiamo invece che sia presente un errore nel 4° bit (che è un bit di parità!): la stringa è cioè 1101110. Facendo i tre test di parità, poichè tale bit fa parte solo di un test, si otterrà come codice di errore 100, cioè 4.
Joomla 1.7 Templates designed by College Jacke