Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Luigi Paura » 3.Codifica di sorgente


Codifica di sorgente

Sommario:

  • I Teorema di Shannon
  • Codifica di Huffman
  • Codifica di Lempel-Ziv

Teorema della Codifica di Sorgente

Il teorema di Shannon

  • Il I teorema di Shannon stabilisce quale è la compressione limite che un codice può raggiungere senza introdurre distorsione (Codifica senza distorsioni).
  • Il minimo numero (medio) di simboli binari per rappresentare il generico simbolo di sorgente (lunghezza media delle parole codice) non può essere più piccolo della entropia della sorgente.

Il teorema di Shannon

R = Tasso del codice

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente

Tasso del codice

Tasso del codice


Il teorema di Shannon

  • Sia S una DMS con alfabeto di sorgente A={a1,a2,…,aN}.
  • In accordo alla Legge dei Grandi Numeri per una sequenza di simboli di lunghezza n sufficientemente lunga (n ) si ha la formula in prima immagine.
Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Il teorema di Shannon

Definizione:

  • Una sequenza tipica è una sequenza che soddisfa la Legge dei Grandi Numeri cioè ni = pin per n -> ∞

Per una sequenza tipica si ha l’equiripartizione asintotica 2-nH(X) (immagine).

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Teorema della Codifica di Sorgente

Le sequenze tipiche hanno la stessa probabilità pari a 2-nH(X)

  • τ = insieme delle sequenze tipiche

Quante sono le possibili sequenze di lunghezza n?

Nn = 2nlogN

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Teorema della Codifica di Sorgente

Quante sono le sequenze tipiche (Nτ)?

  • Nτ = 2nH(X)
  • H(X) ≤ log N => Nτ ≤ Nn

Assegniamo parole codice solo alle sequenze tipiche!!!

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Teorema della Codifica di Sorgente

Serviranno solo Nτ = 2nH(x) parole codice cioè, se utilizziamo codici binari, nH(X) simboli binari per ogni sequenza lunga n simboli di sorgente

=> RISPARMIO DI RISORSE!

Tanto maggiore quanto più H(X) è minore di log N!!

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Teorema della Codifica di Sorgente

Cosa succede se la sorgente emette una sequenza non tipica?

  • Non abbiamo previsto una parola codice!
    • Errore ovvero distorsione!
  • Questo evento si verifica per n con probabilità nulla
    • Codifica asintoticamente senza distorsione

Teorema della Codifica di Sorgente

Per realizzare il codificatore possiamo utilizzare una memoria con Nτ = 2nH(x) locazioni in cui allocare le parole codice: un puntatore controllato dalla sequenza dei simboli di sorgente selezionerà la parola codice.

Ingombro di memoria esponenziale con n! -> NON REALIZZABILE!

Teorema della Codifica di Sorgente

Teorema della Codifica di Sorgente


Teorema della Codifica di Sorgente

Enunciato:

  • Una sorgente senza memoria con tasso entropico H(X) può essere codificata con distorsione arbitrariamente piccola (n ) con tassi R (bits/simbolo di sorgente) tali che:
    • R ≥ H(X)
  • Inversamente se R < H(X) distorsione asintoticamente nulla.

Codifica di Huffman

Il I Teorema di Shannon è un teorema di esistenza: ci assicura che se desideriamo un codice con tasso R ≥ H(X), questo esiste.

Come individuarlo?

  • Algoritmo di Huffman

Algoritmo di Huffman

Ipotesi: conosciamo le probabilità pi dei simboli ai della DMS (Codifica entropica).

  • Il codice di Huffman è un codice blocco/lunghezza variabile.
  • Le parole codice hanno lunghezze differenti:
    • i simboli di sorgente più probabili sono associati alle parole codice più corte;
    • i simboli meno probabili sono associati alle parole codice più lunghe.

Algoritmo di Huffman

Procedura

  1. Si ordinano le pi in maniera decrescente.
  2. Si saldano i due simboli di sorgente con probabilità più piccole in un unico simbolo con probabilità pari alla somma delle probabilità.
  3. Se sono rimasti solo due simboli vai al passo 4. altrimenti ritorna al passo 1.
  4. Si assegnano arbitrariamente uno “0″ed un “1″ ai due simboli.
  5. Se un simbolo è il risultato di una “saldatura” si assegna ai due simboli uno “0″ ed un “1″ e si ripete il passo 5., altrimenti si arresta l’algoritmo.

Algoritmo di Huffman

Algoritmo di Huffman

Algoritmo di Huffman


Algoritmo di Huffman: Esempio

Algoritmo di Huffman: esempio

Algoritmo di Huffman: esempio


Algoritmo di Huffman: Esempio

  • Calcoliamo il tasso R del codice.
  • Verificare che l’entropia H(X) =1.875= R.
Algoritmo di Huffman: esempio

Algoritmo di Huffman: esempio


Codifica di Huffman

  • Si può dimostrare che la lunghezza media R di un codice di Huffman soddisfa la relazione in prima immagine.
  • Se codifichiamo un blocco di n simboli di una DMS otteniamo la relazione in seconda immagine.
Codifica di Huffman

Codifica di Huffman

Codifica di Huffman

Codifica di Huffman


Codifica di Huffman

H(X) ≤ R << H(X) + 1/n

Cioè per n>>1 => R -> H(X) ma la complessità di realizzazione cresce esponenzialmente con n (prima immagine).

Esempio: DMS con tre simboli equiprobabili

Codifica di Huffman

Codifica di Huffman


Codifica di Huffman

  • Se codifichiamo a blocchi con n = 2 si hanno 32 = 9 simboli di sorgente con probabilità pi = 1/9
  • Se si costruisce un codice di Huffman si ha che R2 = 3.222

In immagine:

  • 1.611 codifica per coppia di simboli
  • 1.667 codifica per simbolo
DMS con tre simboli equiprobabili

DMS con tre simboli equiprobabili


La codifica di Lempel-Ziv

Proprietà:

  • Non richiede la conoscenza delle probabilità dei simboli (come la codifica di Huffman).
  • La procedura è autolearning: è una codifica universale.
  • E’ un codice a lunghezza variabile/lunghezza fissa.

La codifica di Lempel-Ziv: Esempio

Esempio:

0100001100001010000010100000110000010100001001001

  • La sequenza è suddivisa in sottosequenze di lunghezza variabile con il criterio che quando si riconosce una nuova sottosequenza essa si inserisce nel dizionario.
  • Ogni frase è la concatenazione di una frase precedente + un simbolo binario.
La codifica di Lempel-Ziv: Esempio

La codifica di Lempel-Ziv: Esempio


La codifica di Lempel-Ziv

  • Detto N il numero delle frasi del Dizionario sono necessari logN bit per ogni frase + un bit per l’ultimo simbolo binario.
La codifica di Lempel-Ziv

La codifica di Lempel-Ziv


La codifica di Lempel-Ziv

Si può dimostrare che per una sorgente stazionaria ed ergodica il numero di bit per n -> ∞ è pari a nH(X):

nH(X) ≤ n perchè H(X) ≤ 1

Problemi:

  • Quante frasi inserire nel dizionario?
  • Come evitare l’overflow? Eliminando dal dizionario le frasi non più ricorrenti.

La codifica di Lempel-Ziv

  • E’ molto utilizzato per comprimere file per computer (routine sotto UNIX quali ZIP, ZOO, LZH,ARJ etc.).
  • Rapporti di compressione: dipende dalle caratteristiche della sorgente.

Considerazioni conclusive

Riassunto della lezione

  • Sono state introdotte le sequenze tipiche ed è stato presentato l’enunciato del I teorema di Shannon.
  • E’ stato presentato l’algoritmo di Huffman (algoritmo per la costruzione del codice, confronto tra lunghezza media del codice e l’entropia della sorgente).
  • E’ stata descritta la codifica di Lempel-Ziv.

Prossima lezione

Trasmissione su canale AWGN

  • Il canale AWGN
  • Rappresentazione geometrica dei segnali
  • Tecniche di modulazione

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