Esercizio - canale binario non simmetrico, informazione mutua, Huffman ed Elias sulle coppie e canale a cancellazione (compito del 10 febbraio 2021, es. 123)

---

Teoria usata: 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 1, 3, 5), 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 → (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 4), Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →. Un esercizio simile sul calcolo di entropie di una sorgente quaternaria: Esercizio 26 · entropia ed efficienza di una sorgente quaternaria e trasformazioni dei simboli (tema d'esame gennaio 2021).

(1) Il canale è binario? È simmetrico?

• a) Binario: ingresso $\{4,9\}$ e uscita $\{0,1\}$ hanno entrambi due valori. Sì.
• b) Simmetrico: un canale binario è simmetrico se $P[y=1|x=a]=P[y=0|x=b]$ per i due ingressi (cioè la probabilità d'errore è la stessa per i due simboli, e la matrice è simmetrica). Qui chiamando "errore" lo scambio dell'uscita attesa: $P[y=1|x=4]=0{,}2$ ma $P[y=0|x=9]=0{,}3$. Non è simmetrico.

(2) Informazione mutua con $P[x=4]=0{,}7$

Si usa $I(x;y)=H(y)-H(y|x)$ (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 →), con $P[x=4]=0{,}7$ e $P[x=9]=0{,}3$.

1. Densità di $y$ (formula delle probabilità totali): $$P[y=0]=0{,}8\cdot0{,}7+0{,}3\cdot0{,}3=0{,}56+0{,}09=0{,}65,\qquad P[y=1]=1-0{,}65=0{,}35.$$
2. $H(y)$: $H(y)=h(0{,}65)=0{,}65\log_2\frac1{0{,}65}+0{,}35\log_2\frac1{0{,}35}=0{,}4040+0{,}5301=0{,}934$ bit.
3. $H(y|x)$: per $x=4$ le uscite hanno probabilità $(0{,}8;0{,}2)$, quindi $H(y|x=4)=h(0{,}2)=0{,}7219$; per $x=9$: $(0{,}3;0{,}7)$, $H(y|x=9)=h(0{,}3)=0{,}8813$. Mediando con $P[x=4]=0{,}7$ e $P[x=9]=0{,}3$: $$H(y|x)=0{,}7\cdot0{,}7219+0{,}3\cdot0{,}8813=0{,}5053+0{,}2644=0{,}770\ \text{bit}.$$
4. Informazione mutua: $I(x;y)=0{,}934-0{,}770=0{,}164\ \text{bit per uso}$.

(La capacità di questo canale, ottenuta massimizzando numericamente $I$ su $P[x=4]$, è $0{,}191$ bit per uso per $P[x=4]=0{,}51$: con $0{,}7$ si resta sotto.)

(3) Densità di $x$ che massimizza $H(y)$

L'entropia di una variabile binaria è massima ($1$ bit) quando le due uscite sono equiprobabili: $P[y=0]=\frac12$. Con $P[x=4]=p$: $$P[y=0]=0{,}8\,p+0{,}3\,(1-p)=0{,}3+0{,}5\,p=\frac12\ \Rightarrow\ p=\frac{0{,}2}{0{,}5}=0{,}4.$$ La densità è $P[x=4]=0{,}4$, $P[x=9]=0{,}6$, con $H(y)=1$ bit. Attenzione: massimizzare $H(y)$ non è lo stesso che massimizzare $I(x;y)$, perché per un canale non simmetrico $H(y|x)$ dipende da $p$: con $p=0{,}4$ si ha $H(y|x)=0{,}4\cdot0{,}7219+0{,}6\cdot0{,}8813=0{,}8176$ e $I=1-0{,}8176=0{,}182$ bit, minore della capacità $0{,}191$ bit (che si ottiene per $p\simeq0{,}51$).

(4) Codice ottimo e codice di Elias per le coppie di uscite

Con $P[x=4]=0{,}7$ si ha $P[y=0]=0{,}65$, $P[y=1]=0{,}35$ (punto 2). Poiché i simboli $x$ sono indipendenti e il canale è senza memoria, anche le uscite $y(nT)$ sono indipendenti, quindi le coppie hanno probabilità prodotto:

(somma $0{,}4225+2\cdot0{,}2275+0{,}1225=1$ ✓).

Huffman. Si uniscono $0{,}1225+0{,}2275=0{,}35$ (coppie $11$ e $01$), poi $0{,}35+0{,}2275=0{,}5775$ (con $10$), poi $0{,}5775+0{,}4225=1$. Il codice è $$00\to0,\quad10\to10,\quad11\to110,\quad01\to111\quad(\text{lunghezze }1,2,3,3).$$ $$L_y=0{,}4225\cdot1+0{,}2275\cdot2+0{,}1225\cdot3+0{,}2275\cdot3=0{,}4225+0{,}455+0{,}3675+0{,}6825=1{,}9275\ \text{bit per coppia},$$ controllo con i nodi interni: $0{,}35+0{,}5775+1=1{,}9275$ ✓. L'entropia della coppia è $2H(y)=1{,}868$ bit, quindi $1{,}868\le1{,}9275<2{,}868$ ✓.

Variante, codice di Elias. Si dispongono le coppie nell'ordine $00,01,10,11$ e si divide $[0,1)$ in segmenti di ampiezza pari alle probabilità; lunghezze $l=\lceil-\log_2P\rceil+1$ (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 →):

Conversione di $m=0{,}21125$ (raddoppiando e prendendo la parte intera): $0{,}4225\to0$, $0{,}845\to0$, $1{,}69\to1$: le prime $3$ cifre sono $001$. Lunghezza media: $$L_E=0{,}4225\cdot3+(0{,}2275+0{,}2275)\cdot4+0{,}1225\cdot5=1{,}2675+1{,}82+0{,}6125=3{,}7\ \text{bit per coppia}.$$ Le parole dipendono dall'ordine in cui si dispongono le coppie (la soluzione del corso ne riporta altre, con lo stesso insieme di lunghezze $3,4,4,5$), ma la lunghezza media è $3{,}7$ bit in ogni caso: quasi il doppio di quella di Huffman ($1{,}9275$).

(5) Capacità del canale a cancellazione

La matrice $\begin{bmatrix}0{,}8&0&0{,}2\\0&0{,}8&0{,}2\end{bmatrix}$ ha, per ciascun ingresso, l'uscita corretta (che coincide con l'ingresso) con probabilità $0{,}8$ e un terzo simbolo $z=2$ con probabilità $0{,}2$, uguale per i due ingressi: è un canale binario con cancellazione con probabilità di cancellazione $\alpha=0{,}2$. La sua capacità, con ingresso uniforme, è (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 →) $$C=\frac{1-\alpha}T=\frac{1-0{,}2}{10^{-3}\ \text{s}}=800\ \text{bit/s}.$$ Perché: $H(z|x)=h(\alpha)$ non dipende dall'ingresso, mentre $H(z)=(1-\alpha)h(P[x=4])+h(\alpha)$, e $I=(1-\alpha)h(P[x=4])$ è massima per $P[x=4]=\frac12$. (Controllo numerico: massimizzando $I$ su $P[x=4]$ si ottiene $0{,}8$ bit per uso in $P[x=4]=0{,}5$.)

(Verificato con Python: $h(0{,}65)=0{,}93407$, $H(y|x)=0{,}76974$, $I=0{,}16433$, $p=0{,}4$, Huffman $L_y=1{,}9275$, Elias $L_E=3{,}7$ con parole $001,1000,1100,11110$, capacità del canale a cancellazione $0{,}8$ bit per uso.)

Errori comuni

• Dire che il canale è simmetrico perché è binario: serve che $P[y=1|x=4]=P[y=0|x=9]$.
• Calcolare $H(y|x)$ senza pesare con $P[x]$ le due entropie delle righe.
• Massimizzare $H(y)$ e chiamare il risultato "capacità": per i canali non simmetrici l'ingresso ottimo per $I$ è diverso.
• Per le coppie, usare $P[y=0]=0{,}8$ (la probabilità condizionata a $x=4$) invece di $P[y=0]=0{,}65$.
• In Elias, usare $\lceil-\log_2P\rceil$ senza il $+1$.
• Per il canale con tre uscite, non riconoscere la cancellazione: le righe sono "identità più una colonna costante".