Liceo Classico Scientifico
“Giosuè Carducci”
Nola (Na)
Presenta:
“Tanti Auguri Tivissimi”
…anzi…No!
“Tanti Auguri Vivissimi”
Trasmettere senza... la paura di sbagliare
INTRODUZIONE
Può capitare nella trasmissione di un
messaggio criptato di incappare in
errori causati da interferenze di segnali
o imperfezioni della fibra ottica,visto
che viene inviato attraverso un canale
di trasmissione. Cause di errori
possono essere però anche il ronzio
degli alimentatori, il fruscio degli
altoparlanti o l’inquinamento acustico.
Quindi occorre una tecnica per correggere eventuali
errori (oltre a codificare e decodificare in tempi
rapidi). La teoria dei codici si occupa esattamente
del problema prospettato, ossia, il problema
matematico della trasmissione di dati attraverso
canali disturbati. Il fondatore della “teoria dei codici
correttori d’errore” è Richard Wesley Hamming
(1915-1996).
Tale teoria rientra in un ambito più ampio che è
quello della teoria dell’Informazione il cui padre è
considerato Claude E. Shannon (1916-2001).
Ci sono due modi per
affrontare il problema:
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).
CODICE DI HAMMING
PER LA CORREZIONE
DEGLI ERRORI
Supponiamo di dover inviare
dei messaggi consistenti in
numeri da 0 a 15 scritti in
base 2. Si tratta, quindi, di
quaterne di cifre 0 e 1. Cioè il
nostro codice ha per alfabeto
l’insieme F2={0,1}.
Indichiamo con F24 l’insieme,
costituito
da
M=24=16
elementi, di tutte le stringhe
di ordine 4 che si possono
ricavare utilizzando il sistema
binario.
Supponiamo di voler trasmettere un
messaggio (a1, a2, a3, a4) corrispondente
a uno dei numeri precedenti. Per
salvaguardarci
da
eventuali
errori
trasmettiamo la 7-pla:
costituita dalle prime quattro cifre,
rispettivamente, uguali ai caratteri del
messaggio da trasmettere e da altre 3
cifre “ridondanti” ottenute sommando
alternativamente tre delle prime quattro
(nel modo indicato nella 7-pla). Le
somme naturalmente vanno calcolate in
F2. Ad esempio, invece di trasmettere
0100 trasmettiamo 0100011.
Assegnate due stringhe di uguale
lunghezza, il numero di bit che in esse
differiscono prende il nome di distanza di
Hamming. Il minimo “d” delle distanze
fra tutte le possibili coppie di stringhe si
definisce distanza di Hamming di un
codice.
In effetti questo allungamento, ottenuto con l’aggiunta delle 3 cifre
(ridondanti) ci permette di scoprire eventuali errori nella trasmissione del
messaggio. Se (x1, x2, x3, x4, x5, x6, x7) è una parola del nostro codice ed è
trasmessa correttamente, ricordando la 7-pla della relazione precedente, si
avrà:
Da cui ricaviamo il sistema:
Questo sistema si dice “sistema delle condizioni di
parità” del codice che stiamo considerando.
In questo codice la distanza di Hamming è: d=3. Ciò
permette di identificare due errori e correggerne uno.
Possiamo verificare l’asserto procedendo
sperimentalmente
Se il sistema è soddisfatto il messaggio è corretto.
Se il messaggio non verifica il sistema e supponiamo di
sapere, o di ritenere assai probabile, che non vi sia più di un
errore di trasmissione, siamo in grado anche di individuare
esattamente l’errore commesso. Infatti, se vi è uno e un solo
errore, si verifica uno solo dei seguenti sette casi possibili:
1) X1 + X3 + X4 + X5 = 0
X1 + X2 + X4 + X6 = 0
X1 + X2 + X3 + X7 = 0
Errata
Errata
Errata
5) X1 + X3 + X4 + X5 = 0 Errata
X1 + X2 + X4 + X6 = 0 Esatta
X1 + X2 + X3 + X7 = 0 Esatta
2) X1 + X3 + X4 + X5 = 0
X1 + X2 + X4 + X6 = 0
X1 + X2 + X3 + X7 = 0
Esatta
Errata
Errata
6) X1 + X3 + X4 + X5 = 0 Esatta
X1 + X2 + X4 + X6 = 0 Errata
X1 + X2 + X3 + X7 = 0 Esatta
3) X1 + X3 + X4 + X5 = 0
X1 + X2 + X4 + X6 = 0
X1 + X2 + X3 + X7 = 0
Errata
Esatta
Errata
7) X1 + X3 + X4 + X5 = 0
X1 + X2 + X4 + X6 = 0
X1 + X2 + X3 + X7 = 0
4) X1 + X3 + X4 + X5 = 0
X1 + X2 + X4 + X6 = 0
X1 + X2 + X3 + X7 = 0
Errata
Errata
Esatta
Esatta
Esatta
Errata
Naturalmente se l’errore è segnalato dal quinto posto in poi, il numero
trasmesso (la cui identificazione è data solo dalle prime 4 cifre) può
comunque essere individuato correttamente in quanto l’errore
commesso riguarda una delle ultime tre cifre (che costituiscono solo il
codice di controllo di errori). In effetti il codice considerato è anche in
grado di autocorreggersi!
In ogni caso, se sappiamo che c’è un solo errore, il sistema considerato
precedentemente, ci consente anche di individuare dove è stato
commesso l’errore e, quindi, di correggerlo. Infatti, trattandosi di
codice binario, se sappiamo dov’è l’errore, per correggerlo basta
cambiare il simbolo che occupa il posto incriminato.
Si potrebbe applicare la stessa procedura a casi in cui i dati da
trasmettere siano in numero superiore a 15, con messaggi costituiti da
più di 4 bit e aumentando opportunamente il numero di equazioni del
“sistema delle condizioni di parità”.
APPLICAZIONI
Un primo esempio concreto dell’importanza della
correzione degli errori nella trasmissione dei dati si
presentò alla fine degli anni 60. Le sonde spaziali
Mariner e Voyager furono spedite nello Spazio per
fotografare Marte e Giove e inviare le loro immagini
sulla Terra. Ogni foto era divisa in quadratini di 0,1
mm2 e, per ognuno di essi, il computer di bordo
inviava un segnale corrispondente alla tonalità di
grigio rilevata in una scala da 0 (bianco) a 63
(nero).
Nel
sistema
binario
ogni
segnale
corrispondeva, quindi, ad una stringa di 6 bit che
rappresentava una delle 64 tonalità di grigio.
In tale situazione cosa succederebbe se vi fossero
degli errori nella trasmissione dei dati a causa di
qualche interferenza?
Senza i codici di correzione di errori, le foto
giungerebbero alterate e darebbero sicuramente
delle
informazioni
errate.
Ciò
potrebbe
compromettere i risultati di importanti scoperte e
vanificare progetti costati miliardi di dollari.
Per avere un esempio pratico dell’utilizzo dei codici correttori d’errore
è stato creato un programma apposito che tramite l’inserimento dei
caratteri da codificare controlla e corregge l’errore presente.
FINE
RINGRAZIAMENTI

L’elenco dei ringraziamenti sarebbe troppo lungo. Ma vogliamo ringraziare, per tutti,
il prof. Catello Tenneriello che con la sua pazienza e competenza ci ha guidati in
questa esaltante esperienza.
Speriamo, per il futuro, di ritrovarci in altre occasioni che, come questa, ci facciano
crescere e migliorare sia sotto l’aspetto umano che culturale.
GRAZIE A TUTTI PER LA CORTESE ATTENZIONE.

Il lavoro è stato curato da:


Valeria Braghieri, Antonino Brunetto, Francesca Caliendo,
Stefano Cangiano, Emanuele D’Aniello, Maddalena Daniele, Domenico De
Lucia, Luigi Fedele, Vincenzo Gambale, Guido Gucci, Marco Guerriero, Sara
Maffettone, Alessandra Muzio, Pasquale Napolitano, Carmen Nappi,
Francesco Pacia, Caterina Paradiso, Manuel Sabatino, Sandro Vecchione.