Esercizio - stop-and-wait con canale a cancellazione e informazione mutua (secondo compitino del 12 gennaio 2018, es. 73)

---

Teoria usata: Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico → (sezione sull'ARQ), 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 →, 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 →. Versione per Ing. Elettronica dell'ARQ: Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →.

1. Throughput dello stop-and-wait

Un pacchetto contiene $1$ simbolo e va ritrasmesso se il ricevitore osserva una cancellazione (l'ACK/NACK serve a chiederlo). Sono erasure solo gli ingressi $0$ e $3$, che hanno probabilità totale $1-q$, e solo con probabilità $0{,}15$: $$p=0{,}15\,(1-q)=0{,}15\cdot0{,}4=0{,}06.$$ Il throughput normalizzato dello stop-and-wait è $$S_{SW}=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}=\frac{1-p}{1+\frac{t_A}{t_P}+\frac{2\tau_P}{t_P}}.$$ Dai dati $\tau_P=0$ e $\frac{t_A}{t_P}=\frac12$: $$S_{SW}=\frac{1-0{,}06}{1+0{,}5}=\frac{0{,}94}{1{,}5}=0{,}627.$$

2. Il sistema modificato

Nel nuovo sistema, quando il ricevitore riceve $1$ o $2$ non manda né ACK né NACK e il trasmettitore passa subito al pacchetto successivo: per questi simboli il canale resta occupato solo per $t_P$ (e non c'è mai una cancellazione, quindi non c'è ritrasmissione). Quando il ricevitore riceve $0$, $3$ o una cancellazione manda l'ACK/NACK: per questi pacchetti vale lo stop-and-wait con probabilità d'errore (cancellazione) $0{,}15$ per ciascun tentativo.

Tempo medio di occupazione esclusiva del canale per ciascun pacchetto ($\tau_P=0$, $t_A=\frac{t_P}2$):

• pacchetti $1$ e $2$: $m_1=m_2=t_P$;
• pacchetti $0$ e $3$: ogni tentativo occupa $t_P+t_A=1{,}5\,t_P$ e riesce con probabilità $0{,}85$; il numero di tentativi è geometrico di media $\frac1{0{,}85}$: $$m_0=m_3=\frac{t_P+t_A+2\tau_P}{1-0{,}15}=\frac{1{,}5\,t_P}{0{,}85}=1{,}765\,t_P.$$

Il tempo medio per pacchetto, con le probabilità $q=0{,}6$ (simboli $1$ e $2$ insieme) e $1-q=0{,}4$ (simboli $0$ e $3$): $$\bar m=0{,}6\cdot t_P+0{,}4\cdot1{,}765\,t_P=1{,}306\,t_P.$$ Il throughput normalizzato è il tempo utile $t_P$ diviso il tempo medio di occupazione: $$S=\frac{t_P}{\bar m}=\frac1{1{,}306}=0{,}766\approx0{,}77.$$ Più alto di $S_{SW}=0{,}627$ del punto 1, come atteso: il nuovo sistema manda la conferma solo quando serve.

3. Informazione mutua in funzione di $q$

L'uscita ha alfabeto $\{0,1,2,3,E\}$ con $E$ la cancellazione. Si usa $I(x;y)=H(y)-H(y\mid 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 →).

Densità dell'uscita. $$p_y(1)=p_y(2)=\frac q2,\qquad p_y(0)=p_y(3)=0{,}85\,\frac{1-q}2,\qquad p_y(E)=0{,}15\,(1-q).$$ (per l'uscita $0$: ingresso $0$ con probabilità $\frac{1-q}2$ e non cancellato, $0{,}85$.)

Entropia condizionata. Per gli ingressi $1$ e $2$ l'uscita è determinata: $H(y\mid x=1)=H(y\mid x=2)=0$. Per gli ingressi $0$ e $3$ l'uscita vale l'ingresso con probabilità $0{,}85$ e $E$ con probabilità $0{,}15$: $$H(y\mid x=0)=H(y\mid x=3)=h(0{,}15)=-0{,}15\log_20{,}15-0{,}85\log_20{,}85=0{,}610\ \text{bit}.$$ Mediando sugli ingressi (probabilità $1-q$ per $\{0,3\}$): $$H(y\mid x)=(1-q)\,h(0{,}15)=0{,}610\,(1-q).$$

Entropia dell'uscita. Conviene raggruppare: gruppo $\{1,2\}$ con probabilità $q$, gruppo $\{0,3\}$ con probabilità $0{,}85(1-q)$, gruppo $\{E\}$ con probabilità $0{,}15(1-q)$. Per la regola del raggruppamento l'entropia è quella dei gruppi più l'entropia media dentro i gruppi: $$H(y)=\underbrace{H\big(q,\ 0{,}85(1-q),\ 0{,}15(1-q)\big)}_{=\ h(q)+(1-q)h(0{,}15)}+q\cdot1+0{,}85(1-q)\cdot1.$$ (dentro $\{1,2\}$ i due simboli sono equiprobabili: $1$ bit; lo stesso dentro $\{0,3\}$; il gruppo $\{E\}$ ha un solo elemento: $0$ bit; l'entropia dei gruppi si spezza ancora: prima "$\{1,2\}$ oppure no" con $h(q)$, poi tra $\{0,3\}$ ed $E$ con $h(0{,}15)$ pesato da $1-q$.)

Informazione mutua. Il termine $(1-q)h(0{,}15)$ si semplifica: $$\boxed{I(x;y)=h(q)+q+0{,}85\,(1-q)=h(q)+0{,}85+0{,}15\,q}$$ con $h(q)=-q\log_2q-(1-q)\log_2(1-q)$. Interpretazione: $h(q)$ è l'informazione sul gruppo ($\{1,2\}$ o $\{0,3\}$) che l'uscita rivela sempre; poi $1$ bit tra $1$ e $2$ (sempre conosciuto), e $1$ bit tra $0$ e $3$ solo se non c'è cancellazione ($0{,}85$). Per $q=0{,}6$: $h(0{,}6)=0{,}971$ e $I=0{,}971+0{,}85+0{,}09=1{,}911$ bit per simbolo (controllato con Python).

4. La capacità

La capacità è il massimo dell'informazione mutua sulle distribuzioni di ingresso. Per la simmetria del canale tra $1$ e $2$ e tra $0$ e $3$ (e la concavità di $I$ rispetto alla distribuzione di ingresso) il massimo si ottiene con probabilità uguali dentro i due gruppi, cioè proprio con la parametrizzazione dell'esercizio, e resta da massimizzare su $q\in[0,1]$: $$C=\max_{q\in[0,1]}\big[h(q)+0{,}85+0{,}15\,q\big],\qquad\frac{d}{dq}:\ \log_2\frac{1-q}{q}+0{,}15=0.$$ Si può anche chiudere il conto: $q^\star=\frac1{1+2^{-0{,}15}}=0{,}526$ e $$C=0{,}85+\log_2\!\left(1+2^{0{,}15}\right)=0{,}85+1{,}077=1{,}927\ \text{bit per simbolo}$$ (il massimo di $h(q)+aq$ vale $\log_2(1+2^a)$; confermato con una ricerca numerica su $q$ con Python). Rispetto a $q=0{,}6$ l'informazione mutua cresce da $1{,}911$ a $1{,}927$ bit: il massimo è vicino a $q=\frac12$.

Errori comuni

• Contare come errore del pacchetto ogni cancellazione "su tutti i simboli": le cancellazioni hanno probabilità $0{,}15$ solo sugli ingressi $0$ e $3$, quindi $p=0{,}15(1-q)$.
• Nel sistema modificato applicare lo stop-and-wait anche ai simboli $1$ e $2$: non c'è conferma, il canale resta occupato solo $t_P$.
• Calcolare $H(y\mid x)$ senza mediare con le probabilità di ingresso: $(1-q)\,h(0{,}15)$, non $h(0{,}15)$.
• Dimenticare di contare la cancellazione come simbolo di uscita nell'entropia $H(y)$.