Teoria dell'informazione

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Teoria dell'Informazione)
Il satellite artificiale Skylab rappresenta una delle applicazioni della teoria dell'informazione

La teoria dell'informazione è una disciplina della fisica applicata che ha come scopo la quantificazione della quantità di dati (ossia di informazione), con lo scopo di essere di in grado di salvarli o di trasmetterli su un canale in modo affidabile. 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 includono la compressione senza perdite dei file (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, la statistica, la fisica, 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.

Panoramica[modifica | modifica sorgente]

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 uno sviluppo incredibile 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 della codifica.

La teoria della codifica 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 degli errori (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.

Ambientazione Storica[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Storia della teoria dell'informazione.

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 state 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 Fattorie 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 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 (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 H = \log S^n = 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 Touring 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.

Ludwig Boltzmann nel 1875

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, comresi 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 findamentale 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

Quantità della teoria dell'informazione[modifica | modifica sorgente]

la teoria dell'informazione è basata sulla teoria della probabilità e sulla statistica. Le principali quantità 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 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[modifica | modifica sorgente]

Entropia di una variabile di Bernoulli

in funzione della probabilità di successo, spesso indicata come entropia binaria, H_\mbox{b}(p). L'entropia è massima e vale 1 bit, quando la probabilità di successo è 0.5, come nel caso del lancio di una moneta.]]

L' entropia, H, di una variabile aleatoria discreta X, è la misura della quantità di incertezza associata al valore di X.

Supponiamo di trasmettere 1000 bit (0 e 1). Se questi bit sono noti prima della trasmissione (ossia assumono un certo valore con probabilità 1), la logica impone che non sia stata trasmessa informazione. Al contrario, se ogni bit è indipendente dagli altri e ha uguale probabilità di valere 0 o 1, sono stati inviati (nel senso della teoria dell'informazione) 1000 bit. Tra questi due estremi, la quantità di informazione può essere quantificata come segue. Se \mathbb{X}\, è l'insieme di tutti i valori x che la variabile X può assumere e p(x)=Pr(X=x) è la brobabilità che X valga x, allora X ha

 H(X) = \mathbb{E}_{X} [I(x)] = -\sum_{x \in \mathbb{X}} p(x) \log p(x)

bit di entropia (Qui,I(x) è l'autoinformazione, ossia il contributo di entropia legato ad ogni singolo messaggio). Una importante proprietà dell'entropia è che è massima quando tutti i messaggi nello spazio dei possibili messaggi sono equiprobabili, ossia maggiormente impredicibili. In questo caso H(X) = \log |\mathbb{X}|.

Il caso speciale di una variabile casuale con due possibili uscite è l' entropia binaria:

H_\mbox{b}(p) = - p \log p - (1-p)\log (1-p).\,

Entropia congiunta[modifica | modifica sorgente]

L'entropia congiunta di due variabili aleatorie discrete X ed Y è semplicemente l'entropia della coppia : (X, Y). Questo implica che, se X e Y sono indipendenti ,allora la loro entropia congiunta è la somma delle loro entropie individuali.

Per esempio, se (X,Y) rappresenta la posizione di un pezzo di scacchi (X la riga ed Y la colonna), allora l'entropia congiunta della riga e della colonna su cui è posto il pezzo sarà l'entropia della posizione del pezzo.

H(X, Y) = \mathbb{E}_{X,Y} [-\log p(x,y)] = - \sum_{x, y} p(x, y) \log p(x, y) \,


Nonostante la notazione simile, l'entropia congiunta non deve essere confusa con l' entropia incrociata.

Entropia condizionale[modifica | modifica sorgente]

L' entropia condizionale di una variabile aleatoria X , data la variabile aleatoria Y è

 H(X|Y) = \mathbb E_Y [H(X|y)] = -\sum_{y \in Y} p(y) \sum_{x \in X} p(x|y) \log p(x|y) = \sum_{x,y} p(x,y) \log \frac{p(y)}{p(x,y)}.

The conditional entropy of X given random variable Y (also called the equivocation of X about Y) is the average conditional entropy over Y:

Una proprietà fondamentale dell'entropia condizionata è che:

 H(X|Y) = H(X,Y) - H(Y) .\,

Informazione mutua[modifica | modifica sorgente]

L' Informazione mutua misura la quantità di informazione su una variabile aleatoria che può essere ricavata osservandone un'altra. In un sistema di comunicazione è importante che sia massimizzata la quantità di informazione condivisa dai segnali inviati e ricevuti. L'informazione mutua di X, relativamente a Y è:

I(X;Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)\, p(y)}

Un'importante proprietà dell'informazione mutua è che

I(X;Y) = H(X) - H(X|Y).\,

Ossia, conoscendo Y, possiamo risparmiare in media I(X; Y) bit nella codificsa di X, rispetto al caso in cui Y è ingota.

L'informazione mutua è simmetrica;

I(X;Y) = I(Y;X) = H(X) + H(Y) - H(X,Y).\,

L'informazione mutua può essere espressa come media della divergenza di Kullback–Leibler della probabilità a posteriori di X, dato il valore di Y, rispetto alla [[probabilità a priori di X:

I(X;Y) = \mathbb E_{p(y)} [D_{\mathrm{KL}}( p(X|Y=y) \| p(X) )].

In altre parole, essa misura quanto, in media, al probabilità della distribuzione X cambia se conosciamo il valore di Y. Questo è spesso calcolato come divergenza dal prodotto delle sitribuzioni marginali rispetto alla vera distribuzione congiunta:

I(X; Y) = D_{\mathrm{KL}}(p(X,Y) \| p(X)p(Y)).

L'informazione mutua può essere considerata una statistica per stabilire l'indipendenza tra una coppia di variabili ed ha una distribuzione asintotica ben specificata.

Divergenza di Kullback–Leibler[modifica | modifica sorgente]

La Divergenza di Kullback–Leibler (o entropia relativa) è un modo per confrontare due distribuzioni: una "vera" distribuzione di probabilità p(X) ed una distribuzione arbitraria q(X). Se comprimiamo dei dati in un qualche modo, per cui q(x) è la distribuzione seguita ddai dati compressi, quando in realtà la distribuzione dei dati è p(x), la divergenza di Kullback–Leibler è il numero di bit addizionali medi per dato necessari alla compressione. È quindi definita come

D_{\mathrm{KL}}(p(X) \| q(X)) = \sum_{x \in X} -p(x) \log {q(x)} \, - \, \left( -p(x) \log {p(x)}\right) = \sum_{x \in X} p(x) \log \frac{p(x)}{q(x)}.

Nonostante sia in alcuni casi usata come una metrica per la "distanza", essa non è una vera metrica, poiché non è simmetrica.

Applicazioni[modifica | modifica sorgente]

Capacità di canale[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Teorema della codifica 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

Sistema di comunicazione.png


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 muta è 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 possinile 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[modifica | modifica sorgente]

Quanlunque 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[modifica | modifica sorgente]

Information rate is the average entropy per symbol. For memoryless sources, this is merely the entropy of each symbol, while, in the most general case, it is

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

Precisely speaking, this is the expected conditional entropy per message (i.e. per unit time) given all the previous messages generated. It is common in information theory to speak of the "rate" or "entropy" of a language. This is appropriate, for example, when the source of information is English prose. The rate of a memoryless source is simply H(M), since by definition there is no interdependence of the successive messages of a memoryless source. The rate of a source of information is related to its redundancy and how well it can be compressed.

Teoria dei codici[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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[modifica | modifica sorgente]

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 dell persone hanno accesso all'informazione ed al crescere del tempo che queste persone devono dedicare al lavoro ed alla revisione di tale informazione, maggiore è 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.

Genereazione di numeri pseudo-casuali[modifica | modifica sorgente]

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 ci fosse 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 pubblicamente come sequenza di 1023 bit, ma la sequenza pseudorandomica usata nel P(Y) rimane segreta. La stessa tecnica può essere usata per trasmettere informazioni nasconte 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[modifica | modifica sorgente]

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

Bibliografia[modifica | modifica sorgente]

L'articolo classico[modifica | modifica sorgente]

Altri articoli scientifici[modifica | modifica sorgente]

Libri di testo[modifica | modifica sorgente]

2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.

Altri libri[modifica | modifica sorgente]

  • (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

Voci correlate[modifica | modifica sorgente]

Applicazioni[modifica | modifica sorgente]

Storia[modifica | modifica sorgente]

Teoria[modifica | modifica sorgente]

Concetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica