Teoria dell'informazione

La teoria dell'informazione è una teoria matematica che offre una definizione quantitativa del concetto di informazione, oltre che gli strumenti matematici essenziali per permettere l'analisi dei fenomeni relativi alla misurazione e alla trasmissione di informazioni su un canale di comunicazione.

Claude Elwood Shannon, ingegnere e matematico statunitense che nel 1948 fondò la teoria dell'informazione.

È comune attribuire la paternità della teoria a Claude Shannon, che la formalizzò nel 1948 pubblicando l'articolo scientifico "A Mathematical Theory of Communication".

La teoria dell'informazione ha avuto e continua ad avere un'importanza fondamentale in moltissimi ambiti. Applicazioni notevoli dei concetti della teoria includono: la compressione dei dati e le modulazioni digitali. Il suo contributo ha reso possibile missioni spaziali, l'invenzione del CD, dei telefonini, di Internet, lo studio di nuovi fenomeni linguistici e innumerevoli altre cose.

Storia

Josiah Willard Gibbs

Ludwig Boltzmann

Alan Turing

Ralph Hartley

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 (lett. "Alcuni fattori che influenzano la velocità del telegrafo" in italiano), 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 $W=K\log m$, 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 (lett. "Trasmissione dell'informazione" in italiano), 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 $H=n\log S$, 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»

(Claude Elwood Shannon, A Mathematical Theory of Communication, p. 1)

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 $p\log p\,$ è considerata per convenzione pari a 0 quando è nulla p. Questo è giustificabile con il fatto che $\lim _{p\rightarrow 0+}p\log p=0$ per qualunque base logaritmica.

Entropia

Il lancio di una moneta: un tipo di evento il cui esito può essere descritto con un singolo bit di informazione (entropia)

L'entropia è 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 $n$ 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 $2^{n}$.

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 $n$ bit di informazione. Alternativamente si può dire che il valore esatto "trasporta" ( o "possiede", o "rappresenta" ) $n$ bit di informazione.

Velocità di trasmissione

Tipica interfaccia di un misuratore di velocità per connessioni internet

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

Uno stesso segnale digitale interpretato dal punto di vista dei simboli (Data) e poi dei bit trasmessi (Manchester) rispetto ad un segnale di riferimento (Clock)

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 $p(y|x)$ la distribuzione di probabilità condizionata di Y data X. Considereremo $p(y|x)$ 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 $f(x)$, 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:

$C=\max _{f}I(X;Y).\!$

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

$r=\mathbb {E} H(M_{t}|M_{t-1},M_{t-2},M_{t-3},\ldots ).$

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 $H(M)$, 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:

1. compressione senza perdita, quando i dati devono essere ricostruiti in modo esatto
2. 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.

Bibliografia

L'articolo classico

• (EN) Claude Elwood Shannon, A mathematical theory of communication, in ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, n. 1, New York (NY, USA), Association for Computing Machinery, 1º gennaio 2001 [prima pubblicazione 1948], DOI:10.1145/584091.584093, ISSN 1559-1662.

Altri articoli scientifici

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

Libri di testo

• (EN) Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1949. ISBN 0-252-72548-4
• (EN) Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
• (EN) 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.

• (EN) Fazlollah Reza. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
• (EN) Raymond W. Yeung. A First Course in Information Theory Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7
• (EN) David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

Altri libri

• (EN) James Bamford, The Puzzle Palace, Penguin Books, 1983. ISBN 0-14-006748-5
• (EN) Leon Brillouin, Science and Information Theory, Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
• (EN) A. I. Khinchin, Mathematical Foundations of Information Theory, New York: Dover, 1957. ISBN 0-486-60434-9
• (EN) 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
• (EN) Tom Siegfried, The Bit and the Pendulum, Wiley, 2000. ISBN 0-471-32174-5
• (EN) Charles Seife, Decoding The Universe, Viking, 2006. ISBN 0-670-03441-X
• (EN) 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

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla teoria dell'informazione

Collegamenti esterni

• Enzo Cambi e *, INFORMAZIONE, Teoria della, in Enciclopedia Italiana, III Appendice, Istituto dell'Enciclopedia Italiana, 1961.
• informazióne, teorìa dell'-, su sapere.it, De Agostini.
• informazione, teoria della, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) George Markowsky, information theory, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Information Theory, su The Encyclopedia of Science Fiction.
• (EN) Eric W. Weisstein, Information Theory, su MathWorld, Wolfram Research.
• (EN) Gibbs, M., "Quantum Information Theory", Eprint
• (EN) Schneider, T., "Information Theory Primer", Eprint
• (EN) IEEE Information Theory Society, su itsoc.org. URL consultato il 29 gennaio 2014 (archiviato dall'url originale il 22 gennaio 2009).
• (EN) 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