Esercizio - entropia, Kraft-McMillan ternario, Huffman e capacità di due canali binari in cascata (secondo compitino del 14 gennaio 2025, es. 186)

---

Teoria usata: 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 → (punto 1), 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 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), Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua → 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 → (punti 4-6).

(1) Entropia dei valori quantizzati

Il testo dà cinque probabilità; la sesta si ricava dalla normalizzazione (Variabili aleatorie discrete e densità discretaUna variabile aleatoria discreta è una funzione X da Ω in R che assume un insieme finito o numerabile di valori (l'alfabeto); la sua densità discreta p_X(x) = P(X = x) basta a calcolare la probabilità di ogni evento che riguarda X.Variabili aleatorie discrete e densità discreta →): $$P[q_6]=1-\left(\frac13+\frac19+\frac1{27}+\frac1{81}+\frac1{243}\right)=1-\frac{81+27+9+3+1}{243}=1-\frac{121}{243}=\frac{122}{243}=0{,}5021.$$ Si calcolano i termini $P\log_2\frac1P$:

$$H=0{,}5283+0{,}3522+0{,}1761+0{,}0783+0{,}0326+0{,}4991=1{,}667\ \text{bit}.$$ (Si sono usati $\log_2\frac1{3^{-k}}=k\log_23=1{,}585k$.) Con $6$ livelli il massimo possibile è $\log_26=2{,}585$ bit: la distribuzione è molto sbilanciata.

(2) Esiste un codice ternario con le lunghezze $1,1,2,2,2,3$?

Alfabeto ternario, $M_y=3$. Per Kraft-McMillan una codifica decodificabile con lunghezze $l_i$ esiste solo se $\sum_i3^{-l_i}\le1$ (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 →): $$\frac13+\frac13+\frac19+\frac19+\frac19+\frac1{27}=\frac23+\frac39+\frac1{27}=\frac{18+9+1}{27}=\frac{28}{27}=1{,}037>1.$$ La somma supera $1$: non esiste nessuna codifica decodificabile con quelle lunghezze. Si vede sull'albero ternario: due parole di $1$ simbolo occupano $\frac23$ delle foglie, tre da $2$ simboli altri $\frac13$ e non rimane posto per quella da $3$ simboli.

(3) Codice di Huffman binario

Si lavora in $243$-esimi (cioè $q_6=122$, $q_1=81$, $q_2=27$, $q_3=9$, $q_4=3$, $q_5=1$). A ogni passo si uniscono i due nodi meno probabili:

Il codice è uno "scalone": ogni passo aggancia un simbolo al ramo che contiene i meno probabili. Leggendo dalla radice (ramo $1$ a $q_6$, ramo $0$ al resto, e così via):

$$L_y=\frac{122\cdot1+81\cdot2+27\cdot3+9\cdot4+3\cdot5+1\cdot5}{243}=\frac{122+162+81+36+15+5}{243}=\frac{421}{243}=1{,}7325\ \text{bit}.$$ Controllo con i nodi interni: $\frac{4+13+40+121+243}{243}=\frac{421}{243}$ ✓. Rispetto all'entropia: $1{,}667\le1{,}733<2{,}667$ ✓, efficienza $\eta=0{,}962$.

(4) Valore di $p$ che massimizza $H(Y|X)$ con $a<b<\frac12$

Il canale ha, per ingresso $X=0$, uscita $Y=0$ con probabilità $1-a$ e $Y=1$ con probabilità $a$; per $X=1$, uscita $Y=1$ con probabilità $1-b$ e $Y=0$ con probabilità $b$. Per ogni valore dell'ingresso $Y$ è binaria: $$H(Y|X=0)=h(a),\qquad H(Y|X=1)=h(b),$$ dove $h(u)=u\log_2\frac1u+(1-u)\log_2\frac1{1-u}$. Mediando sull'ingresso, con $P[X=0]=p$ (Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua →): $$H(Y|X)=p\,h(a)+(1-p)\,h(b)=\left[h(a)-h(b)\right]p+h(b).$$ È una funzione lineare di $p$. La sua pendenza è $h(a)-h(b)$, negativa: infatti $h$ è strettamente crescente su $\left[0,\frac12\right]$ e $a<b<\frac12$ implica $h(a)<h(b)$. Una funzione lineare decrescente su $[0,1]$ ha il massimo nell'estremo sinistro: $$\boxed{p=0,\qquad H(Y|X)_{\max}=h(b).}$$ Si trasmette sempre $X=1$ (il simbolo con la maggiore probabilità d'errore): l'incertezza residua è quella del canale più rumoroso. Esempio numerico con $a=0{,}1$, $b=0{,}2$: $H(Y|X)=0{,}722$ per $p=0$; $0{,}596$ per $p=\frac12$; $0{,}469$ per $p=1$.

(5) Caso $a=b$: $p$ che massimizza $I(X;Y)$

Con $a=b$ il canale è un binario simmetrico con probabilità d'errore $a$ (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 →). L'informazione mutua è $$I(X;Y)=H(Y)-H(Y|X)=H(Y)-h(a),$$ perché per $a=b$, dal punto 4, $H(Y|X)=p\,h(a)+(1-p)h(a)=h(a)$ non dipende da $p$. Resta da massimizzare $H(Y)$, entropia di una variabile binaria, che vale al più $1$ bit con $P[Y=0]=\frac12$. Con la formula delle probabilità totali: $$P[Y=0]=P[Y=0|X=0]\,p+P[Y=0|X=1](1-p)=(1-a)p+a(1-p)=a+p(1-2a).$$ Imponendo $a+p(1-2a)=\frac12$ si ha $p(1-2a)=\frac12-a=\frac12(1-2a)$, quindi $p=\frac12$ (per $a\ne\frac12$). Dunque $$\boxed{p=\tfrac12,\qquad I_{\max}=1-h(a)\ \text{bit per uso}.}$$ Con $T=10^{-3}$ s la capacità è $C=\frac{1-h(a)}T$ bit/s; per $a=0{,}1$: $1-h(0{,}1)=0{,}531$, cioè $531$ bit/s.

(6) Cascata di due canali binari simmetrici

Il primo canale $X\to Y$ ha probabilità d'errore $a=0{,}1$; il secondo $Y\to Z$ ha anch'esso $a=0{,}1$. Se $Y$ è esatta, $Z$ sbaglia con probabilità $a$; se $Y$ è sbagliata, un secondo errore la corregge. Quindi $Z\ne X$ in due modi esclusivi: errore solo nel primo canale, oppure solo nel secondo: $$P[Z\ne X]=a(1-a)+(1-a)a=2a(1-a)=2\cdot0{,}1\cdot0{,}9=0{,}18.$$ Le probabilità di transizione della cascata sono $P[Z=0|X=0]=(1-a)^2+a^2=0{,}81+0{,}01=0{,}82$ e $P[Z=1|X=0]=0{,}18$, uguali per $X=1$: è ancora un canale binario simmetrico, con probabilità d'errore $0{,}18$. La sua capacità, con periodo di simbolo $10^{-3}$ s, è $$C=\frac{1-h(0{,}18)}{10^{-3}\ \text{s}}=1000\cdot\left(1-0{,}6801\right)=319{,}9\ \text{bit/s}.$$ Con $h(0{,}18)=0{,}18\log_2\frac1{0{,}18}+0{,}82\log_2\frac1{0{,}82}=0{,}4453+0{,}2348=0{,}6801$. La cascata ha capacità minore del singolo canale ($531$ bit/s): ogni stadio aggiunge rumore e l'informazione non può aumentare passando per ulteriori elaborazioni.

(Verificato con Python: $H=1{,}66661$ bit, Kraft ternario $28/27$, Huffman $L_y=421/243=1{,}73251$ con somma dei nodi uguale, $h(0{,}18)=0{,}68008$, capacità massimizzata numericamente (Blahut-Arimoto) $0{,}31992$ bit per uso con ingresso uniforme.)

Errori comuni

• Dimenticare che $q_6$ non è dato: va ricavata dalla normalizzazione.
• Usare Kraft con base $2$ per un codice ternario: la somma è $\sum3^{-l_i}$.
• Concludere da Kraft $>1$ che "basta allungare una parola": no, quelle lunghezze non sono realizzabili.
• Al punto 4, cercare il massimo con la derivata come se fosse concava: $H(Y|X)$ è lineare in $p$, il massimo sta agli estremi.
• Al punto 6, sommare le probabilità d'errore ($0{,}2$) o moltiplicarle: serve $2a(1-a)$, perché un secondo errore ripara il primo.
• Dimenticare di dividere per $T$ nelle capacità in bit/s.