Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Luigi Paura » 2.Compressione dati


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.
Sorgente numerica

Sorgente numerica


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

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


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

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)
    • 1 Nat = 1.443 bit

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

Entropia di una variabile aleatoria


Esempio: Binary Source di parametro p

Esempio: Binary Source di parametro p

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.:

  • S1 -> X
  • S2 -> Y
  • 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


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 di una coppia di variabili aleatorie

Entropia congiunta delle v.a X e Y

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 congiunte di n v.a.

Proprietà di additività

Proprietà di additività


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
Entropia condizionale
Entropia condizionale

Entropia condizionale

H(X,Y) = H(X) +H(Y/X)

Entropia condizionale

Entropia condizionale


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

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)
Entropia condizionale

Entropia condizionale


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


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)


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

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

I materiali di supporto della lezione

G.Proakis, M.Salehi, “Communication Systems Engineering”, p. 267-273.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93