Esercizio - canale binario con rumore aleatorio, capacità e Huffman sulle triplette (secondo compitino dell'11 gennaio 2019, es. 90)

---

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-2), 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 → (punto 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 → (punto 3), 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 4), 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 5).

(1) Probabilità di transizione e tipo di canale

Il ricevitore non conosce $W$, quindi il canale visto da $X$ a $Y$ si ottiene marginalizzando su $W$ con la formula delle probabilità totali. Poiché $W$ è indipendente da $X$, $P(W=w|X=x)=p_W(w)$ ($p_W(0)=0{,}3$, $p_W(1)=0{,}7$): $$P(Y=0|X=0)=P(Y=0|W=0,X=0)p_W(0)+P(Y=0|W=1,X=0)p_W(1)=0{,}8\cdot0{,}3+0{,}6\cdot0{,}7=0{,}24+0{,}42=0{,}66,$$ $$P(Y=1|X=1)=0{,}8\cdot0{,}3+0{,}6\cdot0{,}7=0{,}66.$$ Per differenza ($P(Y=1|X=0)=1-0{,}66$, e allo stesso modo per $X=1$): $P(Y=1|X=0)=P(Y=0|X=1)=0{,}34$. Verifica diretta: $P(Y=1|X=0)=0{,}2\cdot0{,}3+0{,}4\cdot0{,}7=0{,}06+0{,}28=0{,}34$ ✓.

$$P(Y=i|X=j)=\begin{cases}0{,}66&i=j\\0{,}34&i\ne j.\end{cases}$$ Il canale è binario simmetrico con probabilità d'errore $P_{bit}=0{,}34$. È senza memoria se la variabile $W$ viene estratta in modo indipendente a ogni uso del canale (ogni simbolo ha il suo valore di $W$, a monte indipendente dagli altri): la soluzione del corso assume questo. (Se invece $W$ restasse fissa per tutti gli usi, i simboli sarebbero correlati attraverso $W$ e il canale avrebbe memoria.)

(2) Capacità e ingresso ottimo

Per un BSC senza memoria, $H(Y|X)=h(P_{bit})$ non dipende dall'ingresso, e $H(Y)$ è massima ($1$ bit) 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 →). La capacità si raggiunge quindi con $P(X=0)=P(X=1)=\frac12$ ed è $$C=\frac{1-h(0{,}34)}T,\qquad h(0{,}34)=0{,}34\log_2\tfrac1{0{,}34}+0{,}66\log_2\tfrac1{0{,}66}=0{,}5292+0{,}3957=0{,}9248,$$ $$C=\frac{1-0{,}9248}{0{,}2\cdot10^{-3}\ \text{s}}=\frac{0{,}07518}{0{,}2\cdot10^{-3}\ \text{s}}=375{,}9\ \text{bit/s}\simeq376\ \text{bit/s}.$$ (Controllo numerico: massimizzando $I(X;Y)$ sulla densità d'ingresso, il massimo è in $P(X=0)=0{,}5$ e vale $0{,}07518$ bit per uso.)

Osservazione. Se il ricevitore conoscesse $W$, avrebbe due BSC: con $W=0$ ($P_{bit}=0{,}2$) $C=0{,}2781$ e con $W=1$ ($P_{bit}=0{,}4$) $C=0{,}0290$ bit per uso, e in media $0{,}3\cdot0{,}2781+0{,}7\cdot0{,}0290=0{,}1038$ bit per uso ($519$ bit/s), più dei $0{,}0752$ ($376$ bit/s) del canale con $W$ ignoto: sapere in quale stato è il canale vale circa $143$ bit/s.

(3) Codice di Huffman per le triplette $[X,Y,W]$

Con $X$ uniforme ($P(X=x)=\frac12$) e $W$ indipendente da $X$, la probabilità di ogni tripletta è $$P(x,y,w)=P(x)\,p_W(w)\,P(y|x,w).$$ Si ha $P(x)p_W(0)=0{,}5\cdot0{,}3=0{,}15$ e $P(x)p_W(1)=0{,}5\cdot0{,}7=0{,}35$, da moltiplicare per $0{,}8$ o $0{,}2$ (se $w=0$, $y=x$ o $y\ne x$) e per $0{,}6$ o $0{,}4$ (se $w=1$):

La somma è $2(0{,}12+0{,}03+0{,}21+0{,}14)=1$ ✓. Huffman, unendo i due nodi meno probabili a ogni passo:

Un codice ottenuto:

$$L_y=0{,}42\cdot2+(0{,}12+0{,}14+0{,}14)\cdot3+0{,}12\cdot4+0{,}06\cdot5=0{,}84+1{,}20+0{,}48+0{,}30=2{,}82\ \text{bit},$$ controllo con i nodi interni: $0{,}06+0{,}18+0{,}26+0{,}32+0{,}42+0{,}58+1=2{,}82$ ✓.

(4) Raggiunge il limite di Shannon?

Il limite inferiore è l'entropia delle triplette. Poiché ogni valore compare due volte con la stessa probabilità, $$H(X,Y,W)=2\left[0{,}12\log_2\tfrac1{0{,}12}+0{,}03\log_2\tfrac1{0{,}03}+0{,}21\log_2\tfrac1{0{,}21}+0{,}14\log_2\tfrac1{0{,}14}\right]=2\left[0{,}3671+0{,}1518+0{,}4728+0{,}3971\right]=2{,}7776\ \text{bit}.$$ Poiché $L_y=2{,}82>2{,}7776$ il codice non raggiunge il limite: l'uguaglianza $L_y=H$ vale solo se tutte le probabilità sono potenze di $\frac12$ (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 →), e qui ($0{,}12$, $0{,}03$, $0{,}14$, $0{,}21$) non lo sono. Vale comunque $2{,}7776\le2{,}82<3{,}7776$ ✓, con efficienza $\frac H{L_y}=0{,}985$. (La soluzione del corso scrive $H=2{,}77$: è $2{,}7776$ arrotondato per difetto.)

(5) Confronti senza calcolare entropie nuove

• $H(Y|X)<H(Y)$ (strettamente minore). $H(Y)-H(Y|X)=I(X;Y)$ (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 →), che è $>0$ perché $X$ e $Y$ non sono indipendenti: $P(Y=0|X=0)=0{,}66\ne P(Y=0|X=1)=0{,}34$, cioè conoscere $X$ cambia la densità di $Y$. L'uguaglianza si avrebbe solo per un canale con $P_{bit}=\frac12$.
• $H(Y|X)<H(X,Y)$ (strettamente minore). Per la regola della catena $H(X,Y)=H(X)+H(Y|X)$ e $H(X)=1$ bit $>0$ ($X$ è uniforme): quindi $H(X,Y)=H(Y|X)+1>H(Y|X)$.

(Come controllo, a calcoli fatti: $H(Y|X)=h(0{,}34)=0{,}9248$, $H(Y)=1$ ($Y$ è uniforme perché $X$ lo è e il canale è un BSC), $H(X,Y)=1+0{,}9248=1{,}9248$ bit: $0{,}9248<1<1{,}9248$ ✓.)

(Verificato con Python: $P(Y|X)=0{,}66/0{,}34$, $C=375{,}9$ bit/s con massimo in $P(X=0)=0{,}5$, Huffman delle triplette $L_y=2{,}82$ con somma dei nodi uguale, $H(X,Y,W)=2{,}77753$.)

Errori comuni

• Usare le probabilità condizionate a $W$ ($0{,}8$ e $0{,}6$) come se il ricevitore conoscesse $W$: va marginalizzata su $W$.
• Scrivere $P(Y=0|X=0)=0{,}3\cdot0{,}8$ senza il secondo termine ($0{,}7\cdot0{,}6$).
• Dire che il canale "ha memoria perché dipende da $W$": $W$ è indipendente a ogni uso, quindi il canale resta senza memoria.
• Assumere un ingresso non uniforme per il BSC: la capacità si ha con ingresso uniforme.
• Dimenticare che le triplette hanno probabilità in coppie uguali: se ne calcolano $4$ e si usano due volte.
• Rispondere "sì" al punto 4 perché $L_y$ è vicina a $H$: il limite si raggiunge solo con probabilità diadiche.