Tesi di Sistemi / Informatica

Codifica di Hamming

In un sistema di comunicazione reale insieme al segnale utile e' presente anche un segnale con andamento del tutto casuale che prende il nome di rumore o Noise.

Il rumore e' un segnale completamente privo d’informazione e influisce molto soprattutto sulla ricezione, con conseguente perdita sulla qualità' dell'informazione

Alcuni esempi di rumore possono essere il ronzio negli alimentatori, il fruscio degli altoparlanti, o più' banalmente, l'inquinamento acustico nell'aula quando il prof. parla attraverso il canale aria.
Si distingue essenzialmente tra :

• Rumore interno, generato dagli apparati elettronici impiegati nella trasmissione; e' sempre presente ed e' molto difficile da eliminare, in quanto dipende dalla materia stessa e dalle cariche elettriche che danno origine alla correnti

• Rumore esterno quale ad esempio, il rumore atmosferico prodotto da onde elettromagnetiche o da scariche naturali come i fulmini e il rumore cosmico, causato dai raggi cosmici o da emissioni di onde elettromagnetiche ad alta frequenza provenienti da varie sorgenti artificiali, come l’accensione di motori elettrici, interferenze tra circuiti, etc.

Ci sono due approcci al trattamento degli errori

• Includere abbastanza informazione aggiuntiva in modo da poter ricostruire il messaggio originario (correzione dell'errore)
• Includere meno informazione aggiuntiva, in modo da accorgersi che c'è stato un errore, senza per questo essere in grado di correggerlo (rilevazione dell'errore).

n = m + r

Tale numero si dice la distanza di Hamming delle due codeword (Hamming, 1956). Se due codeword hanno una distanza di Hamming uguale a d, ci vogliono esattamente d errori su singoli bit per trasformare l'una nell'altra.
Un insieme prefissato di codeword costituisce un codice (code). La distanza di Hamming di un codice è il minimo delle distanze di Hamming fra tutte le possibili coppie di codeword del codice.
Ora, le capacità di rilevare o correggere gli errori dipendono strettamente dalla distanza di Hamming del codice scelto.
In particolare:

• Per rilevare E errori serve un codice con distanza di Hamming (E+1). Infatti, in questo caso qualunque combinazione di E errori non riesce a trasformare un codeword valido in un altro codeword valido, per cui si ha per forza un codeword non valido, che quindi rivela il fatto che ci sono stati degli errori;

•  Per correggere E errori, serve un codice di Hamming con distanza (2E+1). Infatti in questo caso un codeword contenente fino a Eerrori è più vicino a quello originario che a qualunque altro codeword valido.

Come secondo esempio, consideriamo il codice costituito dalle seguenti codeword:
 

ossia sono necessari circa lg2 mbit. Esiste un codice (codice di Hamming) che raggiunge questo limite teorico.

Ora, c'è una semplice tecnica con la quale tale codice può essere impiegato per correggere gruppi contigui di errori (detti burst di errori) di lunghezza massima prefissata.
 

Supponiamo di voler correggere burst di lunghezza k :
 

•  si accumulano k codeword, riga per riga;
•  i codeword si trasmettono per colonne;
•  quando arrivano si riassemblano per righe. Un burst di k errori comporta un singolo errore in ciascun codeword, che quindi può essere completamente ricostruito.

• Condizione necessaria e sufficiente:  affinché un codice sia in grado di rilevare un errore è che la distanza minima tra le configurazioni valide sia 2 (E+1)

• Condizione necessaria e sufficiente:  affinché un codice sia in grado di rilevare un errore e di correggerlo è che la distanza minima tra le configurazioni valide sia 3 (2E+1)

Vogliamo creare un codice di  autocorrezione per la codifica e trasmissione dei caratteri ascii stampabili da, una tastiera computer.

Dato che i caratteri sono in numero di 94 sarà necessaria una codifica di 7 bit per la codifica di tutti i caratteri,
infatti:

quindi applicando la formula:

condizione vera quindi : m = 11

scopriamo quanti sono i bit di codice  ridondante necessari per avere una distanza minima di Hamming pari a 3

quindi avremo m(11) = n(7) + r(4) .
 

Metodo

2. Determino il valore di k

Scrivo la posizione dei vari bit secondo il codice binario,
e  quindi formo i vari sottinsiemi in base al peso dei bit corrispondenti

 

1)          0  0  0  1                 posizione 1  K[1] = {1,3,5,7,9,11}

2)          0  0  1  0

3)          0  0 1 1                 posizione 2   K[2] = {2,3,6,7,10,11}

4)          0  1  0  0

5)          0  1  0  1                 posizione 4  K[3] = {4,5,6,7}

6)          0  1  1  0

7)          0  1 1 1                posizione 8  K[4] ={8,9,10,11}

8)          1  0  0  0

9)          1  0  0  1

10)        1  0  1  0

11)        1  0  1  1

3. calcolo la parità dei bit presenti nella posizione contenuta nei sottoinsiemi

se non trovo la parità’ trasformo il bit di controllo sottinsieme  (posizione  k[n])  in 1

Esempio:

dato il codeword :
 

da un controllo del sottinsieme  K3 {4,5,6,7} non riscontriamo la parità, quindi si dovrà trasformare il bit di controllo sottinsieme k[3] in posizione 4 da 0 a 1
avremo:
 

(In rosso il bit modificato nella posizione 4)
 

A questo punto le codeword sono codificate e pronte alla trasmissione.

Il ricevente in possesso della composizione dei sottinsiemi,  dovrà effettuare a sua volta
Il controllo parità allo stesso modo, per cui se non corrisponde la parità:

Dovrà assegnare ad un vettore V di lunghezza k nelle posizioni kn un bit a 1 ad ogni controllo di sottinsieme in cui la parità non sia riscontrata, così otterrà come risultato un vettore V, contenente la posizione (in codice binario) dove l’errore si è verificato, e quindi facilmente potrà modificare la codeword ricostruendo l’originale.

Esempio:

nel caso che l’errore si sia verificato durante il controllo al sottinsieme k[2]
avremo:

Da come si vede il numero binario contenuto nel vettore V indica la posizione nella codeword dove si è verificato l’errore , in questo caso 2, quindi facilmente potremo eliminarlo con  un opportuna routine di conversione da binario a decimale e relativa correzione.

Un programma in Visual Basic che simula la procedura è disponibile per essere scaricato cliccando qui
 
 
 
 

   scrivi a schumann