Tu sei qui

A cento anni dalla nascita di Claude Elwood Shannon (30 aprile 1916 - 24 febbraio 2001)

Aprile 2016
Alberto Pettorossi
University of Rome Tor Vergata

La sua vita e i suoi studi.

Cento anni fa nasceva a Petoskey in Michigan (USA) Claude Shannon, studioso statunitense che nel secolo scorso ha contribuito in modo fondamentale alla nascita di un nuovo campo della scienza, oggi conosciuto col nome di Teoria dell’Informazione. Egli è anche noto per aver messo a punto tecniche di progetto dei circuiti elettronici e per alcuni risultati nel campo della crittografia. 

La Teoria dell’Informazione fondata da Claude Shannon è alla base delle telecomunicazioni moderne e senza questa teoria non si sarebbe potuta sviluppare tutta la tecnologia delle telecomunicazioni come oggi noi la conosciamo, fino alla straordinaria diffusione di Internet negli ultimi anni.

Shannon studiò al Massuchussetts Institute of Technology (MIT) negli Stati Uniti d’America e, durante i suoi studi, lavorando allo sviluppo di un calcolatore analogico, ideò, sulla base dell’Algebra di Boole, alcune tecniche di progetto dei circuiti elettronici. I risultati furono pubblicati nel lavoro: “A Symbolic Analysis of Relay and Switching Circuits”, Trans. Am. Inst. Elect. Engrs 57, 713–723 (1938). Da allora tali tecniche hanno rimpiazzato le precedenti metodologie empiriche in uso. 

Poi, nei suoi studi di dottorato di ricerca (Ph. D.), Shannon si dedicò alla genetica Mendeleiana, guidato dal Prof. Vannevar Bush, suo supervisore all’MIT. La sua tesi di Ph. D. intitolata: “An Algebra for Theoretical Genetics” fu pubblicata nel 1940.

All’inizio della Seconda Guerra Mondiale Shannon lavorò come ricercatore all’Institute for Advanced Studies a Princeton nel New Yersey (USA), dove ebbe modo di conoscere, tra gli altri, John von Neumann (inventore dell’architettura dei computer moderni), Kurt Gödel (logico e matematico insigne) e Albert Einstein (fisico teorico). Shannon lavorò poi, durante la Seconda Guerra Mondiale, nei Bell Laboratories, sempre nello stato del New Jersey, contribuendo allo sviluppo di sistemi d’arma e alla teoria della crittografia. 

I risultati ottenuti da Shannon nel campo della crittografia furono pubblicati nel lavoro: “Communication Theory of Secrecy Systems”, Bell Syst. Tech. J. 28, 656–715 (1949). In quel lavoro Shannon dimostrò che il sistema chiamato “one-time-pad crittografico” è inattaccabile e che ogni sistema di crittografia che sia inattaccabile deve avere le stesse caratteristiche dell’one-time-pad e, cioè, la sua chiave crittografica deve essere: (i) casuale, (ii) lunga come il testo da criptare, (iii) usata esattamente una sola volta (in tutto o in parte) e (iv) tenuta segreta.

Mentre era ai Bell Laboratories, Shannon ebbe anche l’occasione di interagire con Alan Turing e di conoscere le idee di Turing sulla crittografia, sulla calcolabilità e sulla macchina di calcolo astratta, che oggi gli informatici chiamamo la Macchina di Turing Universale. Questa macchina è in grado di comportarsi come una qualsiasi altra macchina di calcolo a patto di fornirgli la codifica della macchina da simulare. 

Dopo la Seconda Guerra Mondiale Shannon proseguì gli studi che lo portarono alla fondazione e allo sviluppo della Teoria dell’Informazione, teoria per cui egli è più noto. È questa una teoria che si basa sulla Teoria della Probabilità e che permette di progettare canali di trasmissione, cioè, canali per trasferire informazione da una sorgente a uno o più destinatari, in modo affidabile ed efficiente, mediante messaggi discreti o continui, anche in presenza di rumore o disturbi di varia natura.

Questa teoria permette all’ingegnere delle telecomunicazioni di progettare i canali di trasmissione dell’informazione con delle tecniche in un certo senso analoghe a quelle che adotterebbe un ingegnere idraulico per progettare una conduttura per il trasporto dell’acqua e garantire una determinata portata nell’unità di tempo. 

La Teoria dell’Informazione, dopo la sua introduzione da parte di Shannon, ha avuto in breve tempo un grande successo e ha rapidamente manifestato la sua importanza. Citiamo i seguenti lavori fondamentali di Shannon in questo campo (e il lettore potrà far riferimento ad essi per eventuali approfondimenti):

(i) “A Mathematical Theory of Communication”, Bell Syst. Tech. J. 27, 379–423 and 623–656 (1948), 

(ii) “Communication in the Presence of Noise”, Proc. Inst. Radio Engrs 37, 10–21 (1949),

(iii) “Probability of Error of Optimal Codes in a Gaussian Channel”, Bell Syst. Tech. J. 38, 611–656 (1959) e 

(iv) “Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels”, Inform. Control 10, 65–103 e 522–552 (1967) (lavoro fatto in collaborazione con R. G. Gallager e E. R. Berlekamp).

Dopo pochi anni dalla pubblicazione dei risultati di Shannon, già in moltissime università del mondo, si tenevano corsi di Teoria dell’Informazione, di Teoria dei Codici e di Teoria dei Segnali che si basavano appunto sugli studi di Shannon.

Nella sua vita Shannon ha avuto molti hobby e si è interessato di giochi di destrezza, di schacchi e anche di didattica dei calcolatori e di applicazioni della Teoria dell’Informazione alla Teoria dei Giochi. 

Egli fece anche studi relativi all’Intelligenza Artificiale e sviluppò un dispositivo che egli chiama ‘mouse’ (non lo si confonda con il mouse dei computer attuali) che si poteva muovere in un labirinto e che era in grado di trovarne l’uscita, ricordando le posizioni che aveva già visitato. Il mouse faceva uso di tecniche di esplorazione del labirinto simili a quelle che oggi vanno sotto il nome di tecniche di backtracking ed era capace anche di accumulare conoscenza, in base alle precedenti esplorazioni del labirinto stesso. Nella figura si vede Shannon da giovane che posiziona il mouse nel labirinto.

  

Shannon che pone il mouse nel labirinto.

Negli ultimi anni della sua vita Shannon fu colpito dalla malattia di Alzheimer. Così egli che era stato ammirato per l’acutezza dell’ingegno e che aveva tanto contribuito alla tecnologia delle comunicazioni sicure e affidabili tra gli uomini, purtroppo non fu più in grado di comunicare con le persone, familiari e amici, che gli erano accanto.

La Teoria dell’Informazione di Shannon.

Illustriamo ora le idee di base della Teoria dell’Informazione di Shannon. Presenteremo anche dei risultati teorici, cioè dei teoremi, che saranno utili al lettore per capire, seppure in modo elementare, le peculiarità di questa teoria. Questi risultati eviteranno anche il pericolo di confondere la Teoria dell’Informazione di Shannon con altre teorie della comunicazione che possono esistere in ambito psicologico, sociologico e filosofico.

Il sistema di comunicazione.

Partiamo dalla considerazione che in una qualsiasi comunicazione tra persone esiste: (1) una semantica, cioè il significato delle idee da comunicare, (2) una sintassi, cioè le parole della lingua usata per esprimere le idee (essa può essere, per esempio, la lingua italiana o la lingua inglese) e (3) un supporto fisico, che in genere è composto da varie sottocomponenti che ora specificheremo con riferimento al caso particolare della comunicazione vocale tra due persone. In questo caso il supporto fisico è fatto dalle seguenti sottocomponenti: (i) l’apparato vocale della persona che parla, apparato che serve a trasformare le parole in onde di pressione dell’aria, (ii) le stesse onde di pressione che si propagano nell’aria con la velocità del suono e, infine, (iii) l’apparato uditivo della persona che ascolta. 

Ovviamente si potrebbero comprendere tra le sottocomponenti del supporto fisico di una comunicazione anche, da una parte, il cervello della persona che parla e, dall’altra, il cervello della persona che ascolta. Ma non ci addentriamo nelle considerazioni che interessano i processi mentali delle persone, esattamente perché queste considerazioni, come cercheremo di illustrare brevemente qui di seguito, non sono in alcun modo rilevanti nella Teoria dell’Informazione di Shannon.

Usando una distinzione familiare a chi si interessa di informatica, possiamo dire che le componenti semantiche e sintattiche della comunicazione fanno riferimento al software della comunicazione e che il substrato fisico fa invece riferimento all’hardware della comunicazione. 

Ebbene, sono le proprietà astratte del software della comunicazione che sono state oggetto degli studi di Shannon e hanno portato allo sviluppo della Teoria dell’Informazione. Tali studi hanno realizzato nel campo della comunicazione la separazione tra l’hardware e il sofware che, non a caso, si è realizzata nello stesso periodo di tempo nel campo del calcolo automatico con i contributi fondamentali di Alan Turing e John von Neumann.

In effetti, la Teoria dell’Informazione di Shannon si interessa solo delle proprietà sintattiche della comunicazione e non di quelle semantiche, ma siccome, come detto, le studia ad un livello astratto, i risultati della sua teoria possono essere applicati a molti sistemi di comunicazione concreti diversi (per esempio, a quelli della comunicazione di testi, o di voce, o di musica, o di immagini fisse o di immagini in movimento). Questa generalità di applicazione dei risultati della teoria ha determinato la sua grande importanza e validità.

Da un punto di vista astratto, un sistema di comunicazione di messaggi, come lo considera Shannon, è costituito dalle seguenti componenti: (1) la sorgente del messaggio, (2) il trasduttore di trasmissione, (3) il codificatore (di sorgente e di canale), (4) il canale di trasmissione, (5) il decodificatore, (6) il trasduttore di ricezione e, infine, (7) il destinatario del messaggio. 

Un esempio di queste componenti chiarirà le idee. La componente (1) è la persona che parla, la componente (2) è il microfono che genera un segnale elettrico, la componente (3) è il processo di digitalizzazione, codifica e criptaggio del segnale elettrico, la componente (4) è lo spazio ove il segnale elettrico si propaga, la componente (5) è il processo di decriptaggio, decodifica e ricostruzione analogica del segnale elettrico (cioè, esso è l’inverso della componente (3)), la componente (6) è l’altoparlante che genera suoni a partire dal segnale elettrico e, infine, la componente (7) è la persona che ascolta.

Nei suoi studi Shannon si concentra prevalemente sulle componenti intermedie (3)-(4)-(5) del sistema e, cioè, sulla codifica, la trasmissione e la decodifica del messaggio e analizza le caratteristiche di queste componenti, lasciando ad altri campi dell’ingegneria, e in particolare all’ingegneria elettronica, gli studi e le ricerche relativi alle componenti (2) e (6), relative alla trasduzione in trasmissione e alla trasduzione in ricezione.

L’informazione come grandezza misurabile.

Shannon definisce la quantità di informazione che è portata da un messaggio trasmesso attraverso un canale da una sorgente ad un destinatario, come misura della riduzione dell’incertezza del destinatario, quando egli riceve il messaggio. In particolare, il destinatario riceve tanta più informazione da un messaggio ricevuto quanto più improbabile per lui era il messaggio prima che fosse ricevuto. Nella teoria di Shannon la misura di quantità di informazione associata ad un messaggio è proprio derivata dalla misura di probabilità di occorrenza del messaggio stesso, e si esprime in rapporto ad una unità di misura chiamata bit, che è la quantità di informazione rimossa dalla conoscenza di un messaggio tra due che hanno la stessa probabilità. Quindi, la quantità di informazione di un messaggio ricevuto è pari a n bit quando esso è uno di 2n possibili messaggi ritenuti equiprobabili, con probabilità 1/2n

Se ad esempio la sorgente può emettere uno di otto messaggi equiprobabili il destinatario, quando riceve il messaggio costituito da uno qualsiasi di questi otto messaggi, riceve 3 bit di informazione (essendo 3 è il logaritmo in base 2 di 8, cioè dell’inverso della probabilità di emissione). Se, però, la sorgente, può emettere gli otto messaggi con le seguenti probabilità di emissione diverse tra di loro: 1/2, 1/4, 1/8, 1/16, 1/64 , 1/64, 1/64, 1/64, allora il destinatario riceve 3 bit di informazione se riceve il terzo messaggio (giacché 3=log2 8) ma riceve 6 bit di informazione se riceve il quinto messaggio 5 (giacché 6=log2 64).

Si notino due cose: (i) per Shannon l’informazione associata alle sequenze di caratteri non dipende dal significato delle sequenze di caratteri, ma dipende solo dalle probabilità di emissione di dette sequenze, e (ii) qualora ci fossero errori di segnalazione durante la trasmissione, i differenti messaggi che si possono ricevere possono essere in numero diverso da quelli che si possono inviare.

Presentiamo ora due risultati di fondamentale importanza nella Teoria dell’Informazione di Shannon evitando, per quanto possibile, le difficoltà matematiche e dandone un significato intuitivo.

L’entropia in Teoria dell’Informazione.

Introduciamo dapprima la nozione di entropia di una sorgente di messaggi. L’entropia di una sorgente è definita come la quantità di informazione media per messaggio. Questa quantità presenta un’analogia concettuale con la nozione di entropia che si definisce in Termodinamica (per questo Shannon ha adottato questo termine). Intuitivamente parlando, entrambe le nozioni sono legate con il disordine statistico (della sorgente e, rispettivamente, di un sistema termodinamico): l’entropia è tanto più grande, quanto più grande è questo disordine. 

In particolare, se i messaggi sono costituiti da sequenze di M caratteri statisticamente indipendenti, e se i possibili caratteri sono due (alfabeto binario) ed equiprobabili, l’entropia della sorgente è M bit per messaggio, cioè un bit per carattere. Se i caratteri non sono equiprobabili, o non sono statisticamente indipendenti, l’entropia è più piccola di un bit per carattere. Ovviamente, se l’alfabeto comprende più di due caratteri, l’entropia può essere maggiore di un bit per carattere.

Il teorema della codificazione.

Presentiamo ora il primo importante risultato della Teoria dell’Informazione, che va sotto il nome di teorema fondamentale della codificazione. Tale teorema vale, in particolare, per sorgenti discrete (cioè, quelle che emettono messaggi formati con caratteri tratti da un alfabeto di dimensioni finite), stazionarie e senza memoria (non ci soffermiamo qui a definire formalmente queste proprietà) e può essere espresso come segue: per ogni sorgente di entropia H bit per carattere, per ogni numero reale s > 0, esiste un numero intero L sufficientemente grande per cui si possono codificare blocchi di caratteri di lunghezza L in corrispondenti sequenze di caratteri binari, in modo tale che, mediamente, la lunghezza L2 di queste sequenze binarie risultanti soddisfa la seguente relazione H ≤ L≤ H+s.

Questo teorema stabilisce dunque che è possibile codificare blocchi di caratteri emessi da una sorgente di entropia H (bit per carattere) in modo tale che per ogni carattere della sorgente si usano in media circa H caratteri binari, a patto di codificare blocchi sufficientemente lunghi.

L’interesse applicativo di questo teorema sta nel fatto che se la sorgente emette messaggi in alfabeto binario (è questa la forma in cui sono rappresentati usualmente nei sistemi informatici) poiché l’entropia della sorgente (bit per carattere) è molto spesso assai minore di uno, la lunghezza delle sequenze binarie che ne risulta è assai ridotta. Per questo, il teorema assicura la possibilità di realizzare quella che si chiama compressione statistica dei messaggi di sorgente. Il fatto che l’entropia della sorgente binaria sia minore di uno riflette l’esistenza di certa ridondanza espressiva, ridondanza che è rimossa dalla compressione statistica.

Si noti, tuttavia, che c’è un prezzo tecnologico da pagare nel fare la compressione statistica perché, se è necessario usare alti valori di L, il processo di codifica (e quello di decodifica da lato del destinatario) dei messaggi in blocchi di caratteri di lunghezza L può risultare complicato e dispendioso in termini di risorse di calcolo. 

Il teorema della codificazione per canali rumorosi.

Oltre al problema della codifica di sorgente, la Teoria dell’Informazione di Shannon permette di affrontare razionalmente il problema fondamentale di garantire la trasmissione corretta da una sorgente a un destinatario anche in presenza di errori, dovuti al fatto che il trasferimento al destinatario delle sequenze di caratteri, effettuata mediante segnali fisici (forme d’onda), non è indenne da disturbi (rumore). 

Il secondo risultato della Teoria dell’Informazione che ora presentiamo, va sotto il nome di teorema fondamentale della codificazione per canali rumorosi, e riguarda proprio il caso in cui il segnale fisico, attraversato il canale, arrivi al trasduttore di ricezione con modificazioni dovute alla presenza di disturbi.

Per semplicità, presentiamo questo teorema nel caso particolare di un canale binario (cioè, un canale in cui si possono immettere e da cui si possono prelevare sequenze di caratteri binari, ‘a’ o ‘b’) simmetrico, stazionario, per cui se si immette ‘a’, allora si riceve ‘a’ con probabilità p e si riceve ‘b’ con probabilità 1–p. Analogamente, per la simmetria del canale, se si immette ‘b’, allora si riceve ‘b’ con probabilità p e si riceve ‘a’ con probabilità 1–p. Il fatto che il canale sia rumoroso implica che la probabilità p di errore sia diversa da zero, mentre la stazionarietà del canale implica che la probabilità p di errore non vari nel tempo. 

Assumiamo anche che l’entropia della sorgente binaria sia 1 bit per carattere, cioè i caratteri ‘a’ e b abbiano la stessa probabilità di emissione (questa è la situazione pratica nel caso che sia stata effettuata a monte la compressione di sorgente). 

La capacità per carattere di canale è la massima quantità di informazione media per carattere che il canale può trasferire. Nel caso di canale binario simmetrico stazionario rumoroso tale capacità è C1 = 1–(H(p)+H(1–p)), ove H(x) denota il prodotto x log2 (1/x). Il teorema della codificazione per canali rumorosi asserisce che, per ogni canale binario simmetrico stazionario rumoroso con capacità per carattere C1, per ogni numero reale s > 0, esiste una coppia di numeri (r,n) tale che se si codificano blocchi di r caratteri binari provenienti dalla sorgente in blocchi di n caratteri binari da immettere nel canale, se r/n < C1, allora la probabilità media di errore si può rendere minore di s adottando un opportuno metodo di codifica.

In altre parole questo teorema (anche in forme più generali) dice che, anche nel caso in cui un canale sia rumoroso si può, per mezzo di una opportuna codifica in trasmissione, rendere la probabilità media d’errore nella decodifica piccola a piacere, cioè si possono realizzare trasmissioni affidabili anche attraverso un canale rumoroso. L’esistenza di questa codifica di blocchi di lunghezza r in blocchi di lunghezza n che riduce la probabilità di errore al di sotto di un qualunque desiderato limite, dipende dalla validità della relazione r/n < C1. Tuttavia il teorema non indica in quale modo specifico tale la codifica debba essere realizzata. 

Ne consegue che, per instaurare comunicazioni affidabili, la quantità di informazione erogata dalla sorgente nell’unità di tempo, deve essere inferiore al prodotto della capacità per carattere del canale moltiplicata per la frequenza con cui i caratteri binari, risultato della codifica, sono immessi nel canale. Nel caso infatti in cui questa condizione non sia rispettata, allora è comunque impossibile rendere piccola quanto si vuole la probabilità di errore in ricezione.

Software e hardware della comunicazione.

Si può dire che dopo Shannon i processi di sviluppo dell’hardware e del sofware della comunicazione si separano. Lo sviluppo dell’harware viene demandato alle tecniche dell’ingegneria elettronica e lo sviluppo del software viene demandato agli studi di Teoria dell’Informazione e a quelle di Teoria dei Segnali. Quest’ultima teoria studia le proprietà dei segnali che rappresentano i messaggi che debbono essere inviati lungo i canali di trasmissione. I segnali vengono studiati come funzioni matematiche che variano al variare del tempo e che modellano le variazioni di grandezze elettriche (per esempio, il potenziale elettrico nel caso dei segnali elettrici e il campo elettromagnetico nel caso delle onde radio).

In ingegneria elettronica si sviluppano i metodi per la costruzione di circuiti atti a realizzare le trasformazioni dei segnali elettrici con la rapidità e le caratteristiche che la Teoria dell’Informazione dimostrano essere necessarie per una buona qualità della comunicazione, cioè, per garantire una sufficiente quantità di bit trasmessi nell’unità di tempo. 

Progetto di sistemi di comunicazione.

La Teoria dell’Informazione di Shannon permette di progettare un sistema di comunicazione sulla base dei bit al secondo che debbono essere trasmessi. Per esempio, nel caso di un sistema televisivo, si tratta di rinfrescare l’immagine trasmessa con un’opportuna frequenza in modo tale che l’occhio umano percepisca l’immagine in movimento. Si tratta di immettere nel segnale televisivo abbastanza informazione nuova ogni secondo per aggiornare opportunamente i pixel dell’immagine dello schermo televisivo. 

Sulla base delle caratteristiche fisiologiche dell’occhio umano, la Teoria dell’Informazione di Shannon permette di calcolare questa quantità di informazione nuova da immettere nel canale di trasmissione nell’unità di tempo e di determinare così in modo preciso la cosiddetta larghezza di banda che è necessaria nella trasmissione del segnale televisivo. Per questo contributo Shannon si è basato su risultati precedenti e, in particolare, sul Teorema del Campionamento formulato da H. Nyquist e R.V.L. Hartley, anch’essi ricercatori nei Bell Laboratories. Questi risultati permettono di passare, senza perdita di informazione, da segnali continui a segnali discreti (in cui essenzialmente si trasmettono sequenze di numeri), a patto che i segnali continui abbiano una larghezza di banda limitata in frequenza. Sotto questa ipotesi, a partire dai segnali discreti ottenuti per discretizzazione dei segnali continui, è possibile ricostruire i segnali continui di partenza (ovviamente, anche questa ricostruzione si fa senza perdita di informazione). 

Questa capacità di trasformazione dal continuo al discreto e viceversa, senza perdita di informazione, è una proprietà molto importante e ha dato luogo a tutto quel processo di digitalizzazione che ha caratterizzato lo sviluppo tecnologico delle telecomunicazioni negli ultimi decenni e che, molto probabilmente, continuerà a caratterizzarlo ancora nei decenni futuri.


L'autore del contributo desidera ringraziare il prof. Giovanni Jacovitti dell'Università di Roma "Sapienza".