Shannon e La Teoria Dell'Informazione: Entropia, Ridondanza, Codifiche

Per Teoria dell'Informazione, ci si può riferire alla trasmissione di segnali: basso costo, più alta velocità consentita dal canale, pieno controllo degli errori anche in presenza di disturbi non eliminabili.
A questa teoria è legato il nome di Claude Shannon. Come preambolo, si parla d'informazione relativa di un evento, quando tutto ciò contribuisce ad aumentare le conoscenze riguardanti l’evento stesso. Se devo individuare un cane bianco di un amico è molto difficile, se invece il mio amico mi dice che si tratta di un pastore maremmano con una macchia nera su pelo bianco, la ricerca sarà molto più semplice in quanto le informazioni più accurate. Comunque prima d'introdurre la teoria dell'Informazione di Shannon e i concetti di Entropia, partiamo dall'inizio: dal telegrafo e da altri mezzi usati in passato come trasmettitori d'informazioni.


LE INTUIZIONI DI MORSE E IL TELEGRAFO
Pare che Samuel Morse abbia inventato il telegrafo ma l'intuizione in sè non sta in questo strumento che egli aveva visto funzionare nelle mani di altri: le idee più innovative vanno riconosciute nel modo in cui egli organizzò il suo codice, in funzione di determinate caratteristiche dei messaggi da trasmettere e del canale a disposizione. Sicuramente anticipatrici infatti sono alcune scelte da lui operate. Suo obiettivo era trasmettere dei testi scritti quindi comincia con lo studio dell’alfabeto, a cui impone un ordine diverso dal tradizionale A-Z: ordina le lettere secondo il criterio della frequenza con cui esse compaiono nei testi inglesi. Non si serve di calcoli statistici per definire la probabilità di ciascuna lettera come farà Shannon, ma l’intuizione è già presente. Sceglie i segnali da trasmettere via cavo, seguendo il criterio della sicurezza da errori: due soli segnali (chiusura del circuito per un tempo breve o per un tempo lungo), tradotti all’altro capo della linea da un elettromagnete in punti (tratti brevi) e linee (tratti lunghi), segni chiaramente riconoscibili dall’operatore. Alla lettera ‘e’ associa un punto, alla ‘a’ un punto e una linea; alla ‘i’ due punti. Dopo aver notato che i cavi sotterranei erano disturbati da correnti estranee, capaci di introdurre errori non controllabili, adotta come canale le linee aeree. Anche nel telegrafo di Morse, dunque, le vere novità non sono legate alla tecnologia utilizzata, ma al modo con cui viene trattata l’informazione: il sistema opera grazie a un codice efficiente, col quale viene sfruttata la maggiore o minore frequenza dei ‘messaggi’ da trasmettere (le lettere dell’alfabeto), utilizzando dei segnali scelti in funzione delle caratteristiche del canale per aver un miglior controllo dei possibili errori.


SECONDA GUERRA MONDIALE E RADAR
Verso la fine del secolo XIX si adotta un nuovo canale di comunicazione, le onde elettromagnetiche. Queste si propagano ovunque, al di là di ogni ostacolo e senza bisogno di particolari supporti.
Per la loro immediata utilizzazione (Marconi) e poi per molti anni ancora si ricorre al codice Morse. Mano a mano però che si conoscono meglio i fenomeni elettrici ed elettromagnetici, vari tecnici e scienziati mettono a punto codici di trasmissione più efficienti. Una accelerazione a questo tipo di studi venne impressa dalla seconda guerra mondiale: i segnali da trasmettere e gli errori dovuti ai vari disturbi sono le comunicazioni al fronte e i segnali radar, bisognava fornire alle batterie contraeree dei sistemi di puntamento in grado di anticipare la posizione dell’aereo nemico per poterlo abbattere.
In questo tipo di ricerche maturarono le loro idee più innovative Norberthref Wiener, padre della cibernetica e Claude Shannon. I primi lavori di Shannon nel Laboratorio della Bell riguardarono l’analisi matematica delle forme di de-criptazione dei messaggi (lo scopo era fornire alle forze alleate la chiave per decodificare i messaggi della marina e dell’esercito tedesco), e furono formalizzati nella monografia Communication Theory Of Secrecy Sistems. Nel 1949 venne pubblicato "The Mathematical Theory Of Communication, riguardante il problema della trasmissione accurata di un segnale tra emittente e ricevente.


LA TEORIA DELL'INFORMAZIONE
Shannon definisce il problema di cui cerca la soluzione: riprodurre in un determinato punto in modo esatto o con una buona approssimazione, un dato messaggio. È un problema di tipo squisitamente tecnico quello che lui si pone e quando usa la parola comunicazione lo fa come sinonimo di trasmissione di segnali. Prima degli anni 40 questo termine non aveva il significato di oggi, quanto piuttosto era connesso a movimento e trasporti. Sono proprio gli studi di Shannon (e di Norbert Wiener) che mettono al centro dell’attenzione del mondo scientifico questo tema. Shannon propone uno schema, un modello nel quale sono indicati gli elementi fondamentali che entrano in gioco in ogni trasmissione di segnali e viene indicata la relazione che li lega. L’idea di ‘processo’ è collegata con l’idea di comunicazione. Ad esempio se sto parlando al telefono con una persona distante, io sto parlando, l'altro ascolta: quindi io sono la sorgente dell'informazione.
Ma non è la mia voce che viaggia lungo i cavi del telefono: prima viene trasformata da un apparato chiamato trasmettitore in segnali elettrici. Sono questi impulsi elettrici che vengono inviati attraverso la rete telefonica (il canale di comunicazione) fino all'altro capo della linea.
Qui vengono ricevuti dal ricevitore, che si incarica di ripristinare il suono della mia voce, in modo che essa raggiunga il destinatario. La conversazione è invece ostacolata dal rumore. Il trasmettitore è rappresentato come composto di due elementi: il codificatore di sorgente e il codificatore di canale; di conseguenza il ricevitore è costituito dal decodificatore di canale e dal decodificatore di sorgente.
Il codificatore di sorgente serve a eliminare le informazioni ridondanti dal messaggio, riducendone quindi la dimensione; il codificatore di canale trasforma il messaggio in segnali compatibili con il canale. Il ruolo del codificatore di sorgente è quindi quello di comprimere il messaggio.
Un esempio semplicissimo di compressione: 27 è una notazione compatta per evitare di scrivere 3 per 3 per 3. E' chiaro che il codificatore di sorgente deve agire secondo un algoritmo reversibile, in modo che il decodificatore di sorgente sia in grado di ripristinare velocemente e in maniera affidabile tutte le informazioni eliminate. In ogni trasmissione vi sono dei disturbi che alterano i segnali: il messaggio ricevuto è diverso da quello trasmesso. Le conseguenze su un messaggio numerico sono deleterie poiché il cambio di una solo cifra altera il significato (pensate al risultato che si ottiene cambiando una cifra a caso del saldo del vostro conto, specie se a cambiare è il segno, da positivo a negativo).
Per rimediare agli inevitabili errori il codificatore di canale può aggiungere delle informazioni di controllo ai segnali che trasmette. Il decodificatore utilizza queste cifre per verificare la presenza di errori ed è anche in grado di correggerne alcuni. Le componenti individuate sono quindi: la fonte (insieme dei messaggi possibili), il trasmettitore (che codifica), il canale, il ricevitore (che decodifica), il destinatario.

Quali sono i problemi quindi? Il noise (rumore) ed ovviamente la distorsione che può cambiare (lungo il tragitto) il segnale trasmesso. Per Shannon la fonte è un insieme di messaggi possibili (di questi messaggi trasmessi non viene preso in considerazione il significato. Questa affermazione sembra svuotare di importanza tutto il discorso: a che serve un sistema di trasmissione, se non ci si interessa al significato dei messaggi trasmessi?). Nel caso del telegrafo di Chappe tutti gli operatori avevano la tabella delle corrispondenze; tutti gli operatori del telegrafo elettrico conoscevano l’equivalenza tra le sequenze di punti e linee e le lettere dell’alfabeto; anche due persone che parlano tra di loro sanno già che determinati suoni hanno determinati significati. Ciò che non si sa e dunque verrà fornito dal sistema...è quale stringa di punti e linee, quale parola verrà pronunciata. Presa questa decisione, tutte le fonti con lo stesso numero di messaggi possibili, per quanto riguarda la ‘comunicazione’, sono uguali: decisivo è riuscire a trasmettere al destinatario l’indicazione giusta, perché egli sa già se stiamo parlando. L’elemento che differenzia le fonti e rende più incerto il destinatario è la loro diversa prevedibilità: il livello di incertezza è più alto, quanto più numerosi sono i messaggi che possono provenire da quella fonte. Per questo, l'informazione misura la complessità di una fonte o l'imprevedibilità di un messaggio (va notato che le due espressioni si equivalgono: un messaggio è più prevedibile quando la fonte fornisce pochi messaggi; è invece tanto più imprevedibile quanto più numerosi ed egualmente probabili sono i messaggi della fonte). Shannon adotta il codice binario, come sistema ottimale per indicare quale messaggio viene inviato da una fonte e per misurare il suo livello di imprevedibilità. Ad esempio se una fonte ha 32 messaggi possibili, è necessario e sufficiente un numero binario di cinque cifre, per indicare quale si è verificato (con 11111 indico il 32°, con 10001 il 17° e così via). Se i messaggi sono 16, bastano quattro cifre binarie. Se 8, ne bastano tre. Se 4, due (bit). Se la fonte ha solo due messaggi possibili (di meno non si può, perché non ci sarebbe incertezza e dunque non c’è modo di comunicare nulla) basta una sola cifra binaria: 1 o 0.


DIFFERENZA CON SISTEMA DECIMALE
Il sistema decimale per fare la stessa cosa (individuare un elemento in un gruppo di trentadue) usa al massimo due cifre: 3, 15, 21... 32, mentre quello binario ne utilizza sempre cinque: 00011, 10001, 10111. Infatti le due cifre decimali sono scelte tra dieci, per trasmettere le quali occorrono altrettanti segnali fisici diversi. In quello binario le cifre sono soltanto due, e dunque due soltanto sono i segnali.
Ovviamente è molto meno soggetta ad errori una sequenza fatta solo da due variabili tipo 0 o 1 (tutto o niente), che non una sequenza a dieci variabili. Se ad esempio il canale di trasmissione viene disturbato (per qualche istante la tensione nel circuito subisce un innalzamento), il rumore modifica in modo analogo tutti i dati trasmessi; mentre nel caso delle cifre binarie la loro totale diversità può rimanere visibile oltre il disturbo (al posto di 0 e 1, si potrebbero trovare altre cifre, ad esempio 2 e 3: il sistema è in grado di segnalare l’errore e ne dà anche la misura +2), per le cifre decimali questo stesso disturbo è distruttivo, dal momento che cambia una cifra in un’altra (il 5 diventa 7, il 3 diventa 5, valori perfettamente accettati dal sistema quindi l'errore non è riconoscibile).


L'ENTROPIA E LA RIDONDANZA
Impostando così il problema, si è costruito un modello matematico del processo di trasmissione e l’informazione è diventata una quantità misurabile. La sua misurazione si è rivelata importante a vari livelli: per valutare la complessità della fonte (l’entropia), per sapere la quantità di informazione caratteristica di un messaggio (il suo tasso di imprevedibilità) e anche per conoscere la capacità di un canale. Shannon approfondì in modo particolare quest’ultimo problema, riuscendo a definire dei criteri (delle formule matematiche) grazie ai quali è possibile determinare in anticipo quali messaggi si possono trasmettere in un determinato canale, anche se disturbato. Secondo Shannon la quantità di informazione trasmessa da un simbolo dipende dalla probabilità di occorrenza del simbolo.
Maggiore è questa probabilità, minore è la quantità di informazione. Un simbolo la cui probabilità di occorrenza è del 100% ha una quantità di informazione uguale a zero. Un simbolo con bassa probabilità ha invece una grande quantità di informazione. La quantità di informazione dei singoli caratteri è data da:

Q(x1) = -log2 0,5 = 1 bit
Q(x2) = -log2 0,25 = 2 bit
Q(x3) = -log2 0,25 = 2 bit

La quantità di informazione contenuta nel messaggio sarà quindi pari alla somma delle quantità di informazione dovute ai singoli caratteri:

  3
  ∑ Q(xi) = Q(x1) + Q(x2) + Q(x3) =5 bit
i = 1

Ci si riferisce ad entropia della sorgente (H) quando si parla dell'informazione media emessa dalla sorgente in questione.
                                                                                 
H = ∑ p(xi) * Q(xi) = -∑ p(xi) * log2 p(xi)
i = 1                  i = 1

Questa formula significa semplicemente che l’entropia, cioè la quantità media di informazione emessa dalla sorgente (H), è pari alla sommatoria dei prodotti tra la probabilità che ha il simbolo (xi) di essere trasmesso e la quantità di informazione dovuta al simbolo stesso. In generale una codifica è tanto più efficiente quanto più corte sono le sue parole, in quanto richiedono minor tempo di trasmissione e una minor mole di dati da spedire. La codifica esprimerà il numero di bit da cui è composta una parola.
La lunghezza media delle parole, indicata matematicamente con il simbolo L è quindi pari alla sommatoria della probabilità del simbolo xi di essere trasmesso moltiplicato per la lunghezza della parola li.

   n                                          
L =∑ p(xi) * li                                                                            
  i = 1

Quindi per stabilire l’efficienza di una codifica ci basiamo sul primo teorema di Shannon, che afferma che per ogni sorgente in grado di trasmettere n simboli esiste almeno una codifica tale per cui

H ≤ L

Quindi l’entropia della sorgente sarà sempre minore della lunghezza del codice necessario a rappresentare tutti i simboli di una sorgente. Importante, infine, è anche il concetto di ridondanza.
Cioè il surplus di segnali adottato nella trasmissione per garantire il messaggio contro eventuali disturbi. Ad esempio ridondante è la ripetizione che spesso facciamo nel dettare la nostra mail: in questi casi il messaggio (indirizzo mail) rimane esattamente lo stesso, ciò che aumenta è il numero di segnali utilizzati affinché il ricevente trascriva l'indirizzo giusto. Questa teoria messa a punto per risolvere dei problema tecnici, si è rivelata capace di interpretare tanti altri sistemi dove vitale e continuo è lo scambio di messaggi. Si disponeva così di un nuovo punto vista e insieme di una vera e propria piattaforma teorica, che ha fatto incontrare scienze molto diverse: la linguistica, la psicologia, la semiotica, la logica matematica, l’informatica, l’intelligenza artificiale, la microbiologia, la medicina.


SISTEMI CHIUSI ED APERTI
Shannon, che lavora con le macchine, osserva che il modo migliore per garantire efficienza e sicurezza alla trasmissione dei messaggi è considerare chiuso il sistema: le macchine infatti sono costruite per dire e fare soltanto ciò per cui sono state programmate. Nel caso dell’uomo tutto questo vale soltanto fino a quando i due interlocutori accettano di rispettare determinati criteri (per ragioni di efficienza, infatti, l’uomo può anche accettare di comunicare come fanno le macchine). Ma non può farlo a lungo, senza rinunciare alla sua identità di sistema aperto essenzialmente interessato a ciò che è nuovo. Quando la comunicazione è umana, è sempre a rischio, perché va al di là del semplice rispetto del codice utilizzato.


TEORIE
1) Teoria delle sorgenti
Qualunque processo che generi messaggi successivi può essere considerato una sorgente di informazione.

2) Teoria codifica di codici
Può essere suddivisa in codifica dei codici sorgenti e codifica di canale.
La teoria dell'informazione quantifica il numero dei bit necessari a descrivere i dati, tale quantità è l'entropia informativa della sorgente.
Riguardo la compressione dati (codifica sorgente), può essere:
-compressione senza perdita, quando i dati devono essere ricostruiti in modo esatto.
-compressione con perdita allocando i bit necessari a ricostruire i dati.
Codici di correzione errori (codifica di canale): mentre la compressione dati ha lo scopo di rimuovere la maggior ridondanza possibile, un codice di correzione per gli errori aggiunge il giusto tipo di ridondanza necessario a trasmettere i dati in modo efficiente ed affidabile su un canale rumoroso (noise). La suddivisione della teoria dei codici tra compressione e trasmissione è giustificata dai teoremi di trasmissione di informazione, che giustificano l'uso dei bit come misura universale dell'informazione in molti contesti.


CAMPIONAMENTO
Gli studi di Shannon in materia di campionamento hanno aperto la strada al tema della conversione analogico-digitale. Come associare a una grandezza continua un numero, da convertire poi in sequenza di impulsi? Prendendo, dal segnale continuo, solo dei campioni in istanti costanti (ogni secondo o ogni centesimo di secondo) e approssimandoli con i multipli della risoluzione scelta.
La prima operazione non comporta, infatti, perdita di informazione ossia è possibile  ricostruire il segnale originario esattamente com’era a partire dai soli campioni purché la frequenza di campionamento sia sufficientemente elevata (fc>2B dove B è la banda del segnale), con questo risultato che è detto Teorema di Nyquist-Shannon.

Shannon, mostrò anche che l’informazione poteva essere codificata per essere sufficientemente immune al rumore. Chiave del ragionamento fu ancora il concetto di entropia. L’entropia entra con un ragionamento di questo tipo: il trasmittente non è altro che un generatore di simboli che vengono emessi con certe frequenze di apparizione, ossia probabilità. La sua attività, dunque, può essere più o meno imprevedibile, ovvero disordinato. Più risulta difficile, in particolare, sapere quale sarà il prossimo simbolo, maggiore dovrà essere l’entropia perché più entropico sarà il suo comportamento.


CRITTOGRAFIA
Visto che l'entropia non è altro che la media pesata delle informazioni associate a ciascun simbolo, misurata in bit perché costituente una quantità di informazione. Usare un numero di simboli maggiore di quelli strettamente necessari serva a proteggere i messaggi dai possibili rumori perché le nostre reti telematiche riescono a spedire e ricevere mail, messaggi vocali, immagini, etc senza errori.
Il concetto di base è anche qui la ridondanza, dato che questa può essere inserita non solo per aiutare il destinatario a decifrare i bit che riceve, ma anche, all’opposto, per renderli più indecifrabili. Simboli inseriti in modo casuale, infatti, possono rendere la decodifica quasi impossibile se non si possiedono le informazioni per ricostruire a partire dalla sequenza ricevuta il messaggio originario (chiave).
Se non si sa la codifica utilizzata, rimane impossibile decifrare il messaggio.
Shannon nella sua trattazione enunciò due proprietà necessarie per realizzare un buon algoritmo di cifratura: la confusione e la diffusione. La prima fa riferimento alla complessità della relazione fra chiave e testo cifrato, la seconda alla capacità dell’algoritmo di distribuire le correlazioni statistiche lungo tutto l’alfabeto Nel lavoro compare anche, per la prima volta, la dimostrazione dell’esistenza di un codice crittografico perfetto: il codice di Vernam), basato su una chiave lunga come l’intero messaggio e utilizzata una sola volta. Una crittografia adeguata è, dunque, ciò che ci permette di inviare messaggi che, anche se intercettati (nel caso della rete, con programmi denominati sniffer) sarebbero molto difficili da decifrare.