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
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
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
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
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
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
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
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
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
- Si ordinano le pi in maniera decrescente.
- Si saldano i due simboli di sorgente con probabilità più piccole in un unico simbolo con probabilità pari alla somma delle probabilità.
- Se sono rimasti solo due simboli vai al passo 4. altrimenti ritorna al passo 1.
- Si assegnano arbitrariamente uno “0″ed un “1″ ai due simboli.
- 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: 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
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
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
- 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
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
- 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
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
Le lezioni del Corso
1. Schema canonico di un sistema di trasmissione numerico punto-punto
4. Rappresentazione geometrica dei segnali
5. Trasmissione numerica su canale AWGN
6. Prestazioni del ricevitore ottimo su canale AWGN I
7. Prestazioni del ricevitore ottimo su canale AWGN II
8. Demodulazione MV non coerente di segnali FSK
9. Trasmissione su canale AWGN a banda limitata
10. Capacità di canale e codifica
11. Codifica di canale a blocchi
13. Codici ciclici
I materiali di supporto della lezione
G.Proakis, M.Salehi, “Communication Systems Engineering”, p. 267-273.
