Lezione 2Entropia condizionata e codifica di sorgente

Fonte: appunti a mano tlc_02, corso Telecommunications, UniPD.

Argomenti trattati

1. Entropia condizionata $H(x|y)=H(x,y)-H(y)$ (dalla probabilità condizionata e dal teorema di Bayes), limiti $0\le H(x|y)\le H(x)$ e significato pratico (informazione guadagnata scoprendo $x$ quando già si conosce $y$).
2. Messaggi di $N$ simboli: alfabeto e dizionario, entropia media per simbolo $H_s=\frac{H(\vec x)}N$ e suoi limiti, simboli indipendenti.
3. Rate ed efficienza di una sorgente: bit-rate nominale $R_b=F_s\log_2M$, rate di informazione $R_0=F_sH_s$, efficienza $\eta_x=\frac{H_s}{\log_2M}$ e ridondanza.
4. Codifica di sorgente: lossy e lossless; codifica a lunghezza variabile e problema della decodificabilità; codici a prefisso; disuguaglianza di Kraft-McMillan.
5. Teorema di Shannon sulla codifica di sorgente: $\tilde L\ge\frac{H}{\log_2M}$ e esistenza di un codice con $\tilde L<\frac{H}{\log_2M}+1$ (lunghezze di Shannon $\lceil\log_M\frac1p\rceil$); caso di uguaglianza con probabilità potenze di $\frac12$.
6. Algoritmi: codifica di Shannon, di Shannon-Fano (dall'alto) e di Huffman (dal basso), con i teoremi di ottimalità; esempio con probabilità $0{,}38;0{,}19;0{,}17;0{,}14;0{,}12$ ($H=2{,}184$; $\tilde L=2{,}74$ / $2{,}26$ / $2{,}24$).
7. Raggruppamento di simboli per migliorare l'efficienza ($A\,0{,}4$, $B\,0{,}3$, $C\,0{,}3$ a coppie) e codifica aritmetica (Shannon-Fano-Elias) per partizione di intervalli reali.

Teoria

• Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua → — entropia condizionata, informazione mutua, entropia per simbolo, rate ed efficienza
• Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente → — decodificabilità, Kraft-McMillan, Shannon, Shannon-Fano, Huffman, raggruppamento, codifica aritmetica

Esercizi

• Esercizio - entropia del numero di lanci di una moneta — entropia di una variabile geometrica e codice di Shannon (unario)
• Esercizio - sorgente a sette simboli e codici di Shannon, Shannon-Fano e Huffman — i tre codici a confronto
• Esercizio - il meteorologo, entropia e informazione mutua — entropia congiunta, condizionata e informazione mutua

Lezione precedente: Lezione 1 · Conversione A-D e quantizzazione · Lezione successiva: Lezione 3 · Esercizi su quantizzazione e codifica di sorgente