Teoria dell'Informazione: sorgente discreta, entropia e codifica binaria

Teoria dell'Informazione

Lezione 4 marzo
Fin'ora abbiamo parlato e riparlato di "informazione" senza averne mai dato una definizione.
Infatti, mai lo faremo! (per tutta una serie di motivi ... )
Uno di questi, 'e che il concetto di "informazione" `è dipendente dall'osservatore nel senso che una "cosa" può rappresentare informazione per qualcuno, ma non per altri.
Assumiamo quindi che vi sia un dispositivo/fenomeno che emetta qualcosa e che vi sia un osservatore che sia interessato a tali emissioni, ovvero che le consideri informazione.
Esempio: il dispositivo potrei essere io e gli osservatori potreste essere voi!
l dispositivo/fenomeno che emette viene chiamato sorgente (di informazione) che emette simboli di un insieme X che chiameremo alfabeto sorgente.
Esempio: se la sorgente fossi io, allora X = {a, b, c, . . . , z}
Esempio: se la sorgente fosse un musicista, allora X = {do, re, mi, fa, sol, la, si, }

Descrizione Formale di una Sorgente

Come dare una descrizione formale di una sorgente?
Ovvero, come descrivere le regole con cui la sorgente emette i simboli dell'alfabeto sorgente X?
La descrizione deve essere necessariamente di tipo probabilistico, vale a dire il massimo che possiamo "fare" è dare le probabilità con cui la sorgente può emettere i vari simboli x E X.
E perché non possiamo dare una descrizione deterministica della sorgente, ovvero una regola, algoritmo, una funzione ... che ci permette di calcolare, ad ogni istante, con certezza ciò che la sorgente emette/emetterà?
Supponiamo che lo si possa fare e che la sorgente sia io.
Ciò vuol dire che avete un algoritmo/funzione che vi permette di calcolare ciò che io dirò, (con certezza) ad ogni istante.
E allora perché mi state ascoltando? Potreste eseguire l'algoritmo/calcolare la funzione e sapere ciò che io dirò, senza aver bisogno di prendere l'autobus per venire all'università ...
In altri termini, se voi avete un algoritmo/funzione che vi permette di calcolare ciò che io dirò, tutto quello che io in effetti dirò non vi dice nulla di più che già non sapete, ovvero, tutto quello che io in dirò non vi dà nessuna informazione aggiuntiva!
Conclusione: possiamo ricevere informazione da un sorgente solo se abbiamo incertezza su quello che la sorgente può emettere.Possiamo quindi dire che l'informazione è conseguenza ad uno stato preliminare di incertezza.
Ovverosia, l'informazione `e ciò che non si sa a priori e che ci permette di passare da uno stato di incertezza (ignoranza) ad uno stato di non incertezza (di conoscenza).
Abbiamo prima osservato che non abbiamo alcuna incertezza apriori su fenomeni (sorgenti) la cui descrizione `e deterministica, (e quindi non otteniamo informazione dalla osservazione del loro comportamento) siamo quindi naturalmente portati a considerare solo sorgenti la cui descrizione 'e probabilistica, perché solo per esse siamo incerti sulle loro future emissioni (e quindi certamente che otteniamo informazione dalla osservazione del loro comportamento).

Sorgente di Informazione Discreta

QUINDI
Per i nostri scopi, una sorgente di informazione 'e una sequenza di variabili casuali X1, X2, ... , Xi , ... le quali assumono valori in un di un insieme finito X (che chiameremo alfabeto sorgente).
Il valore assunto dalla generica v.c. Xi rappresenta la emissione della sorgente al tempo i.
Assunzione simplificatrice: le variabili casuali X; siano indipendenti, ovvero che Vk ≥ 1 e Vx1, X2, . . . , Xk € X vale che
Pr{X1 = x1, X2= X2, ... , Xk =Xk} =
k
i=1
IPr{Xi=xi},
In più, assumeremo che tutte le X; abbiano la stessa distribuzione P, ovvero la probabilità di emettere un generico simbolo x al tempo i dipende solo da x e non dall'istante i:
Vx E Xi e Vi ≥ 1 vale che Pr{Xi=x} = P(x).
In gergo, la sorgente X1, X2, ... , Xi, ... in cui le Xi sono tra di loro indipendenti e hanno tutte la stessa distribuzione
P = {P(x1), ... , P(xm)} (dove abbiamo assunto che X = {x1, ... Xm}) viene chiamata sorgente discreta, stazionaria e senza memoria.
In queste ipotesi, useremo la seguente notazione per descrivere la sorgente:
X =
X1
X2
...
Xm
P(x1) P(x2)
...
P(Xm)

Codifica e Decodifica

Lezione 5 marzo
PRIMO PROBLEMA
Data una sorgente di informazione con alfabeto sorgente
X = {x1, ... , Xm}, e descritta dalla vc.
X =
×1
×2
...
Xm
P(x1) P(x2)
P(Xm)
Come rappresentare "l'informazione" emessa dalla sorgente X nella maniera più compatta possibile?
Per precisare il termine compatta, introduciamo il concetto di codifica e decodifica.
?
Codifica: una funzione c: x E X k 7-> c(x) E {0, 1} ^ n dove {0, 1} ^n =insieme di tutte le 2^n sequenze binarie di lunghezza n.
c(x) è la rappresentazione della sequenza sorgente x, ovvero la codifica di x.
·Perché codifiche c: x E X k 7-> c(x) = {0, 1} n binarie?
Non cambierebbe molto se considerassimo codifiche c: x E X^K-> c(x) = {y1, y2, . . . } ^ n
?
Dal punto di vista pratico, sono quelle più usate (d'altra parte, tutto è rappresentabile in binario)
?
Decodifica: d: y E {0, 1} ^n-> d(y) E X^ k
d(y) è la sequenza sorgente x E X^ k che "pensiamo" sia stata codificata con y E {0, 1} ^n
Quali proprietà richiediamo alle funzioni c e d?
Ragionevoli proprietà potrebbero essere queste: Vogliamo una funzione di codifica c: X^k -> {0, 1}^n ed una funzione di decodifica d : {0, 1}^ n -> X^ k che abbiano le seguenti caratteristiche
i)
n sia il più piccolo possibile (e quindi il rapporto n/k pari al numero di bits usati per ogni lettera sorgente sia il più piccolo possibile) Perché? Ricordiamo che vogliamo rappresentare le sequenze x E X^ k emessa dalla sorgente X nella maniera più "compatta" possibile, ovvero utilizzando il minimo numero di bit possibili.
ii)
ii) per ogni x E X ^k valga d(c(x)) = x Perché? Perché vorremmo, dalla codifica c(x) di ogni sequenza sorgente x poter risalire ad x.Conseguenze di "per ogni x E Xk valga d(c(x) = x"
In altri termini, vogliamo che la codifica c : x € Xk 1} c(x) € {0,1}" sia invertibile. Ciò comporta che Vx, x' € Xk, x #x'=>c(x) =c(x'), e quindi
{0, 1}"] = 2" > |X | = |X|k => log 2" = n ≥ log | X|k = klog | X| => log2 | X|
ovvero dobbiamo usare un numero di bit per simbolo sorgente n/k almeno pari a log |X|.
Non è una buona idea!
Conclusione: La proprietà che avevamo richiesto: per ogni x E X k valga d(c(x)) = x 'e troppo forte perché ci costringe a predisporre codifiche anche per sequenze in X^k che mai verranno emesse.
Quali proprietà allora richiediamo alle funzioni c e d!
Volevamo una funzione di codifica c : Xk -> {0,1}" ed una funzione di decodifica d : {0,1}" > Xk che avessero le seguenti caratteristiche
i) n sia il più piccolo possibile (e quindi il rapporto n/k pari al numero di bits usati per ogni lettera sorgente sia il più piccolo possibile)
ii') Pr{x : x E Xk e per cui valga d(c(x) { x} < E con E "molto piccolo".
In termini pratici, è come se ammettessimo un errore di decodifica solo se la sorgente emetta zzzz ... z o altre sequenze molto improbabili!
Vedremo che la nuova proprietà ii') ci permetterà di migliorare il risultato precedente, secondo il quale il minimo numero di bits per simbolo sorgente che dovevamo usare era log |X| (nel senso che potremo usare meno bits per simbolo sorgente
Prima di vederlo, osserviamo che le due proprietà
ii) per ogni x € Xk valga d(c(x)) = x
=> Pr{x : x € Xk e per cui valga d(c(x)) #x} = 0
ii') Pr{x : x E Xk e per cui valga d(c(x) { x} < E con E "molto piccolo"
sono "'equivalenti" dal punto di vista pratico (in un certo senso ... )

Probabilità di Errore e Compressione

Quindi, il nostro problema adesso è:
Date funzioni di codifica c: X^k -> {0, 1} n e decodifica d : {0, 1} ^n -> X^ k , e sorgente X, denotiamo con e (d, c) la quantità
e (d, c) = Pr{x : x E X k e per cui valga d(c(x)) = x}
e (d, c) è la probabilità che la sorgente emetta una qualche sequenza su cui le nostre regole di codifica e decodifica sbagliano. Chiameremo quindi e (d, c) la probabilità di errore dello schema di codifica/decodifica.
Fissati k =lunghezza delle sequenze sorgenti che vogliamo codificare, e € =probabilità di errore che vogliamo tollerare, poniamo n (k, E) =al più piccolo valore di n per cui possiamo trovare una funzione di codifica c: X^k -> {0, 1}^ n ed una funzione di decodifica d : {0, 1} n -> X k che abbiano e(d, c) ≤ E. Vogliamo determinare il valore n(k, E)/k quando k è "molto grande".
Perchè vogliamo determinare il valore n(k, €)/k?
Ricordiamo
n(k, E) =al più piccolo valore di n per cui possiamo trovare una funzione di codifica c : Xk -> {0,1}" ed una funzione di decodifica d : {0, 1}" > Xk che abbiano e(d, c) ≤ €
Quindi n(k, E)/k ci dice qual è il minimo numero di bits per simbolo sorgente che ci servono per codificare la sorgente se siamo disposti a tollerare una probabilità di ricostruzione errata < E.
In altre parole, n(k, €) è la massima compressione (misurata in bit) che possiamo effettuare delle sequenze x € Xk, se siamo disposti a accettare una probabilità di decodifica errata ≤ E.
E perchè vogliamo calcolare il rapporto n(k, E)/k, per k -> co?
Vale il fondamentale risultato
Teorema
Per una generica sorgente discreta, stazionaria e senza memoria
X =
X1
P(x1) P(x2)
X2
...
...
Xm
P(Xm)
vale che
lim
n(k, €)
k
n
P(x;) log
1
P ( Xi )
i=1
Denoteremo la quantità Ei-1 P(xi) log P(x) con H(P) e e la chiameremo entropia della sorgente X (ovvero, ed è la stessa cosa, della variabile casuale X con distribuzione
P= {P(x1), ... , P(xm)}).

Entropia della Sorgente

Osservazioni sull'Entropia

Osservazioni
Che succede se la sorgente non è discreta, stazionaria e senza memoria?
Si può ottenere un risultato simile, solo che i conti sono molto più complicati ...
L'aspetto importante è che si riesce a valutare la quantità di interesse pratico
n(k, E) =al più piccolo valore di n per cui possiamo trovare una funzione di codifica c : Xk > {0,1}" ed una funzione di decodifica d : {0,1}" > Xk che abbiano e(d, c) ≤ E
mediante la semplice espressione aritmetica
n
~k
1
P(Xi) log P(Xi)
i=1

Funzione di Codifica e Decodifica

Osservazione
L'esistenza di una funzione di codifica c : Xk -> {0,1}" e decodifica d : {0,1}" > Xk che abbiano probabilità di errore e(d, c) ≤ € è equivalente a trovare un sottoinsieme A c Xk di sequenze di lunghezza k tale che
Pr(A) =
Pr(x) ≥1 -€ e
|A| < 2".
(1)
x€A
Fissati k e o > 0, calcoliamo H(P) = >; P(x;) log(1/P(x;)) e
B(k, 8) = {x E XK : 2-k(H(P)+8) < P(x) ≤ 2-k(H(P)-8)}
(2)
Per l'insieme B(k, 8) valgono le seguenti uguaglianze
B(k,8) = {x € Xk : - k(H(P) + 8) ≤ log P(x) ≤-k(H(P) - 8)}
= {x E X" : k(H(P) + 8) ≥ log P(x)
1
> k(H(P) - 8)}
(poichè log = = - log x)
= { x E X* : k(H(P) + 8) ≥ log
1
II$=1 P(xi)
k
(poichè P(x) = I | P(x;))
i=1
> k(H(P) - 8)}
={xEXª : k(H(P)+8) ≥
i=1
k
10g P ( xi)
1
≥ K(H(P) - 8)}