Teoria dell'informazione

La teoria dell'informazione è una disciplina dell'informatica e delle telecomunicazioni il cui oggetto è l'analisi e l'elaborazione su base matematica dei fenomeni relativi alla misurazione e alla trasmissione di informazioni su un canale fisico di comunicazione. Pioneri del campo di studi sono stati Harry Nyquist e Ralph Hartley, negli anni '20, e Claude Shannon negli anni '40.

La grandezza che misura la quantità di dati prende il nome di entropia ed è solitamente espressa come numero di bit necessari per immagazzinare o trasmettere l'informazione. Ad esempio, se un alfabeto ha un'entropia pari a 4 bit, allora, preso un numero sufficiente di parole costruite con tale alfabeto, in media sono necessari 4 bit per rappresentare ogni lettera.

L'applicazione dei concetti fondamentali della teoria dell'informazione include la compressione senza perdita (es. zip), la codifica con perdita (es. mp3) e le modulazioni digitali utilizzate nelle trasmissioni ethernet. La teoria dell'informazione si pone a metà strada tra la matematica applicata, la statistica, la fisica applicata, le telecomunicazioni e l'informatica. Il suo impatto è stato fondamentale nelle missioni spaziali, nell'invenzione del CD, dei telefonini, di Internet, nello studio della linguistica ed in numerosissimi altri campi.

Storia 

L'evento decisivo che determinò la nascita della teoria dell'informazione e la portò immediatamente all'attenzione mondiale fu la pubblicazione dell'articolo "A Mathematical Theory of Communication", da parte di Claude Shannon sul Bell System Technical Journal nel luglio e nell'ottobre del 1948.

Prima di questo articolo, sempre nei Bell Labs, erano stati sviluppati pochi concetti teorici sull'informazione ed era sempre stata assunta implicitamente l'ipotesi di trattare eventi equiprobabili. L'articolo del 1924 di Harry Nyquist, Certain Factors Affecting Telegraph Speed (Alcuni Fattori che Influenzano la Velocità del Telegrafo), contiene alcune sezioni teoriche in cui si quantificano l'"intelligenza" e la "velocità" a cui si può trasmettere su un sistema di comunicazione, dando la relazione , dove W è la velocità della trasmissione di intelligenza, m è il numero di differenti livelli di tensione su cui si può scegliere ad ogni passo e K è una costante. L'articolo del 1928, ad opera di Ralph Hartley, Transmission of Information (Trasmissione dell'Informazione), usa la parola informazione per indicare una quantità misurabile, che riflette la capacità del ricevitore di distinguere una sequenza di simboli da un'altra; l'informazione nel testo viene definita come , dove S è il numero di simboli possibili, n il numero di simboli trasmessi. La naturale unità di misura dell'informazione era quindi la cifra decimale, rinominata più tardi hartley in suo onore. Alan Turing nel 1940 usò un'idea simile in una parte dell'analisi statistica sulla decifrazione dei codici crittografici Enigma usati dai tedeschi nella seconda guerra mondiale.

Gran parte della matematica che sta dietro alla teoria dell'informazione nel caso di eventi a diversa probabilità fu sviluppata nel campo della termodinamica da Ludwig Boltzmann e Willard Gibbs. I legami tra l'entropia definita in teoria dell'informazione e quella definita in termodinamica, compresi gli importanti contributi di Rolf Landauer degli anni '60, sono esplorati nell'opera Entropy in thermodynamics and information theory.

Nel rivoluzionario articolo di Shannon, questi per la prima volta introdusse i modelli quantitativi e qualitativi della comunicazione, pensata come un processo statistico, alla base della teoria dell'informazione. L'articolo si apre con l'affermazione che:

 "Il problema fondamentale della comunicazione è quello di riprodurre in un certo punto, o esattamente o approssimativamente, un messaggio selezionato in un altro punto."

Con esso nacquero le idee di:

 entropia e ridondanza di una sorgente e la sua importanza, mediante il teorema della codifica di sorgente;
 l'informazione mutua e la capacità di un canale rumoroso, compreso la promessa di una comunicazione senza perdite, mediante il teorema della codifica di canale;
 il risultato pratico del teorema di Shannon-Hartley per la capacità di un canale gaussiano;
 il bit, ossia un nuovo modo di intendere l'unità fondamentale dell'informazione.

Generalità 
I concetti principali alla base della teoria dell'informazione possono essere colti facendo riferimento ad un semplice esempio: il linguaggio umano. In genere, in un linguaggio, le parole più usate sono più corte di quelle meno usate. Ad esempio, "ciao" è più breve di "sostanzioso"; inoltre, anche se a volte non si riescono a cogliere tutte la parole di un discorso, il senso rimane chiaro. Lo scopo della teoria dell'informazione è proprio quello di fornire metodi per comprimere al massimo l'informazione prodotta da una sorgente eliminando tutta la ridondanza (si parla di codifica di sorgente), prima di aggiungere un certo livello di ridondanza in modo mirato, allo scopo di rendere la comunicazione (o l'archiviazione) più protetta dal rumore (si parla in questo caso di codifica di canale). 
Lo studio di questa teoria, i cui principi sono già presenti nelle forme di comunicazione umane, ha consentito a partire dagli anni '40 un eccezionale sviluppo della trasmissione e dell'archiviazione dell'informazione.

In generale, si considera come nascita della teoria dell'informazione la pubblicazione del lavoro "A Mathematical Theory of Communication" (Una teoria matematica della comunicazione) da parte di Claude Shannon; i risultati fondamentali presenti nello scritto sono due: l'enunciazione del Primo teorema di Shannon (o Teorema della codifica di sorgente), che stabilisce che, in media, il numero di bit necessari a rappresentare il risultato di un evento stocastico è pari alla sua entropia, fornendo così un limite superiore alla possibilità di comprimere dati; il secondo risultato, noto come Secondo teorema di Shannon o Teorema della codifica di canale, stabilisce invece che il massimo tasso di informazione trasferibile in modo affidabile su un canale affetto da rumore sta sotto una certa soglia che prende il nome di capacità di canale. La capacità può essere avvicinata a piacere, utilizzando sistemi di codifica e decodifica opportuni.

La teoria dell'informazione è strettamente legata ad una serie di discipline pure ed applicate che sono state studiate ed ingegnerizzate negli ultimi sessant'anni: sistemi adattivi, intelligenza artificiale, sistemi complessi, cibernetica, informatica, apprendimento automatico e molti altri. La teoria dell'informazione è quindi un'ampia ed approfondita teoria matematica, con applicazioni ugualmente ampie e profonde, il cui ambito principale rimane però la teoria dei codici.

La teoria dei codici riguarda lo studio di metodi pratici, chiamati codici, per aumentare l'efficienza di una trasmissione e ridurre la probabilità di errore il più possibile, nei limiti stabiliti e dimostrati da Shannon per un dato canale; questi codici possono essere divisi in tecniche di compressione dei dati (codifica di sorgente) e correzione d'errore (codifica di canale). Nel secondo caso, sono stati necessari molti anni prima che fosse possibile ottenere risultati vicini ai limiti forniti da Shannon. Una terza classe di codici sono gli algoritmi di crittografia. Concetti e metodi della teoria dell'informazione sono infatti utilizzati ampiamente in crittografia e crittoanalisi.

La teoria dell'informazione è oggi usata anche nella teoria dei giochi e nello studio dei mercati azionari, oltre che nella composizione musicale.

Grandezze dell'informazione 

La teoria dell'informazione è basata sulla teoria della probabilità e sulla statistica. Le principali grandezze dell'informazione sono l'entropia, ossia l'informazione contenuta in una variabile aleatoria, e l'informazione mutua, ossia la quantità di informazione in comune tra due variabili aleatorie. La prima indica quanto sia possibile comprimere un messaggio, mentre la seconda è utile per trovare il tasso di comunicazione possibile su un canale.

La scelta della base logaritmica usata nelle formule che seguono determina l'unità di misura usata per l'entropia. L'unità di misura più comune è senza dubbio il bit, che si usa nel caso in cui si scelga di utilizzare logaritmi in base 2. Altre unità di misura includono il nat, nel caso si usi il logaritmo naturale e l'hartley, che si basa sul logaritmo in base 10.

Nel seguito, un'espressione nella forma  è considerata per convenzione pari a 0 quando è nulla p. Questo è giustificabile con il fatto che  per qualunque base logaritmica.

Entropia 

Lentropia è una misura della quantità di informazione contenuta in un messaggio trasferito attraverso un canale di comunicazione.
Alternativamente può essere interpretata come misura di incertezza sul valore di un dato.
L'unità di misura tipica di questa grandezza è il Bit.

Le due interpretazioni sono duali.
Per esempio assumiamo di avere un dato la cui entropia è pari a  bit:

Se il valore del dato non è conosciuto allora è ragionevole interpretare l'entropia come misura di incertezza: ovvero il valore del dato potrebbe essere uno qualsiasi in un set di dimensione .

Per rimuovere completamente questa incertezza sarà necessario accertarsi del valore effettivo del dato, e cioè equivalentemente scegliere un singolo valore tra quelli possibili.
Questa operazione implica ricevere  bit di informazione.
Alternativamente si può dire che il valore esatto "trasporta" ( o "possiede", o "rappresenta" )  bit di informazione.

Velocità di trasmissione 

La velocità di trasmissione (o di trasferimento, detta anche frequenza di cifra o bit-rate) è la grandezza indicante la quantità di informazione trasferita attraverso un canale di comunicazione in un dato intervallo di tempo.
L'unità di misura associata è il bit per secondo.

Velocità di segnalazione 

La velocità di segnalazione, detta anche frequenza di simbolo, symbol rate o baud rate indica la quantità di variazione per unità di tempo dei simboli, della forma d'onda o in generale del segnale su un canale trasmissivo che utilizzi una modulazione o una codifica di linea. La velocità di segnalazione si misura in Baud (simboli al secondo).

Applicazioni

Capacità di canale 

Lo studio della comunicazione su un canale, come ad esempio un cavo Ethernet, è la motivazione prima della nascita della teoria dell'informazione. Come sa chiunque abbia usato un telefono, può accadere che il canale non sia in grado di trasportare il segnale senza "danneggiarlo"; distorsioni, echi o rumore sono solo alcuni esempi di corruzione di un segnale che portano ad un degrado nella qualità della comunicazione. La domanda che sorge spontanea è dunque quale sia il massimo tasso (o bitrate) a cui posso sperare di comunicare su un canale "rumoroso" (ossia che degrada la comunicazione)?

Consideriamo il processo di comunicare su un canale discreto. Un semplice modello del processo è mostrato in figura

Qui X rappresenta lo spazio dei messaggi trasmessi, ed Y lo spazio dei messaggi ricevuti durante un'unità di tempo sul nostro canale. Sia  la distribuzione di probabilità condizionata di Y data X. Considereremo  una proprietà del canale, che non cambia e che in sostanza rappresenta il rumore da cui è affetto il canale. Allora la distribuzione congiunta di X e Y è completamente determinata dal canale e dalla scelta di , ossia la distribuzione marginale del messaggio che decidiamo di inviare sul canale. Dati questi vincoli, desideriamo massimizzare la quantità di informazione, o il segnale, che vogliamo comunicare sul canale. La misura appropriata per questa quantità è l'informazione mutua e il massimo dell'informazione mutua è chiamato capacità di canale, che è data da:

Questa capacità ha la seguente proprietà, legata al tasso di informazione trasmesso R (dove R è solitamente in bit per simbolo). Per ogni tasso di informazione R < C ed errore di codifica ε > 0, per N grande abbastanza, esistono un codice di lunghezza N e tasso R ed un algoritmo di codifica tali che la massima probabilità di errore sia minore uguale a ε; in altre parole, è sempre possibile trasmettere con un tasso di errore basso a piacere. In più, per ogni tasso R > C, non è possibile trasmettere con un tasso di errore basso a piacere.

Teoria delle sorgenti 
Qualunque processo che generi messaggi successivi può essere considerato una sorgente di informazione. Una sorgente priva di memoria è una sorgente tale per cui ogni messaggio è una variabile aleatoria indipendente e identicamente distribuita, mentre le proprietà di ergodicità e stazionarietà impongono vincoli più restrittivi. Tutte queste sorgenti sono stocastiche.

Tasso 
Il tasso di informazione è l'entropia media per simbolo. Per le sorgenti senza memoria, questa è semplicemente l'entropia di ciascun simbolo, mentre, nel caso più generale

Precisamente, questa è l'entropia condizionale prevista per messaggio (vale a dire per unità di tempo) dati tutti i messaggi precedentemente generati. È comune nella teoria dell'informazione parlare di "tasso" o "entropia" di una lingua. Questo è appropriato, ad esempio, quando la fonte delle informazioni è la prosa inglese. La velocità di una sorgente senza memoria è semplicemente , poiché per definizione non esiste alcuna interdipendenza tra i messaggi successivi di una sorgente senza memoria. Il tasso di una fonte di informazioni è correlato alla sua ridondanza e a quanto bene può essere compresso.

Teoria dei codici 

La teoria dei codici è la più importante e diretta applicazione della teoria dell'informazione. Può essere suddivisa in codifica dei codici sorgenti e codifica di canale. Usando una descrizione statistica dei dati, la teoria dell'informazione quantifica il numero dei bit necessari a descrivere i dati, tale quantità è l'entropia informativa della sorgente.

 Compressione dati (codifica sorgente): ci sono due formulazioni per questo problema:
 compressione senza perdita, quando i dati devono essere ricostruiti in modo esatto
 compressione con perdita allocando i bit necessari a ricostruire i dati all'interno di un intervallo di fedeltà misurato dalla funzione di distorsione. Questo ramo della teoria dell'informazione è detto rate–distortion theory.

 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.

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. Comunque, questi teoremi valgono unicamente nella situazione in cui un utente che trasmette vuole comunicare ad un utente che riceve. In scenari con più di un mittente o più di un destinatario, la compressione seguita dalla trasmissione potrebbe non essere ottimale.

Usi da parte dei servizi segreti ed applicazioni alla sicurezza 
I concetti della teoria dell'informazione sono largamente usati in crittografia e criptoanalisi. Per un esempio storico interessante, vedere il deciban. Shannon stesso ha definito un concetto importante ora chiamato distanza di unicità. Basato sulla ridondanza del testo, cerca di dare la minima quantità di testo cifrato necessario ad assicurare una decifrabilità unica.

La teoria dell'informazione di Shannon è estremamente importante al lavoro, molto più di quanto il suo uso in crittografia indichi. I servizi segreti usano la teoria dell'informazione per mantenere segrete le informazioni riservate e per scoprire il numero massimo possibile di informazioni su di un avversario in un modo sicuro. Il teorema di Shannon-Hartley ci fa credere che mantenere dei segreti è molto più difficile di quanto si possa credere inizialmente. In generale, non è possibile fermare la fuoriuscita di informazioni riservate, ma solo rallentarla. Inoltre, al crescere delle persone che hanno accesso all'informazione ed al crescere del tempo che queste persone devono dedicare al lavoro ed alla revisione di tale informazione, cresce la ridondanza che tale informazione acquisisce. È estremamente difficile contenere il flusso di informazioni che hanno alta ridondanza. L'inevitabile fuoriuscita di informazioni riservate è dovuta al fatto psicologico che ciò che le persone sanno influenza il loro comportamento, anche in modo molto subdolo.

Generazione di numeri pseudo-casuali 
Un buon esempio di applicazione della teoria dell'informazione alle comunicazioni nascoste è la progettazione della codifica dei segnali del Sistema di Posizionamento Globale. Il sistema usa un generatore di numeri pseudocasuali che mette il segnale radio sotto la soglia del rumore. Quindi un ascoltatore radio non sarebbe nemmeno in grado di capire che c'è un segnale presente, perché rimarrebbe affogato da varie sorgenti di rumore (rumore atmosferico o di antenna). Comunque facendo l'integrale su un lungo periodo di tempo, usando la sequenza pseudorandomica "segreta" (ma nota al destinatario), è possibile rilevare il segnale e capirne le modulazioni. Nel sistema di posizionamento globale, il segnale C/A è stato pubblicato come sequenza di 1023 bit, ma la sequenza pseudorandomica usata nel P(Y) rimane segreta. La stessa tecnica può essere usata per trasmettere informazioni nascoste usando sistemi a breve raggio ed aventi bassissima potenza, senza che un nemico si accorga dell'esistenza del segnale radio. È analogo alla steganografia. Vedi anche comunicazioni spread spectrum.

Altre applicazioni 
La teoria dell'informazione ha applicazioni anche nei campi del gioco d'azzardo, della bioinformatica e della musica.

Note

Bibliografia

L'articolo classico

Altri articoli scientifici 
  C. E. Shannon, A Mathematical Theory of Cryptography, Memorandum MM 45-110-92, Bell Laboratories, settembre 1945
  R.V.L. Hartley, Transmission of Information, Bell System Technical Journal, luglio 1928
  J. L. Kelly, Jr., A New Interpretation of Information Rate, Bell System Technical Journal, Vol. 35, luglio 1956, pp. 917–26
  R. Landauer, Information is Physical, Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci. Press, Los Alamitos, 1993), pp. 1–4.
  R. Landauer, Irreversibility and Heat Generation in the Computing Process, IBM J. Res. Develop., Vol. 5, No. 3, 1961
  S. Verdù, 50 years of Shannon theory, IEEE Transactions on Information Theory, vol. 44 n.6, Ottobre 1998

Libri di testo 
 Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1949. ISBN 0-252-72548-4
 Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
 Thomas M. Cover, Joy A. Thomas. Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.
2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
 Fazlollah Reza. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
 Raymond W. Yeung. A First Course in Information Theory Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7
  David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

Altri libri 
  James Bamford, The Puzzle Palace, Penguin Books, 1983. ISBN 0-14-006748-5
  Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
  A. I. Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. ISBN 0-486-60434-9
  H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing, Princeton University Press, Princeton, NJ (1990). ISBN 0-691-08727-X
  Tom Siegfried, The Bit and the Pendulum, Wiley, 2000. ISBN 0-471-32174-5
  Charles Seife, Decoding The Universe, Viking, 2006. ISBN 0-670-03441-X
  E. M. Rogers, T. W. Valente, A History of information theory in communication research in: J. R. Schement, B. D. Ruben (a cura di), Information and behavior volume 4: Between communication and information, Transaction Publishers, New Brunswick (NJ), 1993.

Voci correlate

Applicazioni 
 Crittografia
 Crittoanalisi
 Gioco d'azzardo

Storia 
 Storia della teoria dell'informazione
 Claude Elwood Shannon
 Ralph Hartley
 Roberto Mario Fano
 Hubert Yockey

Teoria 
 Codifica di sorgente
 Teoria dell’informazione integrata
 Teoria della rivelazione 
 Teoria della stima
 Informazione di Fisher
 Complessità di Kolmogorov
 Codifica di rete

Concetti 
 Autoinformazione
 Entropia congiunta
 Entropia condizionale
 Canale (telecomunicazioni)
 Ricevitore (teoria dell'informazione)
 Informazione mutua
 Entropia differenziale
 Capacità di canale

Altri progetti

Collegamenti esterni 
 
 Gibbs, M., "Quantum Information Theory", Eprint
 Schneider, T., "Information Theory Primer", Eprint
 
 On-line textbook: Information Theory, Inference, and Learning Algorithms, by David MacKay - da un'introduzione piacevole e completa della teoria di Shannon, che include i metodi più recenti di codifica come i codici di parità a bassa densità e i Turbo codici