Esercizio - quantizzatore con densità esponenziale a due lati, codice di Shannon, 64-QAM e Hamming (compito del 23 gennaio 2026, es. 198)

---

Teoria usata: Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazioneUn quantizzatore uniforme a L = 2^b livelli e range [−v_sat, v_sat] ha passo Δ = 2v_sat/L. L'errore e = x − x^(q) è di saturazione fuori range (illimitato, da rendere raro con P_sat piccola) e granulare dentro (|e| ≤ Δ/2, uniforme con potenza Δ²/12). L'SNR di quantizzazione Λ_q = E[x²]/E[e²] vale in decibel 20log₁₀(σ_x/v_sat) + 4,77 + 6,02·b: ogni bit in più dà 6 dB. Per b minimo che garantisce una specifica: ⌈(specifica − c)/6,02⌉ con c = 20log₁₀(σ_x/v_sat) + 4,77.Quantizzazione uniforme - saturazione, errore granulare e SNR di quantizzazione →, Quantizzazione non uniforme, companding e conversione A-DIn un quantizzatore non uniforme gli intervalli I_i hanno larghezze diverse (stretti dove la densità è alta) e la potenza dell'errore è M_e = Σ M_{e_i} P(x ∈ I_i), con M_{e_i} = E[(x − a_qi)² | x ∈ I_i]. Si realizza con il companding (compressore μ(x), quantizzatore uniforme, espansore) o raggruppando gli intervalli di un quantizzatore uniforme fine. Nella conversione A-D con campionamento ogni T_s e b bit per campione, T_b = T_s/b e R_b = b/T_s bit/s. Esempio completo con densità esponenziale a due lati: v_sat, b, bit rate e periodo di simbolo della 16-QAM.Quantizzazione non uniforme, companding e conversione A-D →, Variabili aleatorie continue - uniforme, gaussiana, esponenziale e funzione QUna v.a. continua ha funzione di distribuzione F_x(a) = P(x ≤ a) e densità f_x(a) = dF_x/da ≥ 0 con integrale 1; P(A ≤ x ≤ B) = F_x(B) − F_x(A) = ∫A^B f_x e P(x = A) = 0. Uniforme U([a,b]): densità 1/(b−a), media (a+b)/2, varianza (b−a)²/12. Esponenziale unilatera di media m: (1/m)e^(−a/m), a ≥ 0. Gaussiana N(m, σ²): P(x ≥ A) = Q((A − m)/σ), con Q(A) coda della gaussiana standard. Somme di gaussiane indipendenti sono gaussiane (medie e varianze si sommano); teorema del limite centrale.Variabili aleatorie continue - uniforme, gaussiana, esponenziale e funzione Q →, Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica →, Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →, Modulazione QAM - costellazioni, energia e probabilità d'erroreLa QAM trasmette due PAM indipendenti su due portanti in quadratura: $s_m(t)=\alpha_{m,I}h_{Tx}(t)\cos(2\pi f_0t)-\alpha_{m,Q}h_{Tx}(t)\sin(2\pi f_0t)$ con $\alpha\in{\pm1,\pm3,\dots}$ e $M=2^{2b}$ ($2b$ bit per simbolo). La base è $\phi_{1,2}\propto h_{Tx}\cos,,-h_{Tx}\sin$ con energia $\frac{E_h}2$, i punti stanno su una griglia $\sqrt M\times\sqrt M$ con $d_{\min}=\sqrt{2E_h}$ ed $E_s=\frac{M-1}{3}E_h$. Con $q=Q\left(\sqrt{\frac{E_h}{2\sigma_I^2}}\right)$: $P[E]=4\left(1-\frac1{\sqrt M}\right)q-4\left(1-\frac1{\sqrt M}\right)^2q^2$, con $\frac{E_h}{2\sigma_I^2}=\frac{E_s}{\sigma_I^2}\frac{3}{2(M-1)}$. Con Gray su ogni asse $P_{bit}\simeq\frac{P[E]}{\log_2M}$.Modulazione QAM - costellazioni, energia e probabilità d'errore →, Codici di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →.

La densità. Per $a\ge0$ è $p_x(a)=C\,e^{-|a-2|/3}$: per $0\le a\le2$ vale $Ce^{-(2-a)/3}$ (cresce da $0{,}513\,C$ a $C$), per $a\ge2$ vale $Ce^{-(a-2)/3}$ (decresce); per $a<0$ si specchia. È una densità con due gobbe simmetriche, con picchi in $a=\pm2$, e media nulla per simmetria. La costante normalizza: $2\int_0^\infty p_x=2C\big[3(1-e^{-2/3})+3\big]=1$ dà $C=0{,}11211$ (il testo riporta $0{,}1121$). La potenza $\int a^2p_x\,da=23{,}38$ coincide con il $23{,}4$ dato.

(1) Saturazione e bit

Valore di saturazione. Con $P_{sat}=10^{-3}$ ripartita sulle due code simmetriche, ciascuna coda vale $5\cdot10^{-4}$. Per $v>2$ la coda destra è $$\int_v^{\infty}Ce^{-(a-2)/3}\,da=3C\,e^{-(v-2)/3}=5\cdot10^{-4}\ \Longrightarrow\ e^{-(v-2)/3}=\frac{5\cdot10^{-4}}{3\cdot0{,}11211}=1{,}487\cdot10^{-3}.$$ Passando ai logaritmi, $\frac{v-2}{3}=\ln\frac{1}{1{,}487\cdot10^{-3}}=6{,}511$, quindi $$v_{sat}=2+3\cdot6{,}511=21{,}53.$$

Numero di bit. $\Lambda_q=3\Big(\frac{\sigma_x}{v_{sat}}\Big)^22^{2b}$, con $\sigma_x^2=23{,}38$ (media nulla, potenza $=$ varianza), $\sigma_x=4{,}835$. Il fattore $20\log_{10}\frac{\sigma_x}{v_{sat}}=20\log_{10}0{,}2245=-12{,}97$ dB, quindi $$c=-12{,}97+4{,}77=-8{,}20,\qquad b\ge\frac{40-c}{6{,}02}=\frac{48{,}20}{6{,}02}=8{,}007.$$ Il valore è appena sopra $8$, quindi il minimo intero è $b=9$. Con $b=8$ si avrebbe $(\Lambda_q)_{dB}=-8{,}20+6{,}02\cdot8=39{,}96$ dB, che non rispetta il vincolo di $40$ dB per soli $0{,}04$ dB; con $b=9$ si ottengono $45{,}98$ dB. Il quantizzatore ha quindi $$v_{sat}=21{,}5,\qquad b=9,\qquad L=2^9=512\ \text{livelli},\qquad\Delta=\frac{2v_{sat}}{L}=\frac{43{,}07}{512}=0{,}084.$$ (Il corso riporta $v_{sat}=21{,}5$ e $b=\lceil8{,}004\rceil=9$: lo stesso risultato, con la stessa avvertenza che il margine è sottilissimo.)

(2) Probabilità degli $8$ valori quantizzati

Gli $8$ intervalli sono $(-\infty,-3]$, $[-3,-2]$, $[-2,-1]$, $[-1,0]$, $[0,1]$, $[1,2]$, $[2,3]$, $[3,\infty)$: passo $\Delta=1$, $v_{sat}=4$, livelli $\pm0{,}5,\pm1{,}5,\pm2{,}5,\pm3{,}5$; i due intervalli esterni comprendono tutta la coda (saturazione). Per la simmetria si calcolano i quattro intervalli di destra:

• $[3,\infty)$: $\int_3^\infty Ce^{-(a-2)/3}da=3C\,e^{-1/3}=3\cdot0{,}11211\cdot0{,}71653=0{,}2410$;
• $[2,3]$: $\int_2^3Ce^{-(a-2)/3}da=3C\big(1-e^{-1/3}\big)=3\cdot0{,}11211\cdot0{,}28347=0{,}0953$;
• $[1,2]$: la densità è $Ce^{-(2-a)/3}$ e per la simmetria attorno al picco $a=2$ l'area è uguale a quella di $[2,3]$: $0{,}0953$;
• $[0,1]$: $\int_0^1Ce^{-(2-a)/3}da=3C\big(e^{-1/3}-e^{-2/3}\big)=3\cdot0{,}11211\cdot(0{,}71653-0{,}51342)=0{,}0683$.

Le probabilità dei $8$ valori, dal livello più negativo, sono $$P=(0{,}2410,\ 0{,}0953,\ 0{,}0953,\ 0{,}0683,\ 0{,}0683,\ 0{,}0953,\ 0{,}0953,\ 0{,}2410).$$ Controllo: $2\,(0{,}2410+0{,}0953+0{,}0953+0{,}0683)=2\cdot0{,}5000=1$. (Il corso dà $0{,}2411$, $0{,}0953$, $0{,}0683$: la differenza di $10^{-4}$ viene da $C=0{,}1121$ arrotondato.)

(3) Lunghezza media del codice di Shannon

Il codice di Shannon assegna al simbolo di probabilità $p$ una parola di lunghezza $\lceil-\log_2p\rceil$ (Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica →):

• $p=0{,}2410$: $-\log_2p=2{,}05\Rightarrow3$ bit (due simboli);
• $p=0{,}0953$: $-\log_2p=3{,}39\Rightarrow4$ bit (quattro simboli);
• $p=0{,}0683$: $-\log_2p=3{,}87\Rightarrow4$ bit (due simboli).

$$\bar L=2\cdot0{,}2410\cdot3+4\cdot0{,}0953\cdot4+2\cdot0{,}0683\cdot4=1{,}446+1{,}525+0{,}546=3{,}52\ \text{bit.}$$ L'entropia di questa sorgente quantizzata è $H=-\sum p\log_2p=2{,}81$ bit e il teorema di Shannon dà $H\le\bar L<H+1$: $2{,}81\le3{,}52<3{,}81$, verificato. Il codice di Shannon è però poco efficiente qui: 3,52 bit sono più dei $3$ bit di una codifica a lunghezza fissa, e un codice di Huffman scenderebbe a circa $2{,}85$ bit.

(4) Bit rate e simboli al secondo

Con otto livelli, ogni campione è rappresentato con $3$ bit (codifica a lunghezza fissa di un quantizzatore uniforme), uno ogni $T_x=3$ ms: $$R_b=\frac{3\ \text{bit}}{3\cdot10^{-3}\ \text{s}}=1000\ \text{bit/s}=1\ \text{kbit/s}.$$ Con una $64$-QAM ogni simbolo porta $\log_26=\log_264=6$ bit, quindi si trasmettono $$\frac{1000\ \text{bit/s}}{6\ \text{bit/simbolo}}=166{,}7\ \text{simboli/s}$$ (periodo di simbolo $6$ ms; Quantizzazione non uniforme, companding e conversione A-DIn un quantizzatore non uniforme gli intervalli I_i hanno larghezze diverse (stretti dove la densità è alta) e la potenza dell'errore è M_e = Σ M_{e_i} P(x ∈ I_i), con M_{e_i} = E[(x − a_qi)² | x ∈ I_i]. Si realizza con il companding (compressore μ(x), quantizzatore uniforme, espansore) o raggruppando gli intervalli di un quantizzatore uniforme fine. Nella conversione A-D con campionamento ogni T_s e b bit per campione, T_b = T_s/b e R_b = b/T_s bit/s. Esempio completo con densità esponenziale a due lati: v_sat, b, bit rate e periodo di simbolo della 16-QAM.Quantizzazione non uniforme, companding e conversione A-D →).

(5) Quantizzatore equiprobabile

Con $8$ livelli equiprobabili ogni valore ha probabilità $\frac18$ e l'entropia è $\log_28=3$ bit. Tra tutte le variabili aleatorie definite sullo stesso alfabeto (qui $8$ simboli) la distribuzione uniforme ha entropia massima, $\log_2L$ (Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →), e ogni altra distribuzione, come quella del punto 2, ha entropia minore: $2{,}81<3$. La risposta è quindi: l'entropia è maggiore con il quantizzatore equiprobabile. (Le soglie si ottengono da $F_x(t_k)=\frac k8$: per questa densità valgono $0,\ \pm1{,}63,\ \pm2{,}89,\ \pm4{,}97$, calcolate con Python.)

(6) Codice di Hamming con $k=4$

Un codice di Hamming con $k=4$ bit di informazione ha $n=7$ (è il codice $(7,4)$, $n=2^m-1$ con $m=3$ bit di parità). I bit che entrano nel codificatore sono quelli del quantizzatore equiprobabile: $3$ bit per campione ogni $3$ ms, cioè $1000$ bit/s (con valori equiprobabili la lunghezza fissa è ottima). Il codificatore aggiunge $3$ bit ogni $4$: $$R_{b,\text{canale}}=1000\cdot\frac74=1750\ \text{bit/s.}$$ Il codice ha distanza minima $3$ e corregge qualunque singolo errore (non ne corregge due): una parola ricevuta è decodificata correttamente se il canale (binario simmetrico senza memoria, errore per bit $p=3\cdot10^{-2}$) commette zero errori oppure uno solo sui $7$ bit: $$P_C=(1-p)^7+7\,p\,(1-p)^6=0{,}97^7+7\cdot0{,}03\cdot0{,}97^6=0{,}8080+0{,}1749=0{,}983.$$ La soluzione del corso riporta il risultato $0{,}98$ (con una forma di calcolo confusa nel testo estratto). Dunque la probabilità di errore sulla parola è circa $1{,}7\%$, contro $1-0{,}97^4=11{,}5\%$ per quattro bit non codificati.

(Tutti i risultati sono stati verificati con Python: $v_{sat}=21{,}534$; $(\Lambda_q)_{dB}=39{,}96$ per $b=8$ e $45{,}98$ per $b=9$; probabilità dei livelli; $\bar L=3{,}518$; $H=2{,}812$; $P_C=0{,}9829$.)

Errori comuni

• Arrotondare $b=8{,}007$ a $8$: serve $9$ perché con $8$ bit la specifica non è rispettata (si ricalcola l'SNR prima di fermarsi).
• Usare $P_{sat}$ intera per una sola coda: ogni coda pesa $5\cdot10^{-4}$.
• Contare per l'intervallo esterno solo l'area in $[3,4]$: l'intervallo $[3,\infty)$ comprende anche la saturazione.
• Considerare il codice di Shannon ottimo: qui è peggiore della lunghezza fissa.
• Calcolare la probabilità di corretta decodifica solo come $(1-p)^7$ (si dimentica il caso di un solo errore, corretto dal codice).