Esercizio - Quattro domande brevi su capacità, TDMA e FDMA, entropia e codice lineare (simulazione d'esame 2013)

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

Testo (simulazione d'esame 2013, esercizio 1: rispondere con meno di $80$ parole).

1. Un canale numerico con simboli di ingresso $0$ e $1$ ha tre possibili simboli di uscita: $0$, $1$ ed errore. Con probabilità $q=0{,}25$ i simboli di ingresso ($0$ e $1$) restano intatti in uscita. Con probabilità $1-q$ (per entrambi) vengono trasformati in errore. Quanto vale la capacità per simbolo di questo canale (cioè la massima informazione mutua)?
2. Un collegamento di capacità $500$ Mbit/s deve essere usato da un numero casuale $N$ di utenti, con $N$ uniformemente distribuito tra $0$ e $200$. Ogni utente invia pacchetti di $L=8$ kbit, generati con tasso $\lambda=300$ pacchetti/s. Trovare la probabilità che il sistema sia stabile con (i) TDMA o (ii) FDMA.
3. Un giovane calciatore brasiliano annuncia che giocherà in Europa il prossimo anno ma non dice la squadra. I giornalisti concordano: probabilità $1/2$ che giochi per l'Arsenal, $1/4$ per il Barcellona, $1/8$ per il Chelsea, $1/16$ per la Juventus, $1/16$ per il Paris Saint Germain. Un giovane giornalista freelance ha scoperto la squadra. Il direttore di un quotidiano sportivo è disposto a pagare la notizia proporzionalmente alla sua informazione, ed è pronto a firmare un assegno da $6000$ euro. Ma, mentre sta per firmare, l'Arsenal annuncia di aver ingaggiato un altro attaccante, il che implica che non ha ingaggiato la stella brasiliana. Quanto valore perde lo scoop?
4. Si consideri una codifica lineare la cui possibile matrice generatrice è $G=\begin{pmatrix}1001010\\0100101\\0011100\end{pmatrix}^T$, con $T$ che indica la matrice trasposta. È un codice sistematico? Scrivere una matrice di controllo di parità. Quanti errori può rivelare questo codice?

Teoria usata: Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →, Accesso al mezzo - ALOHA, CSMA e protocolli deterministiciQuando più nodi condividono il canale serve un protocollo di accesso (MAC): deterministico (TDMA, FDMA, SDMA, CDMA), a richiesta (polling, token) o casuale (ALOHA, CSMA). Con $N_u$ utenti, arrivi di Poisson $\lambda$ ciascuno e pacchetti da $t_P=L/R_b$: TDMA stabile se $N_u\lambda t_P<1$, $m_{delay}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P$; FDMA ha ritardo maggiore di $t_P(N_u/2-1)$. ALOHA puro: intervallo di vulnerabilità $2t_P$, $S=Ge^{-2G}$, $S_{max}=1/(2e)\simeq0{,}18$ per $G=1/2$; slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, $S_{max}=1/e\simeq0{,}37$. ALOHA è intrinsecamente instabile (oltre il massimo il throughput va a $0$). Il carrier sense riduce la vulnerabilità a $\tau_P$ (CSMA), CD interrompe le collisioni, CA (RTS/CTS) è per il wireless; la persistenza (1-, non-, $p$-persistente) può portare il throughput verso il $100,%$.Accesso al mezzo - ALOHA, CSMA e protocolli deterministici →, 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 →, Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →.

1. Canale a cancellazione

Il canale non sbaglia mai un bit: lo lascia intatto con probabilità $q$ o lo sostituisce con il simbolo errore (cancellazione) con probabilità $1-q$. Sia $\pi=P[X=1]$. L'uscita $Y\in\{0,1,e\}$: $P[Y=e]=1-q$ (indipendente da $X$), e se non c'è cancellazione $Y=X$. Allora $$H(Y)=h(1-q)+q\,h(\pi),\qquad H(Y|X)=h(1-q)$$ (l'entropia di $Y$ si scompone: prima si decide se c'è cancellazione, poi, con probabilità $q$, quale valore). Quindi $$I(X,Y)=H(Y)-H(Y|X)=q\,h(\pi),$$ massimo per $\pi=\frac12$ ($h=1$): $$C_s=q=0{,}25\ \text{bit/simbolo}.$$ (Il testo dice che sia lo $0$ sia l'$1$ restano intatti con probabilità $q=0{,}25$ e diventano errore con probabilità $0{,}75$.) Il risultato è intuitivo: solo il $25\,\%$ dei simboli arriva, e porta un bit pieno.

2. Stabilità con TDMA e FDMA

Il tempo di pacchetto sul collegamento è $t_P=\dfrac L{R_b}=\dfrac{8000}{500\cdot10^6}=16\ \mu$s. La condizione di stabilità, identica per TDMA e FDMA, è $N\lambda t_P<1$ (Accesso al mezzo - ALOHA, CSMA e protocolli deterministiciQuando più nodi condividono il canale serve un protocollo di accesso (MAC): deterministico (TDMA, FDMA, SDMA, CDMA), a richiesta (polling, token) o casuale (ALOHA, CSMA). Con $N_u$ utenti, arrivi di Poisson $\lambda$ ciascuno e pacchetti da $t_P=L/R_b$: TDMA stabile se $N_u\lambda t_P<1$, $m_{delay}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P$; FDMA ha ritardo maggiore di $t_P(N_u/2-1)$. ALOHA puro: intervallo di vulnerabilità $2t_P$, $S=Ge^{-2G}$, $S_{max}=1/(2e)\simeq0{,}18$ per $G=1/2$; slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, $S_{max}=1/e\simeq0{,}37$. ALOHA è intrinsecamente instabile (oltre il massimo il throughput va a $0$). Il carrier sense riduce la vulnerabilità a $\tau_P$ (CSMA), CD interrompe le collisioni, CA (RTS/CTS) è per il wireless; la persistenza (1-, non-, $p$-persistente) può portare il throughput verso il $100,%$.Accesso al mezzo - ALOHA, CSMA e protocolli deterministici →): $$N\cdot300\cdot16\cdot10^{-6}=N\cdot4{,}8\cdot10^{-3}<1\ \Rightarrow\ N<208{,}3.$$ Poiché $N\le200$, la condizione è sempre soddisfatta (al massimo $N\lambda t_P=0{,}96<1$): il sistema è stabile per ogni valore di $N$. $$P[\text{stabile}]=1\qquad\text{sia con TDMA sia con FDMA}.$$ La differenza tra TDMA e FDMA è solo nel ritardo, non nella stabilità (TDMA ha una coda con arrivi $N\lambda$ e servizio $1/t_P$, FDMA $N$ code con arrivi $\lambda$ e servizio $1/(Nt_P)$: la condizione è la stessa).

3. Il valore dello scoop

La notizia vale in proporzione alla sua informazione. L'informazione media (entropia) della squadra incognita è $$H=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+2\cdot\frac1{16}\cdot4=0{,}5+0{,}5+0{,}375+0{,}5=1{,}875\ \text{bit}.$$ Dopo l'annuncio dell'Arsenal il giornalista sa che la squadra non è l'Arsenal. Le probabilità condizionate si ottengono rinormalizzando i restanti (eliminando $\frac12$ e dividendo per $\frac12$): $\frac12,\frac14,\frac18,\frac18$ ($\frac14/\frac12$, $\frac18/\frac12$, $\frac1{16}/\frac12$, $\frac1{16}/\frac12$) per Barcellona, Chelsea, Juventus, PSG. La nuova entropia è $$H'=\frac12\cdot1+\frac14\cdot2+2\cdot\frac18\cdot3=0{,}5+0{,}5+0{,}75=1{,}75\ \text{bit}.$$ Lo scoop perde $1{,}875-1{,}75=0{,}125$ bit, cioè una frazione $\dfrac{0{,}125}{1{,}875}=\dfrac1{15}$ del valore: il valore diventa $6000\cdot\dfrac{1{,}75}{1{,}875}=5600$ euro, perde $400$ euro.

4. Il codice lineare

Con la convenzione del corso le colonne di $G$ sono parole di codice: $G$ è $7\times3$ ($n=7$, $k=3$), con colonne $\boldsymbol\gamma_1=1001010$, $\boldsymbol\gamma_2=0100101$, $\boldsymbol\gamma_3=0011100$, cioè $$G=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&0&1\\0&1&1\\1&0&0\\0&1&0\end{pmatrix}.$$ Sistematico? Sì: le prime $k=3$ righe formano $I_3$, quindi $c_j=b_j$ per $j=1,2,3$ (Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →). La matrice di parità è $A=\begin{pmatrix}1&0&1\\0&1&1\\1&0&0\\0&1&0\end{pmatrix}$ ($(n-k)\times k=4\times3$).

Matrice di controllo. $H=[A\mid I_4]$ ($4\times7$): $$H=\begin{pmatrix}1&0&1&1&0&0&0\\0&1&1&0&1&0&0\\1&0&0&0&0&1&0\\0&1&0&0&0&0&1\end{pmatrix}.$$ Controllo $HG=O$: per esempio $H\boldsymbol\gamma_1$: riga $1$ ($c_1+c_3+c_4=1+0+1=0$), riga $2$ ($c_2+c_3+c_5=0+0+0=0$), riga $3$ ($c_1+c_6=1+1=0$), riga $4$ ($c_2+c_7=0+0=0$) ✓ (verificato per tutte le colonne).

Quanti errori rivela. Le $8$ parole sono $0000000,0011100,0100101,0111001,1001010,1010110,1101111,1110011$, con pesi $0,3,3,4,3,4,6,5$: $d_{min}=3$ (minimo peso delle parole non nulle). Il codice rivela fino a $d_{min}-1=2$ errori (e ne corregge $1$, ma non insieme). Conferma con $H$: le colonne sono $\mathbf h_1=1010$, $\mathbf h_2=0101$, $\mathbf h_3=1100$, $\mathbf h_4=1000$, $\mathbf h_5=0100$, $\mathbf h_6=0010$, $\mathbf h_7=0001$: tutte non nulle e distinte (nessuna coppia dipendente: $d_{min}\ge3$), e la terna $\mathbf h_1+\mathbf h_4+\mathbf h_6=1010+1000+0010=\mathbf0$ è dipendente (corrisponde alla parola $1001010$ di peso $3$): $d_{min}=3$.