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 informazione su un canale di comunicazione.
È 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
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 (), 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 (), 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 è il numero di simboli possibili, 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:
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 le 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."Grandezze della forma [...] giocano un ruolo centrale nella teoria dell'informazione come misure di informazione, scelta e incertezza". (); Scelta ed incertezza sono misure equivalenti. 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", "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