Esercizio - Kraft-McMillan, Huffman, due canali binari alternati e codice di Hamming (15,11) (compito del 13 febbraio 2026, es. 201)

---

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 → (punti 1-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), 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 4), 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 → e Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset → (punti 5-6). Per 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 →.

Le probabilità sommano a $2\cdot\frac{8+4+3+1}{32}=1$ ✓. Per comodità si indica $P(q_k)$ in trentaduesimi: $q_0:1,\ q_1:3,\ q_2:4,\ q_3:8,\ q_4:8,\ q_5:4,\ q_6:3,\ q_7:1$.

(1) Esiste un codice a prefisso con le lunghezze $2,3,3,3,4,4,5,5$?

Per 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 →) esiste un codice a prefisso binario con quelle lunghezze se e solo se $\sum_i2^{-l_i}\le1$: $$\frac14+3\cdot\frac18+2\cdot\frac1{16}+2\cdot\frac1{32}=\frac{8+12+4+2}{32}=\frac{26}{32}=0{,}8125<1.$$ Sì, esiste. Migliore assegnazione: per minimizzare la lunghezza media si danno le parole più corte ai simboli più probabili (ordinando le probabilità in modo decrescente e le lunghezze in modo crescente, altrimenti un semplice scambio abbasserebbe $L_y$):

La coppia di probabilità uguali $8/32,8/32$ riceve una lunghezza $2$ e una $3$; è indifferente quale. La lunghezza media è $$L_y=\frac{8\cdot2+8\cdot3+4\cdot3+4\cdot3+3\cdot4+3\cdot4+1\cdot5+1\cdot5}{32}=\frac{16+24+12+12+12+12+5+5}{32}=\frac{98}{32}=3{,}0625\ \text{bit}.$$

(2) Bit rate minimo

Il flusso di informazione prodotto dal convertitore è l'entropia per campione moltiplicata per i campioni al secondo. Frequenza di campionamento $F_s=\frac1{10^{-5}\ \text{s}}=100$ kHz. L'entropia dei valori quantizzati è $$H=2\left[\tfrac8{32}\log_2\tfrac{32}8+\tfrac4{32}\log_2\tfrac{32}4+\tfrac3{32}\log_2\tfrac{32}3+\tfrac1{32}\log_2\tfrac{32}1\right]=2\left[0{,}5+0{,}375+0{,}3202+0{,}15625\right]=2{,}7028\ \text{bit}.$$ (Qui $\tfrac8{32}\log_24=0{,}5$, $\tfrac4{32}\log_28=0{,}375$, $\tfrac3{32}\log_2\tfrac{32}3=\tfrac3{32}\cdot3{,}4150=0{,}3202$, $\tfrac1{32}\cdot5=0{,}15625$: la somma è $1{,}3514$ e raddoppiata dà $2{,}7028$.) Per il teorema di Shannon sulla codifica di sorgente nessun codice può usare in media meno di $H$ bit per campione, quindi il bit rate minimo è $$R_{\min}=F_sH=100\ \text{kHz}\cdot2{,}7028\ \text{bit}=270{,}28\ \text{kbit/s}.$$ (Per confronto, la codifica a lunghezza fissa con $\log_28=3$ bit darebbe $300$ kbit/s.)

(3) Codice ottimo: Huffman

(I numeri sono in trentaduesimi. Al passo 2 i nodi minimi sono $2\,(A)$ e un $3$ ($q_1$ o $q_6$); si sceglie $q_1$, la scelta opposta dà lo stesso $L_y$.) Etichettando i rami $0/1$ si ottiene, per esempio,

$$L_y=\frac{(8+8)\cdot2+(4+4+3)\cdot3+3\cdot4+(1+1)\cdot5}{32}=\frac{32+33+12+10}{32}=\frac{87}{32}=2{,}71875\ \text{bit}.$$ Controllo con i nodi interni (in trentaduesimi): $2+5+7+9+15+17+32=87$ ✓. Rispetto al punto 1 ($3{,}0625$) si risparmia mezzo bit; il limite $H=2{,}7028\le2{,}7188<3{,}7028$ ✓, efficienza $\eta=0{,}994$.

(4) Massimo periodo di bit sui due canali

Con la codifica a lunghezza fissa minima i $8$ livelli usano $\log_28=3$ bit, quindi il flusso all'uscita dell'ADC è $3\cdot100$ kHz $=300$ kbit/s. I bit vengono mandati alternativamente su due canali: ciascun canale riceve metà dei bit, cioè $$R_b=\frac{300\ \text{kbit/s}}2=150\ \text{kbit/s}$$ di informazione. Ogni canale è un BSC senza memoria (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 →) con capacità per uso $1-h(P_{bit})$: $$C_1T_c=1-h(10^{-3})=1-0{,}01141=0{,}98859,\qquad C_2T_c=1-h(10^{-2})=1-0{,}08079=0{,}91921.$$ Se si introduce una codifica di canale di rate $\frac kn$ prima di ciascun canale, e se $T_c$ è il periodo di bit sul canale (cioè dopo il codificatore), le parole di $n$ bit portano $k$ bit di informazione: $R_b=\frac kn\cdot\frac1{T_c}$, cioè $\frac kn=R_bT_c$. Per il teorema di Shannon una probabilità d'errore residua piccola a piacere è possibile se $\frac kn\le C\,T_c=1-h(P_{bit})$ per entrambi i canali, quindi $$R_bT_c\le\min\{0{,}98859;\ 0{,}91921\}=0{,}91921\quad\Rightarrow\quad T_c\le\frac{0{,}91921}{150\ \text{kbit/s}}=6{,}128\ \mu\text{s}.$$ Il canale peggiore (quello con $10^{-2}$) fissa il limite: $T_{c,\max}=6{,}13\ \mu$s, cioè un bit ogni $6{,}13\ \mu$s per canale ($163$ kbit/s per canale).

Differenza con la soluzione del corso. La soluzione del corso riporta $T_c<4{,}0854\cdot10^{-5}$ s. Il valore corretto, con gli stessi dati ($0{,}9192$ e $150$ kbit/s), è $\frac{0{,}9192}{150\cdot10^3}=6{,}128\cdot10^{-6}$ s: il numero riportato è $6{,}667$ volte più grande ed è incompatibile con quei dati (con $T_c=40{,}9\ \mu$s il rate del codice sarebbe $R_bT_c=6{,}13>1$, impossibile). La soluzione del corso usa comunque la stessa formula, $R_b<\min C_i$.

(5) Hamming $(15,11)$: bit-rate, distanza minima e probabilità di $d_{\min}$ errori

Un codice di Hamming con $n=15=2^4-1$ ha $n-k=4$ bit di parità e $k=11$ bit di informazione (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 →). Il rate è $\frac{11}{15}$. I $300$ kbit/s di informazione (sul flusso complessivo) diventano $$300\ \text{kbit/s}\cdot\frac{15}{11}=409{,}09\ \text{kbit/s}\quad(\text{circa }204{,}5\text{ kbit/s per canale}).$$ Tutti i codici di Hamming hanno distanza minima $d_{\min}=3$ (rilevano $2$ errori e ne correggono $1$). Sul canale peggiore ($P_{bit}=10^{-2}$) la probabilità di avere esattamente $3$ errori in una sequenza di $15$ bit è $$P[3\ \text{errori}]=\binom{15}3P_{bit}^3(1-P_{bit})^{12}=455\cdot10^{-6}\cdot0{,}99^{12}=455\cdot10^{-6}\cdot0{,}88638=4{,}033\cdot10^{-4}.$$ Qui $\binom{15}3=\frac{15\cdot14\cdot13}{6}=455$.

(6) Matrice di controllo e decodifica

Le colonne della matrice di controllo di parità $H$ ($4\times15$) di un codice di Hamming sono tutte le $15$ sequenze binarie non nulle di lunghezza $4$, ciascuna una sola volta. In forma sistematica $H=[\,A\,|\,I_4\,]$ le ultime quattro colonne sono quelle di peso $1$ (matrice identità) e le prime undici sono le sequenze di peso almeno $2$. Una scelta valida è

$$H=\begin{bmatrix}1&0&1&1&1&1&1&1&0&0&0&1&0&0&0\\1&1&0&1&1&1&0&0&1&1&0&0&1&0&0\\1&1&1&0&1&0&1&0&1&0&1&0&0&1&0\\1&1&1&1&0&0&0&1&0&1&1&0&0&0&1\end{bmatrix}.$$

(Le colonne $1$-$11$ sono $[1,1,1,1]^T,[0,1,1,1]^T,[1,0,1,1]^T,[1,1,0,1]^T,[1,1,1,0]^T,[1,1,0,0]^T,[1,0,1,0]^T,[1,0,0,1]^T,[0,1,1,0]^T,[0,1,0,1]^T,[0,0,1,1]^T$ e coprono tutti i pesi $\ge2$; le altre $4$ sono $I_4$.)

Decodifica. La sindrome di $\xi=[0\ \dots\ 0\ 1\ 1\ 1\ 1]^T$ (con bit pari a $1$ solo nelle posizioni $12,13,14,15$) è la somma delle colonne $12,\dots,15$ di $H$, che sono le colonne di $I_4$: $$s=H\xi=[1,0,0,0]^T+[0,1,0,0]^T+[0,0,1,0]^T+[0,0,0,1]^T=[1,1,1,1]^T.$$ La sindrome non è nulla, quindi $\xi$ non è una parola di codice. Un codice di Hamming corregge un errore: la sindrome è uguale alla colonna di $H$ nella posizione dell'errore. $[1,1,1,1]^T$ è la colonna $1$ di $H$, quindi l'errore più probabile (coset leader, Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →) è $e=[1\ 0\ \dots\ 0]^T$ e la parola decodificata è $$\gamma=\xi+e=[1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\ 1\ 1]^T.$$ Verifica: $H\gamma=$ colonna $1$ + colonne $12$-$15$ $=[1,1,1,1]^T+[1,1,1,1]^T=\mathbf0$ ✓: $\gamma$ è una parola di codice (i primi $11$ bit, $[1,0,\dots,0]$, sono l'informazione e gli ultimi $4$, $1111$, la parità).

(Verificato con Python: Kraft $=26/32$, $L_y$ del punto 1 $=3{,}0625$, $H=2{,}70282$, Huffman $L_y=2{,}71875$, $1-h(10^{-3})=0{,}98859$, $1-h(10^{-2})=0{,}91921$, $T_{c,\max}=6{,}128\ \mu$s, $\binom{15}3(10^{-2})^3(0{,}99)^{12}=4{,}033\cdot10^{-4}$; la matrice $H$ ha come colonne tutte le $15$ sequenze non nulle e $H\gamma=0$.)

Errori comuni

• Per Kraft, dire "$<1$ quindi il codice è ottimo": esprime solo l'esistenza di un codice a prefisso con quelle lunghezze, non la sua ottimalità.
• Assegnare le lunghezze corte ai simboli meno probabili.
• Usare $\log_28=3$ bit (lunghezza fissa) per il bit rate minimo: il minimo è $F_sH=270{,}28$ kbit/s.
• Al punto 4 prendere la media dei due canali o il canale migliore: serve il peggiore.
• Al punto 4 dimenticare che ciascun canale porta metà dei bit.
• Per la distanza minima dire $d_{\min}=2^{n-k}$ o simili: per i codici di Hamming è sempre $3$.
• Non controllare che la sindrome $[1,1,1,1]^T$ coincida con una colonna di $H$ (qui la prima).