Esercizio - Kraft-McMillan, Huffman, Hamming (7,4) e attenuazione massima con 16-QAM (secondo compitino del 12 gennaio 2024, es. 170)

---

Teoria usata: Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media → (punto 1), 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 Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon → (punto 2), 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 → (punto 3), 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 → (punto 4), 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 → (punto 5). Il quantizzatore: 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 →.

(1) Il valore di $K$ e le lunghezze $2,2,2,3,3,3,4,5$

Le probabilità devono sommare a $1$: $$2\,(4K+3K+2K+K)=20K=1\ \Rightarrow\ K=\frac1{20}=0{,}05.$$ Le probabilità sono $q_0,q_7:0{,}05$; $q_1,q_6:0{,}10$; $q_2,q_5:0{,}15$; $q_3,q_4:0{,}20$.

Kraft-McMillan (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →): un codice a prefisso binario con lunghezze $l_i$ esiste solo se $\sum_i2^{-l_i}\le1$: $$3\cdot\frac14+3\cdot\frac18+\frac1{16}+\frac1{32}=\frac{24+12+2+1}{32}=\frac{39}{32}=1{,}219>1.$$ La condizione non è verificata: non esiste un codice a prefisso (né alcun codice decodificabile) con quelle lunghezze. Si vede anche dal fatto che le tre parole da $2$ bit occupano già $\frac34$ dell'albero e le tre da $3$ bit altri $\frac38$: in tutto $\frac98>1$ prima ancora di aggiungere quelle da $4$ e $5$ bit.

(2) Bit rate minimo

Il flusso di informazione è l'entropia per campione per i campioni al secondo (Tasso d'informazione, capacità di canale e teorema di ShannonUna sorgente che emette un simbolo ogni $T$ secondi ha tasso d'informazione $R=\frac{H_s}T$ [bit/s] ($H_s$ entropia per simbolo); un canale ha tasso $R(g)=\frac{I_s(x;y)}T\le R(x)$. La capacità è il massimo del tasso del canale su tutte le statistiche d'ingresso, $C=\max_{p_x}\frac{I(x;y)}T$ per un canale senza memoria. Teorema di Shannon: se il tasso nominale della sorgente è $R\le C$ esiste un codice di canale con probabilità d'errore piccola a piacere, se $R>C$ no. Capacità: BSC $C=\frac1T[1-h(P_{bit})]$, canale a cancellazione $C=\frac{1-\alpha}T$, AWGN reale $C=\frac1{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)$; canali in parallelo sommano le capacità.Tasso d'informazione, capacità di canale e teorema di Shannon →). Calcolando ogni coppia di valori con la stessa probabilità:

$$H=0{,}4322+0{,}6644+0{,}8211+0{,}9288=2{,}8464\ \text{bit per campione}.$$ Per il teorema di Shannon sulla codifica di sorgente nessun codice scende sotto $H$ bit per campione, e a $F_s=100$ kHz campioni al secondo il bit rate minimo è $$R_{\min}=F_sH=100\ \text{kHz}\cdot2{,}8464=284{,}64\ \text{kbit/s}$$ (la soluzione del corso arrotonda a $2{,}85$ bit e $285$ kbit/s). Rispetto ai $300$ kbit/s della codifica a lunghezza fissa ($3$ bit) c'è un margine del $5\%$.

(3) Codice di Huffman

Si uniscono i due nodi meno probabili a ogni passo (probabilità ordinate: $0{,}20;0{,}20;0{,}15;0{,}15;0{,}10;0{,}10;0{,}05;0{,}05$).

Un codice che ne risulta: $q_4\to00$, $q_1\to010$, $q_6\to011$, $q_2\to101$, $q_5\to110$, $q_3\to111$, $q_0\to1000$, $q_7\to1001$ (lunghezze $2,3,3,3,3,3,4,4$ per $q_4,q_1,q_6,q_2,q_5,q_3,q_0,q_7$).

$$L_y=0{,}20\cdot2+(0{,}10+0{,}10+0{,}15+0{,}15+0{,}20)\cdot3+(0{,}05+0{,}05)\cdot4=0{,}40+2{,}10+0{,}40=2{,}90\ \text{bit},$$ controllo con i nodi interni: $0{,}10+0{,}20+0{,}25+0{,}35+0{,}40+0{,}60+1=2{,}90$ ✓. Vale $H=2{,}846\le2{,}90<3{,}846$ ✓ e l'efficienza è $0{,}981$. Le lunghezze del punto 1 ($2,2,2,3,3,3,4,5$), impossibili per Kraft, non sono quelle del codice ottimo.

(4) Bit-rate sul canale con Hamming $(7,4)$

Con la codifica a lunghezza fissa gli $8$ livelli usano $\log_28=3$ bit, quindi all'uscita dell'ADC ci sono $3\cdot100$ kHz $=300$ kbit/s. Il codice di Hamming $(7,4)$ ha rate $\frac47$: ogni $4$ bit di informazione diventano $7$ (gruppi di bit che attraversano più campioni), quindi $$R_{\text{canale}}=300\ \text{kbit/s}\cdot\frac74=525\ \text{kbit/s}.$$ La probabilità d'errore sul bit del canale è $P_{bit}=10^{-3}$: è il dato del punto 5.

(5) Attenuazione massima con la 16-QAM

Periodo di simbolo. La 16-QAM porta $\log_216=4$ bit per simbolo: il symbol-rate è $\frac{525\ \text{kbit/s}}4=131{,}25$ ksimboli/s e $$T=\frac{4}{525\cdot10^3\ \text{bit/s}}=7{,}619\ \mu\text{s}.$$

Energia in trasmissione. L'impulso è rettangolare di ampiezza $2$ V e durata $T$: $E_{h_{Tx}}=A^2T=4\cdot7{,}619\cdot10^{-6}=3{,}048\cdot10^{-5}$ V$^2$s.

Condizione sull'SNR. Con codifica di Gray la probabilità d'errore sul bit della 16-QAM è circa $P_{bit}\simeq\frac{P(E)}{\log_2M}=\frac{P(E)}4$ e, per la probabilità d'errore di simbolo (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 →), $$P(E)\simeq4\left(1-\frac1{\sqrt{16}}\right)Q(x)=3\,Q(x),\qquad x=\sqrt{\frac{E_s}{\sigma_I^2}\cdot\frac3{2(M-1)}}=\sqrt{\frac{E_s}{10\,\sigma_I^2}},$$ con $E_s$ energia media di simbolo e $\sigma_I^2$ varianza del rumore per dimensione. Dunque $P_{bit}\simeq\frac34Q(x)$. Imponendo $P_{bit}=10^{-3}$ si ha $Q(x)=1{,}333\cdot10^{-3}$, quindi $x=3{,}00$ ($Q(3)=1{,}35\cdot10^{-3}$) e $$x^2=\frac{E_s}{10\sigma_I^2}=9\ \Rightarrow\ E_s=90\,\sigma_I^2=90\cdot10^{-10}=9{,}0\cdot10^{-9}\ \text{V}^2\text{s}\quad(\text{energia media in ricezione}).$$ (Con la formula esatta, che include il termine in $Q^2$, si trova $x=3{,}0035$ e $E_s=9{,}02\cdot10^{-9}$: lo stesso risultato.)

Attenuazione. Nella 16-QAM l'energia media è $E_s=\frac{M-1}3E_{h}=5E_{h}$, dove $E_{h}$ è l'energia dell'impulso (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 →). All'ingresso del decisore l'energia dell'impulso minima è quindi $E_{h,\text{rx}}=\frac{E_s}5=1{,}80\cdot10^{-9}$ V$^2$s. L'attenuazione è il rapporto tra l'energia (o potenza) in trasmissione e in ricezione, e il massimo valore ammesso è quello per cui $E_{h,\text{rx}}$ scende al minimo richiesto: $$a_{\max}=\frac{E_{h_{Tx}}}{E_{h,\text{rx}}}=\frac{3{,}048\cdot10^{-5}}{1{,}80\cdot10^{-9}}=1{,}69\cdot10^4,\qquad(a_{\max})_{\text{dB}}=10\log_{10}\left(1{,}69\cdot10^4\right)=42{,}3\ \text{dB}.$$

Differenza con la soluzione del corso. La soluzione riporta $35{,}3$ dB, ottenuti dividendo $E_{h_{Tx}}=3{,}05\cdot10^{-5}$ per $9\cdot10^{-9}$, cioè confrontando l'energia dell'impulso trasmesso con l'energia media di simbolo $E_s=9\cdot10^{-9}$ (la quantità che compare in $x^2=\frac{E_s}{10\sigma_I^2}$): le due grandezze differiscono per il fattore $\frac{M-1}3=5$ ($7$ dB). Con le definizioni del corso ($E_s=5E_h$ per la 16-QAM) l'attenuazione massima è $42{,}3$ dB. In alternativa si può confrontare l'energia media in trasmissione, $5E_{h_{Tx}}=1{,}52\cdot10^{-4}$, con quella in ricezione, $9\cdot10^{-9}$: si ottiene $1{,}69\cdot10^4$ come sopra.

(Verificato con Python: $K=0{,}05$, Kraft $=39/32$, $H=2{,}84644$, $R_{\min}=284{,}64$ kbit/s, Huffman $L_y=2{,}9$ con somma dei nodi uguale, $x=3{,}0038$ per $\frac34Q(x)=10^{-3}$, $E_s=9{,}02\cdot10^{-9}$, $a=1{,}689\cdot10^4=42{,}28$ dB.)

Errori comuni

• Dire che esiste un codice perché "ci sono otto simboli e otto lunghezze": va verificata la somma di Kraft.
• Per il bit rate minimo, usare i $300$ kbit/s della lunghezza fissa o l'entropia senza il fattore $F_s$.
• Moltiplicare il bit-rate per $\frac47$ invece di $\frac74$: il codice aggiunge bit.
• Per la 16-QAM, usare $\log_2M=4$ bit per simbolo per il periodo di simbolo, ma poi dimenticare di usare $P_{bit}=\frac{P(E)}4$.
• Confondere energia dell'impulso e energia media di simbolo ($E_s=\frac{M-1}3E_h$): è l'errore che porta ai $35{,}3$ dB.