Esercizio 4quantizzatore a 6 livelli, bit aggiuntivi e codice non decodificabile (tema d'esame agosto 2025)

---

Teoria usata: Conversione A-D e D-A - campionamento, anti-aliasing e interpolazionePer trasmettere un segnale analogico in forma digitale lo si campiona (a frequenza $F_s\ge2B$, dopo un filtro anti-aliasing), lo si quantizza su $L=2^b$ livelli e si trasforma ogni livello in $b$ bit. Il bit-rate nominale è $R_b=F_s,b$. Al ricevitore si fa il percorso inverso e si interpola (con un filtro con risposta $T_s,\mathrm{rect}\frac f{2B}$ in teoria, con un mantenitore di ordine zero in pratica). La quantizzazione è l'unica operazione che introduce un errore irreversibile.Conversione A-D e D-A - campionamento, anti-aliasing e interpolazione →, Quantizzatore uniforme - livelli, mid-riser ed erroriUn quantizzatore mappa i campioni reali su $L=2^b$ livelli. Quello uniforme (PCM) sceglie un range dinamico $[-V_{sat},V_{sat}]$ e un passo $\Delta=\frac{2V_{sat}}L$; nel tipo mid-riser i livelli sono $\pm\frac\Delta2,\pm\frac{3\Delta}2,\dots$ e non c'è lo zero. L'errore $e_q=a_q-a$ ha una parte granulare (in $[-\frac\Delta2,\frac\Delta2]$, circa uniforme, potenza $\frac{\Delta^2}{12}$) e una di saturazione (fuori range). Per renderlo piccolo servono $P_{sat}$ piccola e $L$ grande.Quantizzatore uniforme - livelli, mid-riser ed errori →, SNR di quantizzazione e progetto del quantizzatoreL'SNR di quantizzazione è $\Lambda_q=\frac{M_a}{M_e}$. Con errore granulare uniforme e saturazione trascurabile vale $\Lambda_q=\frac{\sigma^2}{\Delta^2/12}=3\frac{\sigma^2}{V_{sat}^2},2^{2b}$, cioè $[\Lambda_q]{dB}=6{,}02,b+4{,}77+20\log{10}\frac\sigma{V_{sat}}$: ogni bit in più dà $+6$ dB. Per progettare: $V_{sat}$ dalla probabilità di saturazione ($V_{sat}=\sigma,Q^{-1}\left(\frac{P_{sat}}2\right)$ per un gaussiano), poi $b$ dall'SNR richiesto, arrotondando per eccesso.SNR di quantizzazione e progetto del quantizzatore →, Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →, Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →.

(1) Frequenza di campionamento

La PSD è un rettangolo $\operatorname{rect}\left(\frac f{2B_a}\right)$, nullo per $\lvert f\rvert>B_a$: il segnale è a banda limitata con $B=B_a=50$ Hz. Per il teorema del campionamento (Teorema del campionamento, interpolazione e aliasingTeorema di Shannon: un segnale a banda limitata $\omega_M$ si ricostruisce esattamente dai campioni se $T_c<\pi/\omega_M$ (frequenza di campionamento maggiore di quella di Nyquist $2f_{\max}$), con la formula di interpolazione ideale $x(t)=\sum_nx(nT_c)\operatorname{sinc}\left(\frac{t-nT_c}{T_c}\right)$. Sotto Nyquist c'è aliasing: le frequenze alte si confondono con quelle basse e l'informazione è persa.Teorema del campionamento, interpolazione e aliasing →) si ricostruisce senza errore se $F_s\ge2B$: $$F_{s,min}=2B_a=100\ \text{Hz}.$$

(2) Soglie e probabilità di saturazione

Il segnale è gaussiano a media nulla con varianza uguale alla potenza, cioè all'integrale della PSD: $$\sigma^2=\int\mathcal P(f)\,df=P_0\cdot2B_a=10^{-4}\cdot100=10^{-2}\ \text{V}^2,\qquad\sigma=0{,}1\ \text{V}.$$ Il range è $[-0{,}3,0{,}3]$ V con $L=6$ livelli: $\Delta=\frac{0{,}6}6=0{,}1$ V. Le soglie interne (cinque, per sei livelli) sono i multipli di $\Delta$: $$v_i\in\{-0{,}2,\ -0{,}1,\ 0,\ 0{,}1,\ 0{,}2\}\ \text{V},$$ con i livelli (mid-riser) in $\pm0{,}05,\ \pm0{,}15,\ \pm0{,}25$ V; oltre $\pm0{,}3$ V si satura. La probabilità di saturazione (due code): $$P_{sat}=2Q\left(\frac{0{,}3}{0{,}1}\right)=2Q(3)=2\cdot1{,}35\cdot10^{-3}=2{,}7\cdot10^{-3}.$$ Con $P_{sat}$ di questo ordine l'errore granulare domina, ma la saturazione non è trascurabile del tutto: $\Lambda_q=\frac{\sigma^2}{\Delta^2/12}=12=10{,}8$ dB (solo granulare).

(3) Bit aggiuntivi per $+10$ dB

A $P_{sat}$ (cioè $V_{sat}$) invariata, l'SNR è proporzionale a $L^2$: $\Lambda_q\propto L^2$. Guadagnare almeno $10$ dB (un fattore $10$ in potenza) richiede $$\frac{L'}{L}\ge\sqrt{10}=3{,}162\ \Longrightarrow\ L'\ge6\cdot3{,}162=18{,}97\ \Longrightarrow\ L'=2^{b'}\ge19.$$ Con la codifica a lunghezza fissa i $6$ livelli occupano $\lceil\log_26\rceil=3$ bit. Si deve avere $2^{b'}\ge19$, cioè $b'=5$ bit ($L'=32$): con $4$ bit ($L'=16$) l'aumento sarebbe $20\log_{10}\frac{16}6=8{,}5$ dB (non basta); con $5$ bit $20\log_{10}\frac{32}6=14{,}5$ dB. Servono quindi 2 bit aggiuntivi (da $3$ a $5$). Lo stesso risultato dalla regola dei $6{,}02$ dB per bit: $\frac{10}{6{,}02}=1{,}66\to2$ bit.

(4) Probabilità dei simboli ed efficienza

I livelli (con le regioni) sono simmetrici; con $\frac\Delta\sigma=1$ gli estremi in unità di $\sigma$ sono $0,1,2$ e l'ultima regione si estende all'infinito (comprende la saturazione). Per ciascun livello con segno:

(somma $2\,(0{,}02275+0{,}1359+0{,}3413)=1$.) L'entropia è $$H=2\left[0{,}02275\log_2\frac1{0{,}02275}+0{,}1359\log_2\frac1{0{,}1359}+0{,}3413\log_2\frac1{0{,}3413}\right]=2{,}09\ \text{bit}.$$ Con la codifica A) a lunghezza fissa ogni livello usa $L_y=3$ bit, quindi $$\eta=\frac{H}{L_y\log_2 2}=\frac{2{,}09}3=0{,}70\qquad(\text{il rate nominale è }3F_s,\ \text{quello di informazione }2{,}09F_s).$$ (Rispetto al massimo teorico di un quantizzatore a $6$ livelli, $\log_26=2{,}585$ bit, si avrebbe $\frac{2{,}09}{2{,}585}=0{,}81$.)

(5) La codifica B)

Le parole sono $\{000,00,01,10,11,111\}$.

• Kraft-McMillan: $\sum2^{-\ell_i}=\frac18+4\cdot\frac14+\frac18=1{,}25>1$: nessun codice binario decodificabile può avere queste lunghezze.
• Ambiguità concreta (come suggerisce il testo): $00$ è prefisso di $000$: la sequenza $00000$ si decodifica sia come $q_1q_0$ ($00\,000$) sia come $q_0q_1$ ($000\,00$); $11$ e $111$ creano lo stesso problema ($11111$ come $q_4q_5$ oppure $q_5q_4$).
• Contro-prova con Shannon: la lunghezza media del codice B) con le probabilità trovate sarebbe $L_B=3\cdot0{,}02275+2\cdot(0{,}1359\cdot2+0{,}3413\cdot2)+3\cdot0{,}02275=2{,}046$ bit, inferiore all'entropia $2{,}09$ bit: un codice decodificabile non può scendere sotto $H$ (Codifica di sorgente - codici a prefisso e teorema di ShannonLa codifica di sorgente riduce il numero di bit mappando le parole della sorgente in parole di lunghezza variabile (più corte per le più probabili), senza perdere informazione. Il codice deve essere decodificabile; i codici a prefisso (nessuna parola è prefisso di un'altra) lo sono. Kraft-McMillan: se il codice è decodificabile $\sum M_y^{-L(b)}\le1$. Teorema di Shannon: $L_y\ge\frac{H(x)}{\log_2M_y}$ e esiste un codice a prefisso con $L_y\le\frac{H(x)}{\log_2M_y}+1$; l'efficienza è $\eta=\frac{H(x)}{L_y\log_2M_y}$.Codifica di sorgente - codici a prefisso e teorema di Shannon →).

Non è conveniente: non si può usare, perché non è decodificabile. Un codice a lunghezza variabile corretto è quello di Huffman (Codici di Shannon-Fano e di HuffmanIn un codice ottimo le parole più probabili non sono più lunghe di quelle meno probabili e le due parole più lunghe differiscono solo per l'ultimo simbolo. Shannon-Fano costruisce l'albero dall'alto dividendo ripetutamente i simboli in due gruppi di probabilità quasi uguali; Huffman lo costruisce dal basso unendo ogni volta i due simboli meno probabili ed è sempre ottimo tra i codici a prefisso. La lunghezza media $L_y$ è la somma delle probabilità dei nodi uniti, l'efficienza è $\eta=\frac{H}{L_y}$.Codici di Shannon-Fano e di Huffman →): unendo i due meno probabili si ottengono le lunghezze $1,2,3,4,5,5$ (assegnate a $q_3,q_2,q_4,q_1,q_0,q_5$) con le parole $q_3=0,\ q_2=11,\ q_4=100,\ q_1=1011,\ q_0=10100,\ q_5=10101$ (a prefisso), $L_y=0{,}3413+2\cdot0{,}3413+3\cdot0{,}1359+4\cdot0{,}1359+5\cdot2\cdot0{,}02275=2{,}20$ bit, $\eta=\frac{2{,}09}{2{,}20}=0{,}95$ contro $0{,}70$ del codice A.

(Verificato: $\sigma=0{,}1$ V, $P_{sat}=2{,}70\cdot10^{-3}$, $H=2{,}0896$ bit, Kraft $=1{,}25$, $L_B=2{,}0455$ bit, Huffman $L_y=2{,}2029$ bit.)

Errori comuni

• Dimenticare che le soglie sono cinque (non sei) per $L=6$ livelli.
• Calcolare i bit aggiuntivi con $L'\ge10L$ invece di $L'\ge\sqrt{10}\,L$: l'SNR cresce come $L^2$.
• Contare i $3$ bit di $L=6$ come $\log_26$ senza arrotondare quando si parla di parole a lunghezza fissa.
• Usare un codice per cui una parola è prefisso di un'altra senza controllare Kraft o l'ambiguità.