Compressione dati
Sommario
- Modello della sorgente di informazione.
- Misura dell’informazione: entropia di una variabile aleatoria.
- Entropia di una sorgente di informazione.
- Entropia condizionale.
Modello della sorgente di informazione
Esempi di sorgenti di informazione
- Sistema di audio diffusione: segnale vocale.
- Sistema di video diffusione: segnale video.
- Sistema di trasmissione fax: immagine fissa monocromatica.
- Sistema di comunicazione tra computer: sequenza di caratteri ASCII o sequenza di simboli binari.
Modello della sorgente di informazione
Sorgente numerica
- E’ una sorgente che emette simboli appartenenti ad un alfabeto discreto e finito (N simboli) con una certa cadenza (ogni T secondi).
- Una sorgente numerica può essere modellata come un segnale aleatorio a tempo discreto cioè una sequenza di variabili aleatorie.
Modello della sorgente di informazione
Esempio: Sorgente binaria senza memoria
- La sorgente emette simboli appartenenti all’insieme {0,1} statisticamente indipendenti ogni T secondi.
- La sequenza delle v.a. Xi è i.i.d. (indipendenti e identicamente distribuite) _ Sorgente discreta senza memoria e stazionaria (DMS).
Sorgente binaria senza memoria
Modello della sorgente di informazione
Caratterizzare la sequenza Xi emmessa dalla sorgente binaria è semplice:
- Si assegnano le probabilità:
- Pr(Xi=1) Δp
- Pr(Xi=1) = 1-p
- La probabilità che la sorgente emetta un arbitrario blocco di simboli nell’intervallo kT si calcola sfruttando la statistica indipendenza
- Detto m il numero degli “1″ si ha:
- Pr(X1 …… Xk) = pm(1-p)k-m
Esempio: Pr (010110100) = p4(1-p)5
Assegnato p la sorgente è completamente caratterizzata statisticamente.
Esempio di codifica di sorgente
- Sia S una sorgente binaria senza memoria (BMS) che emette simboli “1″ e “0″ con p = 3/4.
- Se non effettuiamo alcuna codifica, per memorizzare una sequenza di 10.000 simboli sarà necessaria una memoria M di 10.000 locazioni binarie.
- Usiamo il codice binario in immagine (li = lunghezza iesima parola codice).
Esempio di codifica di sorgente
Esempio di codifica di sorgente
Essendo 8450 < 10.000, abbiamo ottenuto un risparmio per rappresentare la nostra informazione associando a coppie di simboli binari più probabili (11) parole codice più corte (di lunghezza unitaria).
Rappresentazione del codice con un albero:
Regola:
- da un nodo escono due rami;
- ramo verso l’alto associamo “1″;
- ramo verso il basso associamo “0″.
Nessuna parola codice è prefisso di un’altra parola codice => Codice a prefisso
Rappresentazione del codice con un albero
Esempio di codifica di sorgente
Quanta memoria al più possiamo risparmiare?
- La risposta ci viene data dal I Teorema di Shannon.
- Il minimo numero di simboli binari per rappresentare “senza perdite”ogni simbolo della sorgente è dato dalla quantità di informazione che ogni simbolo di sorgente trasporta mediamente.
Misura dell’informazione
- L’informazione di un evento è associata al suo livello di incertezza ovvero alla probabilità con cui si verifica.
Esempio: Partita Napoli-Roma
Possibili eventi:
- V = Il Napoli vince sulla Roma
- S = Il Napoli è sconfitto dalla Roma
- P = Il Napoli pareggia con la Roma
Pr(V) + Pr(S) + Pr(P) = 1
Misura dell’informazione
Assumiamo di aver stimato le tre probabilità:
- Pr(V) = 0.001, Pr(S) = 0.99, Pr(P) = 0.009
- Pr(V) < Pr(P) << Pr(S)
L’informazione di un evento è una funzione decrescente della sua probabilità.I(V) > I(P) >> I(S)
Misura dell’informazione di una variabile aleatoria discreta
L’informazione associata al verificarsi di due eventi A e B indipendenti deve essere la somma delle informazioni di A e B:
I(AB) = I(A) + I(B)
Definiamo autoinformazione I(ai) associata alla emissione del simbolo ai:
I(ai) = log1/p(ai) = -logp(ai)
Misura dell’informazione di una variabile aleatoria discreta
- Se il logaritmo è in base 2 l’autoinformazione I(•) si misura in bit (binary unit).
- Se il logaritmo è in base e l’autoinformazione I(•) si misura in nat (natural unit)
Misura dell’informazione di una variabile aleatoria discreta
I(ai) = log1/p(ai) = -logp(ai)
Questa definizione assicura le due proprietà:
- Decrescenza con p(ai)
- Additività per simboli indipendenti grazie al logaritmo
I(ai, bj) = -logp(ai, bj) = I(ai) + I(bj) Inoltre:
- I(•) dipende solo dalla probabilità di ai cioè I[p(ai)]
- I(•) è una funzione continua di p(ai) = pi
Entropia di una variabile aleatoria
La corrispondenza ai I(pi) definisce una variabile aleatoria discreta X:
- H(X) Entropia della variabile aleatoria X.
- E[I(ai)] Informazione convogliata mediamente da un simbolo.
Entropia di una variabile aleatoria
Esempio: Binary Source di parametro p
Esempio: Binary Source di parametro p
Esempio: Binary Source di parametro p
Entropia di una coppia di variabili aleatorie
Consideriamo un esperimento congiunto il cui spazio campione S = S1 x S2 con S1 = {V,P,S} e S2 = {G,NG}:
- G – gioca Totti
- NG – non gioca Totti
Su ogni singolo esperimento Si possiamo definire una v.a.:
- H(X) misura l’informazione media fornita dall’esperimento S1
- H(Y) misura l’informazione media fornita dall’esperimento S2
Entropia di una coppia di variabili aleatorie
- Qual’è l’informazione media fornita da S cioè dalla coppia di v.a.?
- I(X,Y) è uguale a I(X) +I(Y)? NO!
Definiamo l’informazione convogliata dalla coppia di risultati xi e yi (immagine).
Entropia di una coppia di variabili aleatorie
Entropia di una coppia di variabili aleatorie
Quindi I(X, Y) è una variabile aleatoria funzione delle variabili aleatorie; l’entropia congiunta delle v.a X e Y è H(X,Y).
Entropia di una coppia di variabili aleatorie
Entropia congiunta delle v.a X e Y
Entropia congiunte di n v.a.
- L’informazione mediamente convogliata dal blocco di n v.a. è definita in prima immagine.
Proprietà di additività
- Se le n v.a. sono statisticamente indipendenti si dimostra facilmente la formula in seconda immagine.
Entropia congiunte di n v.a.
Entropia condizionale
Nella prima immagine si ricava I(xi|yj), dove p(xi|yj) è la probabilità che si verifichi xi dato (condizionatamente) che si è verificato yj .
Il caso generale è mostrato in terza immagine.
Entropia condizionale
H(X,Y) = H(X) +H(Y/X)
Entropia condizionale
Più in generale abbiamo la formula in immagine, in cui la sommatoria regola a catena per l’entropia.
Regola a catena per l'entropia
Entropia condizionale
Se X e Y sono statisticamente indipendenti:
- H (X/Y) = H (X)
- H (Y/H) = H (Y)
Infatti in questo caso si ha:
- p(x/y)= p(x,y)/p(y)= p(x)p(y)/p(y) =p(x)
Proprietà dell’entropia
- H(X1, X2, … ,Xn) è funzione solo della p(x1, x2, … , xn).
- Se le Xi sono congiuntamente statisticamente indipendenti H(X1, X2, …, Xn) è funzione delle p(xi).
- L’entropia è non negativa: H(X1, X2, … , Xn) = H(X) ≥ 0; infatti I(X1,X2, … , Xn) ≥ 0 cioè è una v.a. non negativa => La media statistica di I(X1,X2, … , Xn), cioè H(X), è maggiore o uguale a 0.
Tasso di informazione di una sorgente discreta
Tasso di informazione di una sorgente discreta
Tasso di informazione di una sorgente discreta senza memoria (DMS)
- Xi è un segnale aleatorio numerico
- H(X2) statistica indipendenza
- K • H(X) stazionarietà
Tasso di informazione di una sorgente discreta senza memoria (DMS)
Tasso di informazione di una sorgente discreta senza memoria (DMS)
Per una DMS (Discrete Memoryless Source) il Tasso H, cioè il numero medio di bit emesso dalla sorgente per simbolo, è uguale all’entropia del generico simbolo X:
H = H(X)
- H(X) è un parametro medio di una variabile aleatoria.
- H è un parametro medio di un segnale aleatorio (segnale numerico).
Misura dell’informazione di una sorgente DMS
Esempio: Una sorgente di banda monolatera 4KHz è campionata alla frequenza di Nyquist. Supponendo che la sequenza dei campioni può essere modellata approssimativamente come una sorgente discreta senza memoria con alfabeto sorgente:
A ≡ {-2,-1,0,1,2} con le probabilità {1/2, 1/4, 1/16, 1/32}
- Valutare il tasso di informazione emesso dalla sorgente DMS.
Misura dell’informazione di una sorgente DMS
La frequenza di Nyquist è 2×4.000=8.000 campioni al secondo. Poiché ogni campione trasporta 15/8 bits la sorgente fornisce un tasso in bits/sec:
15/8 x 15000 bits/sec
Misura dell'informazione di una sorgente DMS
Considerazioni conclusive
Riassunto della lezione
- E’ stato introdotto il modello di sorgente numerica di informazione mostrando gli effetti di una eventuale codifica di sorgente.
- Sono stati introdotti i concetti di entropia di una variabile aleatoria, entropia di una coppia di variabili, entropia congiunta di n variabili aleatorie, entropia condizionale.
- E’ stato definito il tasso di informazione di una DMS.
Prossima lezione
Codifica di sorgente
- I Teorema di Shannon
- Codifica di Huffman
- Algoritmo di Lempel-Ziv