Teoria dell'Informazione - La misura dell'informazione


"L'informatica non riguarda i computer più di quanto l'astronomia riguardi i telescopi."

                               Edsger Wybe Dijkstra

In ogni processo comunicativo esistono due modi mediante i quali si può valutare le informazioni che ci sono pervenute: si può effettuare una valutazione qualitativa o quantitativa.
  
La valutazione qualitativa è di tipo soggettivo e la effettuiamo ogni volta che per esempio giudichiamo le notizie che abbiamo ascoltato al telegiornale o che abbiamo sentito alla radio. In questo caso classificheremo le informazioni in buone notizie  o cattive in base ai nostri gusti personali e alle nostre aspettative.

La valutazione quantitativa delle informazioni è invece una forma di valutazione oggettiva, che ha una rilevante importanza in ambito scientifico, per esempio nella progettazione di sistemi di comunicazione.

    Innanzitutto è necessario stabilire la definizione di informazione: si dice informazione relativa a un evento tutto ciò che contribuisce ad aumentare le conoscenze riguardanti l’evento stesso.

   Per esempio, immaginiamo di aver perso il nostro gatto e di mostrare la sua foto ad alcune persone sperando che qualcuno sappia fornirci indicazioni per trovarlo. Se il nostro gatto è un comune gatto nero senza segni particolari, noi, descrivendolo, non forniamo ai nostri interlocutori informazioni di grande importanza, perché esistono moltissimi gatti identici al nostro e sarebbe quindi molto difficile identificarlo con sicurezza.  Se invece il nostro gatto era un po’ particolare, diciamo a strisce nero azzurre, noi, comunicando questo inusuale particolare, stiamo fornendo un’informazione estremamente importante, perché il nostro potrebbe essere l’unico gatto al mondo di questo colore e quindi è decisamente più facile identificarlo.

    Da questo surreale esempio si deduce quindi che la quantità di informazione dovuta a un evento (colore del gatto) è inversamente proporzionale alla probabilità che ha l’evento di verificarsi. Dire solo che il gatto è nero non è un’informazione cruciale per il ritrovamento del gatto, proprio perché è molto comune che esistano gatti di questo colore. Se il gatto ha un segno particolare, che lo differenzia da ogni altro gatto, questa informazione è estremamente importante, perché la probabilità che esistano gatti simili è molto vicina a zero.
    Questa relazione può essere scritta matematicamente come:
    

Q(x) =   1 / p(x)  =  p(x) -1


Cioè, la quantità di informazione dovuta all’evento x è tanto maggiore quanto è minore la probabilità che x sia verificato (p(x)).

Questa stessa relazione è valida anche in ambito informatico, con alcuni piccoli accorgimenti. Innanzitutto non parleremo più di eventi ma di simboli discreti (caratteri, tanto per intenderci). Per cui la stessa formula di prima sarà valida: la quantità Q(x) di informazione dovuta a un generico simbolo x è inversamente proporzionale alla probabilità che ha il carattere x di essere trasmesso.
   Un altro accorgimento da prendere è dovuto alla codifica dei caratteri: in ambito informatico ogni simbolo viene codificato in binario, per cui la quantità di informazione dovrà avere il bit come unità di misura.
  
   Una delle prime considerazioni che si possono fare è che la quantità di informazione dovuta a un messaggio è uguale alla sommatoria delle quantità di informazione dovute ai singoli caratteri trasmessi.
  Questa considerazione si può esprimere come:

Q(xi) = log[ p(xi)-1] = -log( p(xi) )
        
In questo modo misuriamo la quantità di informazione dovuta al simbolo xi  .

Dato che in abito informatico dobbiamo lavorare con i bit, perché ogni carattere è codificato come una serie di 0 e 1, in questo caso la base del logaritmo sarà quella binaria.
   Vediamo ora un esempio al riguardo: immaginiamo una sorgente in grado di emettere 3 simboli, x1, x2, x3, che hanno una probabilità di essere trasmessi rispettivamente di 0,5 , 0,25 e 0,25.
  
Possiamo quindi scrivere:

p(x1) = 0,5        p(x2) = 0,25        p(x3) = 0,25

Misuriamo ora la quantità di informazione dei singoli caratteri:

Q(x1) = -log2 0,5 = 1 bit
Q(x2) = -log2 0,25 = 2 bit
Q(x3) = -log2 0,25 = 2 bit

La quantità di informazione contenuta nel messaggio sarà quindi pari alla somma delle quantità di informazione dovute ai singoli caratteri:

  3
  ∑ Q(xi) = Q(x1) + Q(x2) + Q(x3) =5 bit
i = 1

A questo punto possiamo anche valutare la quantità di informazione media emessa dalla sorgente in questione. In matematica questo valore viene detto entropia della sorgente,  e viene indicato con la lettera H.

                                                                                              n                      n
H = ∑ p(xi) * Q(xi) = -∑ p(xi) * log2 p(xi)
i = 1                  i = 1

Questa formula significa semplicemente che l’entropia, cioè la quantità media di informazione emessa dalla sorgente (H), è pari alla sommatoria dei prodotti tra la probabilità che ha il simbolo (xi) di essere trasmesso e la quantità di informazione dovuta al simbolo stesso.
    Applicando molto semplicemente le proprietà dei logaritmi alla formula con cui si ricava H, si deduce che se tutti gli n simboli trasmessi dalla sorgente avessero la stessa probabilità  p(xi) = 1 /n = n–1  la formula diventerebbe H = log n

Se p(xi) = 1/n  = n^–1
    n                  n                                                                  
H = ∑ p(xi) * Q(xi) = -∑ 1 / n * log2 n  =
  i = 1              i = 1      
            
= -n *   1 / n   * log2 n  = - log2 n


A questo punto si può notare proprio che abbiamo ottenuto esattamente la formula che indica il numero di bit necessari a rappresentare n simboli, quindi, quando i caratteri trasmessi dalla sorgente hanno tutti la stessa probabilità, la quantità media di informazione della sorgente è pari al numero di bit necessari a rappresentare tutti i caratteri trasmissibili.

   L’ultima nota riguardante questo concetto è dovuta all’approssimazione: il logaritmo in base 2 di n darà come risultato un intero solo se n è una potenza di 2. In caso contrario, è necessario approssimare il risultato ottenuto al più vicino intero superiore.


    La conoscenza dell’entropia della sorgente risulta utile per analizzare e rendere ottimali i codici usati per la trasmissione di dati. Dovremo ora introdurre un nuovo concetto, quello di lunghezza media delle parole.
  Già intuitivamente si deduce che una codifica è tanto più efficiente quanto più corte sono le sue parole, in quanto richiedono minor tempo di trasmissione e una minor mole di dati da spedire.  Da qui in avanti chiameremo li la lunghezza di una delle parole in una determinata codifica. Questo numero esprimerà quindi il numero di bit da cui è composta una parola.
   La lunghezza media delle parole, indicata matematicamente con il simbolo L è quindi pari alla sommatoria della probabilità del simbolo xi di essere trasmesso moltiplicato per la lunghezza della parola li.
   n                                            
L =∑ p(xi) * li                                                                              
  i = 1

Ora che abbiamo definito sia l’entropia della sorgente che la lunghezza media della parole di una codifica, possiamo finalmente stabilire l’efficienza di una codifica basandoci sul primo teorema di Shannon, che afferma che per ogni sorgente in grado di trasmettere n simboli esiste almeno una codifica tale per cui

H ≤ L

Tradotto in lingua italiana, l’entropia della sorgente sarà sempre minore della lunghezza del codice necessario a rappresentare tutti i simboli di una sorgente.

Appurata questa considerazione, l’efficienza di una codifica (eta) può essere calcolata come il rapporto tra l’entropia della sorgente e la lunghezza media del codice:


η =   H / L
La codifica migliore, quella più efficiente, si ottiene quando η si avvicina a 1.
La codifica è ottimale per   η →  1

Segnalazione errori e commenti at  <eddiewrc@aliceposta.it>