Esercizio - Quattro domande brevi su entropia, informazione, M-M-3 e quantizzazione (simulazione d'esame 2012)

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (simulazione d'esame 2012, esercizio 1: rispondere con al massimo $80$ parole per risposta).

1. Una variabile aleatoria discreta $x$ ha alfabeto $\mathcal A_x=\{A,B,C,D,E\}$ e $p_A=0{,}36$. Quale scelta delle probabilità degli altri simboli massimizza l'entropia $H(x)$ e quanto vale in questo caso?
2. Nell'insieme degli eventi $\mathcal F$, la funzione $P$ associa a ogni evento la sua probabilità. Scrivere la definizione di informazione di un evento e mostrare che soddisfa: (i) meno probabile l'evento, più informativo; (ii) l'informazione portata da due eventi indipendenti che accadono insieme è la somma dei loro valori di informazione.
3. Un sistema a coda M/M/3 riceve $2$ clienti al secondo. La probabilità di accodamento all'arrivo è $C=91{,}14\,\%$ e il numero medio di clienti nella parte di accodamento è $18{,}227$. Il sistema è stabile? Qual è il tempo medio che un cliente passa nella parte di accodamento?
4. Un segnale analogico è campionato ogni secondo. I campioni hanno ampiezze che sono variabili aleatorie indipendenti $a_1,a_2,\dots$, con $a_j=(x_j)^2$ e $x_j$ gaussiana a media nulla e deviazione standard $3$ V. I valori $a_j$ sono quantizzati con un quantizzatore a $16$ bit che ottiene un SNR di $82{,}2$ dB. Quanti bit servono per ottenere un SNR di quantizzazione di almeno $95$ dB?

Teoria usata: Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →, Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, Sistemi a coda M-G-1 e formula di LittleMisure di un sistema a coda: occupazione $x=q+z$, tempi $s=w+y$, traffico offerto $G=\frac\lambda\mu$, fattore di carico $\rho=\frac\lambda{m\mu}$, throughput $\eta$ e throughput normalizzato $S=\frac\eta\mu$. Il sistema senza blocco è stabile se $\rho<1$ e allora $\eta=\lambda$, altrimenti $\eta=m\mu$. La formula di Little $E[x]=\lambda E[s]$ vale sempre (anche per la sola coda, $E[q]=\lambda E[w]$, e per il servizio, $E[z]=\lambda E[y]$). Per arrivi di Poisson e servizio generale (M/G/1) la formula di Pollaczek-Khinchin dà $E[w]=\frac{\lambda E[y^2]}{2(1-\rho)}$: con servizio esponenziale si ritrova l'M/M/1, con servizio costante (M/D/1) l'attesa si dimezza, $E[w]=\frac{\rho}{2\mu(1-\rho)}$.Sistemi a coda M-G-1 e formula di Little →, Quantizzazione e rumore di quantizzazioneIl quantizzatore mappa ogni campione reale su uno dei $L=2^b$ livelli. Il quantizzatore uniforme mid-riser ha passo $\Delta=\frac{2v_{sat}}{L}$, soglie multiple di $\Delta$ e livelli multipli dispari di $\frac\Delta2$. L'errore $e_q=a_q-a$ è granulare (in $[-\frac\Delta2,\frac\Delta2]$, circa uniforme, potenza $\frac{\Delta^2}{12}$) o di saturazione (fuori da $[-v_{sat},v_{sat}]$, trascurabile se $P_{sat}$ è piccola). L'SNR è $\Lambda_q=\frac{M_a}{M_{e_q}}$ e, con saturazione trascurabile, $[\Lambda_q]{dB}=6{,}02,b+4{,}77-20\log{10}\frac{v_{sat}}{\sigma_a}$: $+6$ dB per ogni bit.Quantizzazione e rumore di quantizzazione →, Campionamento e conversione analogico-digitalePer trasmettere un segnale analogico $a(t)$ con un sistema digitale lo si trasforma in bit: filtro anti-aliasing, campionatore ($T_s=\frac1{F_s}$, $F_s\ge2B$), quantizzatore su $L=2^b$ livelli, mappa livello $\to$ $b$ bit, serializzatore. Il bit-rate nominale è $R_b=bF_s$. Campionare è reversibile (con un filtro interpolatore, in pratica un holder) se $F_s\ge2B$; quantizzare invece perde informazione in modo irreversibile. Al ricevitore si ripercorre la catena al contrario (D/A).Campionamento e conversione analogico-digitale →.

1. Entropia massima con $p_A$ fissata

L'entropia è $H=-\sum_ip_i\log_2p_i$, con $p_A=0{,}36$ fissata e $p_B+p_C+p_D+p_E=1-0{,}36=0{,}64$. Il termine di $A$ è costante: $-0{,}36\log_20{,}36=0{,}531$. Resta da massimizzare $-\sum_{i\ne A}p_i\log_2p_i$ con somma fissata. Per la concavità di $-x\log_2x$ (disuguaglianza di Jensen, Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →) la somma è massima quando i quattro simboli sono equiprobabili: $$p_B=p_C=p_D=p_E=\frac{0{,}64}4=0{,}16.$$ Valore: $$H_{max}=-0{,}36\log_20{,}36-4\cdot0{,}16\log_20{,}16=0{,}531+0{,}64\cdot2{,}644=0{,}531+1{,}692=2{,}223\ \text{bit}.$$ (Il massimo assoluto con $5$ simboli, $\log_25=2{,}322$ bit, richiederebbe $p_A=0{,}2$.)

2. Definizione di informazione

Definizione. L'informazione (autoinformazione) di un evento $A$ è $$i(A)=-\log_2P(A)=\log_2\frac1{P(A)}\quad[\text{bit}].$$ (i) Meno probabile $\Rightarrow$ più informativo. Se $P(A_1)<P(A_2)$ allora $\frac1{P(A_1)}>\frac1{P(A_2)}$ e, poiché $\log_2$ è crescente, $i(A_1)>i(A_2)$. Casi limite: l'evento certo ($P=1$) ha $i=0$; un evento con probabilità $\to0$ ha informazione $\to\infty$.

(ii) Additività. Se $A$ e $B$ sono indipendenti, $P(A\cap B)=P(A)P(B)$, quindi $$i(A\cap B)=-\log_2\big[P(A)P(B)\big]=-\log_2P(A)-\log_2P(B)=i(A)+i(B),$$ perché il logaritmo trasforma prodotti in somme (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →). È la proprietà che rende il logaritmo la funzione "giusta": è, di fatto, l'unica funzione monotona di $P$ con questa additività.

Esempio. Due lanci di moneta ($P=\frac12$ ciascuno): $i=1+1=2$ bit, uguale all'informazione dell'evento "testa-testa" $P=\frac14$, $-\log_2\frac14=2$ bit.

3. M/M/3: stabilità e tempo di accodamento

Dati: $\lambda=2$ clienti/s, $m=3$, $C=0{,}9114$, $E[q]=18{,}227$ (numero medio di clienti nella parte di attesa). Per l'M/M/$m$ (Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m →, con $G=\lambda/\mu$ il traffico offerto e $\rho=G/m$): $E[q]=\dfrac{C\,G}{m-G}$. Quindi $$\frac{G}{m-G}=\frac{E[q]}C=\frac{18{,}227}{0{,}9114}=20\ \Rightarrow\ G=20(3-G)\ \Rightarrow\ G=\frac{60}{21}=2{,}857.$$ Fattore di carico $\rho=G/m=0{,}9524<1$: il sistema è stabile (la condizione è $\lambda<m\mu$). Si ricava anche $\mu=\lambda/G=2/2{,}857=0{,}7$ clienti/s per servitore, cioè $m\mu=2{,}1>\lambda=2$.

Tempo medio nella parte di accodamento. Per la formula di Little applicata alla sola coda (Sistemi a coda M-G-1 e formula di LittleMisure di un sistema a coda: occupazione $x=q+z$, tempi $s=w+y$, traffico offerto $G=\frac\lambda\mu$, fattore di carico $\rho=\frac\lambda{m\mu}$, throughput $\eta$ e throughput normalizzato $S=\frac\eta\mu$. Il sistema senza blocco è stabile se $\rho<1$ e allora $\eta=\lambda$, altrimenti $\eta=m\mu$. La formula di Little $E[x]=\lambda E[s]$ vale sempre (anche per la sola coda, $E[q]=\lambda E[w]$, e per il servizio, $E[z]=\lambda E[y]$). Per arrivi di Poisson e servizio generale (M/G/1) la formula di Pollaczek-Khinchin dà $E[w]=\frac{\lambda E[y^2]}{2(1-\rho)}$: con servizio esponenziale si ritrova l'M/M/1, con servizio costante (M/D/1) l'attesa si dimezza, $E[w]=\frac{\rho}{2\mu(1-\rho)}$.Sistemi a coda M-G-1 e formula di Little →): $E[q]=\lambda\,E[w]$, quindi $$E[w]=\frac{E[q]}\lambda=\frac{18{,}227}2=9{,}11\ \text{s}.$$ Controllo con la formula diretta $E[w]=\dfrac C{m\mu-\lambda}=\dfrac{0{,}9114}{2{,}1-2}=9{,}11$ s ✓. È un tempo lungo perché $\rho=0{,}95$: il sistema è quasi al limite.

4. Quanti bit servono per $95$ dB

Per un quantizzatore uniforme senza saturazione, l'SNR in dB cresce di $20\log_{10}2=6{,}02$ dB per ogni bit in più, a parità di $v_{sat}$ e di distribuzione del segnale: $$[\Lambda_q]_{dB}=6{,}02\,b+4{,}77-20\log_{10}\frac{v_{sat}}{\sigma_a}.$$ Il segnale $a_j=x_j^2$ non è gaussiano (è sempre $\ge0$) ma la formula non lo richiede: per qualunque segnale, con la saturazione trascurabile e $v_{sat}$ fissato, l'unica dipendenza da $b$ è il termine $6{,}02\,b$. Quindi, indicando con $K$ il resto, con $b=16$: $82{,}2=6{,}02\cdot16+K\Rightarrow K=82{,}2-96{,}32=-14{,}12$ dB. Si vuole $$6{,}02\,b-14{,}12\ge95\ \Rightarrow\ b\ge\frac{109{,}12}{6{,}02}=18{,}13\ \Rightarrow\ b=19$$ (si arrotonda per eccesso). Controllo: con $18$ bit l'SNR è $82{,}2+2\cdot6{,}02=94{,}24<95$ dB (insufficiente); con $19$ bit è $82{,}2+3\cdot6{,}02=100{,}26$ dB $\ge95$ ✓.

Risposta: $19$ bit (cioè $3$ bit in più: servono $12{,}8$ dB in più, e $12{,}8/6{,}02=2{,}13$ bit).