Amici della Scienza

Shannon, padre della teoria dell’informazione

“Domani pioverà.” La definiremmo una notizia non molto interessante, se fossimo a Londra in ottobre e, viceversa, un’informazione preziosa, se fossimo ad agosto nel Sahara. Eppure, se ci venisse chiesto perché, probabilmente saremmo in difficoltà.

Ancora: utilizziamo quotidianamente mail e SMS e acquistiamo spesso prodotti o servizi su internet. Se dovessimo specificare, però, perché queste tecnologie sono così affidabili, potremmo avere altrettanti problemi. C’è stata una persona, però, che, pur non avendo mai usato uno smartphone o mai manifestato una particolare abilità con i computer – come recitano diverse sue biografie – saprebbe illuminarci da svariati punti di vista: Claude Shannon, uno dei più geniali matematici e ingegneri di sempre, considerato da molti [0] il padre della digital era.

Shannon
Shannon

Shannon nacque nel 1916 a Petoskey (USA) e si laureò, a soli venti anni, in matematica e ingegneria elettronica. Lavorò successivamente presso i Laboratori Bell, ricoprendo anche la cattedra di professore ordinario presso il Massachussets Institute of Technology. Il suo ambito di interesse spaziò dall’analisi dei circuiti, ai calcolatori analogici, alla genetica, alla crittografia, oltre naturalmente alle telecomunicazioni.

Il suo lavoro probabilmente più noto, il saggio Una teoria matematica della comunicazione [1], fu pubblicato nel 1948 a sintetizzare gran parte dell’esperienza precedente. Shannon era famoso per il suo approccio basato sulla riduzione della complessità. Dichiarava, infatti, a tal proposito [2]:

I don’t care what kind of problem: a machine to design, or a physical theory to develop, or a mathematical theorem to prove or something of that kind. Probably a very powerful approach to this is to attempt to eliminate everything from the problem except the essentials; that is, cut it down to size.

Un problema semplice – ma contenente tutti gli elementi essenziali – ovvero un modello può essere formalizzato matematicamente e come tale risolto. E proprio ragionando in questo modo arrivò al seguente, celebre, schema:

General Communication System
General Communication System

 

Questo nasceva nell’ambito delle telecomunicazioni ma era capace di descrivere la comunicazione anche a livello più generale, ad esempio fra esseri viventi.

Il modello ha il pregio di mettere subito in luce alcuni fatti essenziali. Innanzitutto: un processo di comunicazione è caratterizzato da due attori fondamentali (emittente e ricevente) e da un’informazione che viene scambiata (messaggio). Siccome il messaggio deve passare attraverso un supporto fisico (canale) e questo può essere affetto da disturbi (rumore) è necessaria una codifica di sorgente, ovvero una trasformazione del contenuto in una forma tale da renderlo più immune possibile al rumore. Dualmente, è necessaria anche una decodifica di destinazione affinché il contenuto possa essere fruito dal destinatario.

I limiti di questa concettualizzazione emergono principalmente quando si tenta di utilizzarla in ambiti molto diversi dall’originario – ad esempio la comunicazione fra umani – e per questi è stato integrato soprattutto con il concetto di feedback (sviluppato negli stessi anni da Norber Wiener nella sua Cibernetica), e con il ruolo degli aspetti culturali, psicologici, emotivi e contestuali. Resta, allo stesso tempo, un punto fermo anche oggi per chiunque voglia occuparsi di comunicazione.

Shannon definì la sua teoria “matematica” perché non si limitò a evidenziare degli elementi e a organizzarli in un grafico ma fornì anche delle regole quantitative per descrivere dei comportamenti e impostare dei legami causa-effetto.

La prima e, per certi versi, basilare definizione è quella di informazione. Si può ricostruire il ragionamento applicandolo al nostro esempio delle previsioni del tempo come segue. Perché associamo intuitivamente alla notizia sulla pioggia nel Sahara maggiore informazione? Forse perché nel Sahara non piove spesso, si potrebbe ipotizzare. Ne segue che, data una proposizione X e la sua probabilità di verificarsi pX, è pensabile l’associare la sua informazione IX all’inverso di pX; in questo modo, infatti, più la probabilità di un evento è piccola, più il sapere che può potenzialmente comunicare (informazione) è grande. Matematicamente Shannon definì la IX in termini di 1/pX facendo intervenire anche un logaritmo:

Ilog(1/pX) = –logpX

La base del logaritmo è semplicemente un fattore di scala e, tipicamente, viene scelto il 2, portando l’unità di misura dell’informazione a essere il bit, ossia il binary digit, il numero di cifre binarie (0,1) necessarie per rappresentarla. Così se, ad esempio, un certo evento ha probabilità di verificarsi del 10% la quantità di informazione ad esso associata sarà log(10)=3.32, ossia servirà un segnale di 4 impulsi on/off per poterlo comunicare (10 si scrive 1010 in base 2).

L’aver slegato la quantità di informazione dal concetto e dal sistema simbolico usato – non è rilevante né di cosa si parla né in quale linguaggio lo si fa – rappresentava, per i tempi, una novità assoluta. E’ anche ciò che ci permette di capire perché la frase “domani pioverà” con cui abbiamo cominciato questo documento può portare più o meno informazione: dipende del contesto che la rende più o meno probabile, non da quello di cui tratta.

E’ utile notare, inoltre, che l’idea di rappresentare un’informazione con un insieme di bit (ossia il rendere quella binaria la codifica per eccellenza) è stata anch’essa uno dei contributi fondamentali di Shannon che utilizziamo quotidianamente navigando su internet o utilizzando un PC. Secondo alcuni autori questa è arrivata come conseguenza della sua esperienza come telegrafista alla Wester Union dato che non è altro che una generalizzazione dell’approccio di Morse, per cui le parole erano rappresentate da sequenze di linee e punti.

L’utilizzo di segnali discreti nel tempo e in ampiezza si collega anche agli studi di Shannon in materia di campionamento [6] che hanno aperto la strada al tema della conversione analogico – digitale.

Come associare, infatti, a una grandezza continua un numero, da convertire poi in sequenza di impulsi? Semplice: prendendo, dal segnale continuo, solo dei campioni in istanti equispaziati nel tempo (es. ogni secondo) e approssimandoli con i multipli della risoluzione scelta (es. c=12.1 Volt trasformato in n=12=1100  in base 2, presa la risoluzione pari a 1 Volt).

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.

Campionamento
Campionamento di un segnale tempo continuo y(t) con passo T=1/fc

Shannon, comunque, non si fermò qui, mostrando anche come l’informazione doveva essere codificata per essere sufficientemente immune al rumore. Chiave del ragionamento fu il concetto di entropia, il primo tentativo di misura della ricchezza informativa emessa.

Fino ad allora il termine era stato utilizzato solo in termodinamica, come grado di disordine presente in un sistema [3], legato a grandezze come temperatura e calori scambiati reversibilmente. Oppure in meccanica statistica, sempre come livello di disordine ma espresso in funzione del numero G delle combinazioni possibili dei costituenti elementari di un sistema [4], essendo:

S = K*log G

dove K è la costante di Boltzmann.

Nella teoria di Shannon l’entropia entra con un ragionamento di questo tipo: l’emittente 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 disordinata. Più risulta difficile, in particolare, sapere quale sarà il prossimo simbolo, maggiore dovrà essere l’entropia perché più entropico sarà il suo comportamento. Queste considerazioni sono alla base della seguente formula:

Entropia

da cui deriva che l’entropia non è altro che la media pesata delle informazioni associate a ciascun simbolo, misurata in bit perché costituente una quantità di informazione.

L’introduzione di tale concetto fu un passaggio epocale perché permise di specificare la lunghezza minima di un messaggio necessaria per una sua decodifica corretta (Teorema della codifica di sorgente) in assenza e in presenza di vincoli sul canale (capacità e rumore, Teorema della codifica di canale). Tutto questo, in particolare, rovesciò la credenza, allora dominante, secondo cui l’unico modo per diminuire gli errori in ricezione fosse la riduzione del numero di simboli per secondo emessi, senza riconoscere alcuna influenza al tipo di canale, al livello del rumore e alla ridondanza della codifica.

Abbiamo capito, dunque, perché frasi diverse possono portare informazioni diverse e perché la ridondanza (usare un numero di simboli maggiore di quelli strettamente necessari) serva a proteggere i messaggi dai possibili rumori e quindi, ad esempio, perché le nostre reti telematiche riescono a spedire e ricevere mail e SMS (messaggi vocali, immagini e via dicendo …) senza errori. Ci mancherebbe, a questo punto, la comprensione del meccanismo con cui i messaggi vengono resi confidenziali, quando, come nel caso delle transazioni con carta di credito, ciò è necessario.

Anche qui Shannon potrebbe essere la nostra guida, in particolare con il saggio Una Teoria matematica per i sistemi crittografici, del 1949. 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).

Così, ad esempio, anche la sola traduzione del messaggio “pd4ppd4” in “mamma” non è così banale se il destinatario non sa che è stata utilizzata una delle più semplici e antiche tecniche crittografiche: il cifrario di Cesare (con spostamento k=3 e inserimento del simbolo ridondante “1” dopo ogni vocale).

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. Cose che mancano evidentemente nell’esempio precedente (in cui il legame fra messaggio in chiaro e messaggio cifrato è una semplice traslazione e in cui si ha sempre a->d, b->e etc…) che costituisce, infatti, un sistema di codifica molto debole.

Nel lavoro compare anche, per la prima volta, la dimostrazione dell’esistenza di un codice crittografico perfetto: il codice di Vernam (dal nome del tecnico dell’AT&T che lo scoprì nel 1919), basato su una chiave lunga come l’intero messaggio e utilizzata una sola volta. Un algoritmo che pone grossi problemi di realizzabilità pratica ma che, se i progressi tecnologici porteranno all’effettiva realizzazione di computer a funzionamento quantistico (e dunque a potenzialità di calcolo di diversi ordini di grandezza superiori agli attuali), potrà essere sfruttato per costruire metodi di comunicazione completamente sicuri.

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. Ed è ciò che, ad esempio, viene tipicamente impiegato nelle pagine web dedicate all’e-commerce, basate sulla tecnologia HTTPS (Secure Hyper Text Transfer Protocol). Quando, il nostro browser ci segnala l’uso di quel protocollo (di norma tramite una piccola icona a forma di lucchetto), dunque, possiamo stare relativamente tranquilli:  i dati che transitano, sono codificati in sequenze di simboli, incomprensibili per chiunque non possieda la chiave, ossia emittente e destinatario.

Beh, quasi incomprensibili, perché la codifica Vernam è stata impiegata solo in rare occasioni durante la guerra fredda e non è utilizzata per le comunicazioni su internet. C’è sempre una piccola probabilità, dunque, che un malintenzionato possa scoprire, da quei caratteri apparentemente privi di senso, una chiave con cui decodificarli, ad esempio con metodi iterativi.

Ecco perché è consigliabile non lasciare somme troppo alte sulle carte che usiamo per gli acquisti on-line.

Anche Shannon, di certo, sarebbe d’accordo.

 

Riferimenti e approfondimenti

[0] Waldrop; M. Mitchell, Claude Shannon: Reluctant Father of the Digital Age URL: http://www.technologyreview.com/magazine/jul01/waldrop.asp

[1] Claude E. Shannon; Warren Weaver, Mathematical Theory of Communication, University of Illinois Press, 1963

[2] Eugene Chiu; Jocelyn Lin; Brok Mcferron; Noshirwan Petigara; Satwiksai Seshasai, Mathematical Theory of Claude Shannon URL: http://users.ece.utexas.edu/~adnan/syn-07/Shannon1.pdf

[3] Mencuccini Corrado; Silvestrini Vittorio, Fisica I Meccanica – Termodinamica, Liguori, 2006

[4] J. M. Smith; H.C.Van Ness; M. M. Abbot, Introduction to Chemical Engineering Thermodynamics, McGraw-Hill, 2000

[5] Claude E. Shannon, Communication Theory of Secrecy Systems, URL: http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf

[6] Claude E. Shannon, Communication in the Presence of Noise, Proceedings Of The IEEE, VOL. 86, NO. 2, FEBRUARY 1998

Amici della Scienza

0 0 vote
Article Rating
Subscribe
Notificami
guest
0 Commenti
Inline Feedbacks
View all comments
Translate »
0
Would love your thoughts, please comment.x
()
x