Esercizio 27TDMA, codice a blocco (63,45) e PAM a quattro livelli (tema d'esame luglio 2021)

---

Teoria usata: Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMAQuando più nodi condividono un mezzo serve un protocollo di accesso (MAC). Accesso deterministico: FDMA (una banda per utente) e TDMA (uno slot per utente in una trama): nessuna collisione, a ogni utente $\frac{R_b}N$ meno le perdite di sincronismo. Accesso aleatorio: ALOHA puro ($S=Ge^{-2G}$, massimo $\frac1{2e}=0{,}184$ in $G=0{,}5$), slotted ALOHA ($S=Ge^{-G}$, massimo $\frac1e=0{,}368$ in $G=1$), CSMA (si ascolta prima di trasmettere: nel non persistente $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, con $a=\frac{\tau_P}{t_P}$ piccolo si arriva a $\approx0{,}8$-$0{,}9$).Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA →, Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →, Informazione ed entropiaL'informazione di un evento di probabilità $p$ è $\log_2\frac1p$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza della sorgente: $0\le H\le\log_2M$, con il massimo quando i simboli sono equiprobabili. Per più simboli: $H(x,y)\le H(x)+H(y)$ (uguaglianza se indipendenti), $H(x|y)=H(x,y)-H(y)$. Per una sorgente con $F_s$ simboli al secondo il rate di informazione è $F_sH_s$, il rate nominale $F_s\log_2M$ e l'efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione ed entropia →, PAM - modulazione di ampiezza di impulsiNella PAM ogni segnale è l'impulso $h(t)$ moltiplicato per un'ampiezza $\alpha_m=2m-1-M$: $s_m(t)=\alpha_mh(t)$. La costellazione è su una retta (base $\phi=\frac h{\sqrt{E_h}}$, punti $\alpha_m\sqrt{E_h}$) con $d_{min}=2\sqrt{E_h}$ ed energia media $E_s=E_h\frac{M^2-1}3$. La probabilità di errore è $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{2E_h}{N_0}}\right)=2\left(1-\frac1M\right)Q\left(\sqrt{\frac6{M^2-1}\frac{E_s}{N_0}}\right)$ e con Gray $P_{bit}\approx\frac{P[E]}{\log_2M}$. È semplice, ma l'energia cresce come $M^2$.PAM - modulazione di ampiezza di impulsi →, Mezzi di trasmissione - cavi, fibre e collegamenti radioIl mezzo di trasmissione fissa l'attenuazione $a_{ch}$ nel link budget. Nei cavi $H_{ch}=e^{-\gamma d}$ e l'attenuazione in dB cresce con la distanza ($a=\tilde a,d$, dB/km) e con $\sqrt f$. Le fibre ottiche hanno banda larghissima (10¹⁴-10¹⁵ Hz), attenuazione bassa in tre finestre di lunghezza d'onda e limitazione dalla dispersione. Nei collegamenti radio vale la formula di Friis, $g_{ch}=g_{tx}g_{rx}\left(\frac\lambda{4\pi d}\right)^2$, cioè $a_{ch}=32{,}4+20\log_{10}d_{km}+20\log_{10}f_{MHz}-G_{tx}-G_{rx}$ dB.Mezzi di trasmissione - cavi, fibre e collegamenti radio →.

(1) Bit-rate utile per utente

Con TDMA ideale ogni utente dispone di $\frac1N$ del tempo, quindi di $\frac{R_b}N=\frac{10\ \text{Gbit/s}}{20}=500$ Mbit/s trasmessi. Il codice $(63,45)$ ne dedica $63-45=18$ su $63$ alla ridondanza: i bit utili sono $\frac kn$ di quelli trasmessi, $$R_{utile}=\frac{R_b}N\cdot\frac kn=500\cdot\frac{45}{63}=357{,}1\ \text{Mbit/s}.$$

(2) Distanza minima

Il codice deve correggere $t\ge3$ errori: serve $d_{min}\ge2t+1=7$ (Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →). La distanza minima richiesta è quindi $d_{min}=7$ (per il limite di Singleton $d_{min}\le n-k+1=19$, quindi un codice con $d_{min}=7$ è possibile).

(3) Frequenza di simbolo massima

I simboli della sorgente (alfabeto di $20$ valori) portano un'informazione media pari all'entropia $$H=8\cdot0{,}05\log_2\frac1{0{,}05}+8\cdot0{,}025\log_2\frac1{0{,}025}+4\cdot0{,}1\log_2\frac1{0{,}1}=1{,}729+1{,}064+1{,}329=4{,}122\ \text{bit/simbolo}.$$ (Le probabilità sommano $0{,}4+0{,}2+0{,}4=1$.) Con una codifica di sorgente ideale ($\eta\to1$) il rate di informazione $F\cdot H$ può arrivare a occupare tutto il bit-rate utile, per cui la massima frequenza con cui la sorgente può emettere simboli è $$F_{max}=\frac{R_{utile}}H=\frac{357{,}14\cdot10^6}{4{,}122}=86{,}6\ \text{Msimboli/s}.$$ (Senza codifica di sorgente servirebbero $\lceil\log_220\rceil=5$ bit per simbolo: $71{,}4$ Msimboli/s.)

(4) Potenza statistica media in trasmissione

Per la $4$-PAM con simboli $\alpha\in\{\pm1,\pm3\}$ ($E[\alpha^2]=5$) e impulso rettangolare di durata $\frac T2$ e ampiezza $A$: $E_h=A^2\frac T2$, $E_s=E[\alpha^2]E_h=5A^2\frac T2$ (PAM - modulazione di ampiezza di impulsiNella PAM ogni segnale è l'impulso $h(t)$ moltiplicato per un'ampiezza $\alpha_m=2m-1-M$: $s_m(t)=\alpha_mh(t)$. La costellazione è su una retta (base $\phi=\frac h{\sqrt{E_h}}$, punti $\alpha_m\sqrt{E_h}$) con $d_{min}=2\sqrt{E_h}$ ed energia media $E_s=E_h\frac{M^2-1}3$. La probabilità di errore è $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{2E_h}{N_0}}\right)=2\left(1-\frac1M\right)Q\left(\sqrt{\frac6{M^2-1}\frac{E_s}{N_0}}\right)$ e con Gray $P_{bit}\approx\frac{P[E]}{\log_2M}$. È semplice, ma l'energia cresce come $M^2$.PAM - modulazione di ampiezza di impulsi →). La potenza statistica è $E_s$ diviso il periodo di simbolo: $$M_s=\frac{E_s}T=\frac52A^2=\frac52\cdot6{,}25=15{,}6\ \text{V}^2.$$ Non dipende da $T$.

(5) Probabilità d'errore sul simbolo

Attenuazione: $2\ \text{dB/km}\cdot20\ \text{km}=40$ dB, cioè $10^4$ in potenza: $M_{s,rx}=\frac{15{,}625}{10^4}=1{,}5625\cdot10^{-3}\ \text{V}^2$. Con rumore $M_w=2\cdot10^{-5}\ \text{V}^2$ l'SNR è $$\Gamma=\frac{M_{s,rx}}{M_w}=78{,}1\ \ (18{,}9\ \text{dB}).$$ Per la PAM in banda base $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{3\Gamma}{M^2-1}}\right)$ con $M=4$: $$P[E]=\frac32\,Q\left(\sqrt{\frac{3\cdot78{,}125}{15}}\right)=\frac32\,Q(3{,}953)=1{,}5\cdot3{,}86\cdot10^{-5}=5{,}8\cdot10^{-5}.$$

(6) Probabilità d'errore sul bit dopo la correzione

Con codifica di Gray, la probabilità d'errore sul bit del canale numerico è $p=\frac{P[E]}{\log_24}=2{,}9\cdot10^{-5}$. Il codice $(63,45)$ corregge $t=3$ errori: una parola è sbagliata se ne ha almeno $4$, e con $p\ll1$ $$P_w\approx\binom{63}{4}p^4=595\,665\cdot(2{,}9\cdot10^{-5})^4=4{,}2\cdot10^{-13},$$ e la probabilità d'errore sul bit residuo è circa $\frac{d_{min}}nP_w$ (una parola decodificata male sbaglia circa $d_{min}$ bit su $n$): $$P_{bit,res}\approx\frac{7}{63}\binom{63}4p^4(1-p)^{59}=4{,}6\cdot10^{-14}.$$ La correzione fa passare la probabilità d'errore sul bit da $2{,}9\cdot10^{-5}$ a $4{,}6\cdot10^{-14}$ (nove ordini di grandezza), pagando $\frac{63}{45}=1{,}4$ di banda o il $29\%$ di rate.

(Verificato con Python: $R_{utile}=357{,}14$ Mbit/s, $H=4{,}1219$ bit, $F_{max}=86{,}64$ Msimb/s, $P[E]=5{,}79\cdot10^{-5}$, $P_{bit,res}=4{,}65\cdot10^{-14}$. La soluzione a mano del Drive scrive $4{,}75\cdot10^{-5}$ per il punto 5, ma $\frac32Q(3{,}953)$ vale $5{,}8\cdot10^{-5}$.)

Errori comuni

• Dimenticare di moltiplicare per $\frac kn$ (e dividere per $N$) nel bit-rate utile.
• Prendere $d_{min}=2t$ ($=6$) invece di $2t+1$.
• Calcolare la frequenza di simbolo con $\log_220$ (senza codifica) anche quando la sorgente ha un'entropia più bassa.
• Usare l'SNR in dB nella $Q$ (serve il lineare) o l'attenuazione di $2$ dB invece di $40$ dB.