Lezione 3Esercizi su quantizzazione e codifica di sorgente

Fonte: appunti a mano tlc_03, svolgimento della scheda di esercizi n. 1 ("Quantization and Source coding"), corso Telecommunications, UniPD; e l'approfondimento sul progetto di un quantizzatore.

Argomenti trattati

1. Esercizio 1: segnale uniforme in $[-V,V]$ con quantizzatore mid-riser a $3$ bit; media, potenza e varianza; SNR di quantizzazione per $v_{sat}=V$ ($18{,}06$ dB), $2V$ ($12{,}04$ dB) e $\frac V2$ (con saturazione, $\approx7{,}5$ dB).
2. Esercizio 2: segnale gaussiano con $\sigma_a^2=4$ V$^2$, $B=250$ Hz, $F_s=1{,}6\times$Nyquist, $6$ bit: bit-rate, passo $\Delta$, $P_{sat}=2Q(4)$, SNR ($28{,}85$ dB), bit per $36$ dB ($b=8$) e limite per $60$ dB.
3. Esercizio 3: entropia del numero di lanci di una moneta fino alla prima croce ($H=2$ bit), somma notevole $\sum nq^n$ e codice di Shannon.
4. Esercizio 4: sorgente senza memoria a $7$ simboli: entropia ($2{,}4457$ bit), Shannon ($3{,}00$ bit), Shannon-Fano ($2{,}55$ bit), Huffman ($2{,}49$ bit, $\eta=98{,}2\%$).
5. Approfondimento: quantizzatore ottimo per una densità lineare crescente (media non nulla, potenza dell'errore, Lloyd-Max e mid-tread, guadagno di circa $1$ dB rispetto all'uniforme).

Teoria

• Quantizzazione e rumore di quantizzazioneIl quantizzatore mappa ogni campione reale su uno dei $L=2^b$ livelli. Il quantizzatore uniforme mid-riser ha passo $\Delta=\frac{2v_{sat}}{L}$, soglie multiple di $\Delta$ e livelli multipli dispari di $\frac\Delta2$. L'errore $e_q=a_q-a$ è granulare (in $[-\frac\Delta2,\frac\Delta2]$, circa uniforme, potenza $\frac{\Delta^2}{12}$) o di saturazione (fuori da $[-v_{sat},v_{sat}]$, trascurabile se $P_{sat}$ è piccola). L'SNR è $\Lambda_q=\frac{M_a}{M_{e_q}}$ e, con saturazione trascurabile, $[\Lambda_q]{dB}=6{,}02,b+4{,}77-20\log{10}\frac{v_{sat}}{\sigma_a}$: $+6$ dB per ogni bit.Quantizzazione e rumore di quantizzazione →
• 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 →
• 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 →

Esercizi

• Esercizio - quantizzazione di segnali uniformi e gaussiani — esercizi 1 e 2
• Esercizio - entropia del numero di lanci di una moneta — esercizio 3
• Esercizio - sorgente a sette simboli e codici di Shannon, Shannon-Fano e Huffman — esercizio 4
• Esercizio - progetto di un quantizzatore non uniforme — approfondimento

Lezione precedente: Lezione 2 · Entropia condizionata e codifica di sorgente · Lezione successiva: Lezione 4 · Sistemi a coda, stabilità e formula di Little