Esercizio - capacità di un canale 4-PSK, entropia di un codice a blocco, distanza minima e decodifica (compito dell'11 febbraio 2025, es. 192)

---

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 → (punto 1), 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 2), Codici a blocco lineari - matrice generatrice, forma sistematica e bound di SingletonUn codice a blocco è lineare se le sue $2^k$ parole formano un sottospazio dello spazio delle sequenze binarie di $n$ bit, con la somma modulo 2 (XOR) senza riporto: contiene la parola nulla ed è chiuso rispetto alla somma. Si descrive con la matrice generatrice $G$ ($n\times k$, rango $k$, $\mathbf c=G\mathbf b$, le colonne sono parole di codice); le operazioni sulle colonne non cambiano il codice, le permutazioni delle righe permutano i bit e non cambiano le prestazioni sul canale senza memoria. In forma sistematica $G=\begin{bmatrix}I_k\A\end{bmatrix}$ e $\mathbf c=[\mathbf b;A\mathbf b]$. Per i codici lineari la distanza minima è il peso di Hamming minimo delle parole non nulle e vale il bound di Singleton $d_{min}\le n-k+1$.Codici a blocco lineari - matrice generatrice, forma sistematica e bound di Singleton →, Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset → e 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 → (punti 3-5), Modulazione QAM - costellazioni, energia e probabilità d'erroreLa QAM trasmette due PAM indipendenti su due portanti in quadratura: $s_m(t)=\alpha_{m,I}h_{Tx}(t)\cos(2\pi f_0t)-\alpha_{m,Q}h_{Tx}(t)\sin(2\pi f_0t)$ con $\alpha\in{\pm1,\pm3,\dots}$ e $M=2^{2b}$ ($2b$ bit per simbolo). La base è $\phi_{1,2}\propto h_{Tx}\cos,,-h_{Tx}\sin$ con energia $\frac{E_h}2$, i punti stanno su una griglia $\sqrt M\times\sqrt M$ con $d_{\min}=\sqrt{2E_h}$ ed $E_s=\frac{M-1}{3}E_h$. Con $q=Q\left(\sqrt{\frac{E_h}{2\sigma_I^2}}\right)$: $P[E]=4\left(1-\frac1{\sqrt M}\right)q-4\left(1-\frac1{\sqrt M}\right)^2q^2$, con $\frac{E_h}{2\sigma_I^2}=\frac{E_s}{\sigma_I^2}\frac{3}{2(M-1)}$. Con Gray su ogni asse $P_{bit}\simeq\frac{P[E]}{\log_2M}$.Modulazione QAM - costellazioni, energia e probabilità d'errore → (probabilità di bit della 4-PSK/4-QAM con codifica di Gray).

(1) Quando è possibile una codifica con errore piccolo a piacere

Il canale visto dai bit. La 4-PSK trasporta $2$ bit per simbolo. Con la mappa di Gray i bit di due simboli vicini differiscono in una sola posizione, e un errore di simbolo è quasi sempre il passaggio a un punto adiacente, che sbaglia un bit su due. La probabilità d'errore sul bit è quindi $$P_{bit}\simeq\frac{P_e}{\log_2M}=\frac{P_e}2=\frac{10^{-3}}2=5\cdot10^{-4}.$$ Poiché il canale è senza memoria, i bit vedono un canale binario simmetrico con $P_{bit}=5\cdot10^{-4}$. (Se i due bit del simbolo sbagliassero in modo indipendente con probabilità $p$ si avrebbe $P_e=1-(1-p)^2$, cioè $p=5{,}006\cdot10^{-4}$: la differenza è trascurabile.)

Capacità. Per un BSC la capacità per bit trasmesso è $$1-h(P_{bit})=1-h(5\cdot10^{-4})=1-\left[5\cdot10^{-4}\log_2\tfrac1{5\cdot10^{-4}}+0{,}9995\log_2\tfrac1{0{,}9995}\right]=1-(0{,}005483+0{,}000721)=0{,}99380\ \text{bit}.$$ Se $T_b'$ è il periodo di bit sul canale (dopo il codificatore di canale), la capacità in bit/s è $C=\frac{0{,}9938}{T_b'}$.

Condizione. La sorgente $b_k$ ha un bit ogni $10^{-4}$ s, cioè tasso nominale $R=\frac1{10^{-4}}=10$ kbit/s (la trasformazione $b_k=B_k+1$ è una biiezione e non cambia il tasso). Per il teorema di Shannon la codifica con errore piccolo a piacere esiste se $R\le C$ (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 →): $$10\ \text{kbit/s}\le\frac{0{,}9938}{T_b'}\ \Rightarrow\ T_b'\le99{,}38\ \mu\text{s}\ \Leftrightarrow\ \frac1{T_b'}\ge10{,}062\ \text{kbit/s}.$$ Con due bit per simbolo il periodo di simbolo della 4-PSK è $T=2T_b'$, quindi $$T\le198{,}8\ \mu\text{s}\ \Leftrightarrow\ \frac1T\ge5{,}031\ \text{ksimboli/s}.$$ La codifica esiste solo se il modulatore trasmette almeno $5{,}031$ ksimboli/s (almeno $10{,}062$ kbit/s sul canale): serve un po' più della velocità della sorgente, perché la capacità è un po' meno di $1$ bit per uso. Se si trasmettesse al ritmo della sorgente ($T_b'=100\ \mu$s, $T=200\ \mu$s) la capacità sarebbe $9{,}938$ kbit/s, minore di $10$ kbit/s, e non esisterebbe nessuna codifica con errore piccolo a piacere.

(2) Entropia del vettore $\mathbf c$

Le righe $1$ e $2$ della matrice sono l'identità: $c_1=b_1$, $c_2=b_2$, quindi da $\mathbf c$ si risale a $[b_1,b_2]$. Le altre componenti sono funzioni di $b_1,b_2$: $c_3=b_1$, $c_4=b_2$, $c_5=c_6=b_1+b_2$ (modulo $2$). Dunque $\mathbf c$ è una funzione biunivoca della coppia $[b_1,b_2]$, e questa a sua volta è biunivoca rispetto a $[B_1,B_2]$ (basta sommare $1$ a ciascun bit). I due bit $B_1,B_2$ sono indipendenti ed equiprobabili, quindi le $4$ parole di codice sono equiprobabili, ciascuna con probabilità $\frac14$, e $$H(\mathbf c)=H(b_1,b_2)=4\cdot\frac14\log_24=2\ \text{bit}.$$ Una funzione biunivoca non cambia l'entropia (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 →: se $y=f(x)$ e $x=g(y)$, $H(x,y)=H(x)=H(y)$).

(3) Rate, distanza minima, errori rilevati e corretti

Il codice ha $k=2$ bit di informazione e parole di $n=6$ bit: rate $\frac kn=\frac26=\frac13$. Le quattro parole di codice (calcolando $\mathbf c$ per le $4$ coppie, con $c_5=c_6=b_1+b_2$):

Il codice è lineare (è definito da una matrice, con somme modulo $2$), quindi $d_{\min}$ è uguale al peso minimo delle parole non nulle: $d_{\min}=4$. Controllo sulle distanze tra coppie: $d(010111,101011)=4$, $d(010111,111100)=4$, $d(101011,111100)=4$ ✓. Il codice rileva $d_{\min}-1=3$ errori e corregge $\left\lfloor\frac{d_{\min}-1}2\right\rfloor=1$ errore (Codici a blocco lineari - matrice generatrice, forma sistematica e bound di SingletonUn codice a blocco è lineare se le sue $2^k$ parole formano un sottospazio dello spazio delle sequenze binarie di $n$ bit, con la somma modulo 2 (XOR) senza riporto: contiene la parola nulla ed è chiuso rispetto alla somma. Si descrive con la matrice generatrice $G$ ($n\times k$, rango $k$, $\mathbf c=G\mathbf b$, le colonne sono parole di codice); le operazioni sulle colonne non cambiano il codice, le permutazioni delle righe permutano i bit e non cambiano le prestazioni sul canale senza memoria. In forma sistematica $G=\begin{bmatrix}I_k\A\end{bmatrix}$ e $\mathbf c=[\mathbf b;A\mathbf b]$. Per i codici lineari la distanza minima è il peso di Hamming minimo delle parole non nulle e vale il bound di Singleton $d_{min}\le n-k+1$.Codici a blocco lineari - matrice generatrice, forma sistematica e bound di Singleton →).

(4) Decodifica

La matrice generatrice è già in forma sistematica ($c_1=b_1$, $c_2=b_2$ sono i bit di informazione): $G=\begin{bmatrix}I_2\\P\end{bmatrix}$ con $P=\begin{bmatrix}1&0\\0&1\\1&1\\1&1\end{bmatrix}$ (le righe $3$-$6$ di $G$). La matrice di controllo di parità è $H=[\,P\,|\,I_4\,]$ (Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →): $$H=\begin{bmatrix}1&0&1&0&0&0\\0&1&0&1&0&0\\1&1&0&0&1&0\\1&1&0&0&0&1\end{bmatrix}.$$ Le quattro righe esprimono le condizioni $c_1+c_3=0$, $c_2+c_4=0$, $c_1+c_2+c_5=0$, $c_1+c_2+c_6=0$.

$\xi_1=[1\ 1\ 1\ 1\ 0\ 0]^T$. Sindrome: $s_1=\xi_1+\xi_3=1+1=0$, $s_2=\xi_2+\xi_4=0$, $s_3=\xi_1+\xi_2+\xi_5=1+1+0=0$, $s_4=\xi_1+\xi_2+\xi_6=0$. La sindrome è nulla, quindi $\xi_1$ è una parola di codice (la parola per $[b_1,b_2]=[1,1]$): $\gamma_1=\xi_1=[1\ 1\ 1\ 1\ 0\ 0]^T$.

$\xi_2=[1\ 1\ 1\ 0\ 0\ 0]^T$. Sindrome: $s_1=1+1=0$, $s_2=\xi_2+\xi_4=1+0=1$, $s_3=1+1+0=0$, $s_4=1+1+0=0$, quindi $s=[0\ 1\ 0\ 0]^T$. È la quarta colonna di $H$ (e nessun'altra colonna è uguale, perché la colonna $2$ è $[0,1,1,1]^T$): l'errore di peso minimo è sul quarto bit, $\mathbf e=[0\ 0\ 0\ 1\ 0\ 0]^T$, e $$\gamma_2=\xi_2+\mathbf e=[1\ 1\ 1\ 1\ 0\ 0]^T.$$ Controllo con la distanza di Hamming: $\xi_2$ dista $1$ da $111100$ e $3$ da $000000$ e da $101011$ (e $5$ da $010111$): la parola più vicina è unica. I due ricevuti portano alla stessa parola decodificata $[1,1,1,1,0,0]^T$, cioè ai bit di informazione $[b_1,b_2]=[1,1]$ e quindi a $[B_1,B_2]=[0,0]$.

(5) Probabilità di ricevere una sequenza di peso $6$

Con $B_1=0$, $B_2=1$ si ha $b_1=0+1=1$, $b_2=1+1=0$. La parola trasmessa è $\mathbf c=G[1,0]^T=[1\ 0\ 1\ 0\ 1\ 1]^T$ (peso $4$: ha due zeri, in posizione $2$ e $4$). Una sequenza di peso $6$ è l'unica $\xi=[1\ 1\ 1\ 1\ 1\ 1]^T$. Per ottenerla dal canale si devono verificare entrambe le cose: i due zeri vengono invertiti e i quattro uni arrivano senza errore. Gli errori del BSC senza memoria sono indipendenti, quindi $$P[\xi=\mathbf1|\mathbf c]=P_{bit}^2(1-P_{bit})^4=(5\cdot10^{-4})^2\cdot(0{,}9995)^4=2{,}5\cdot10^{-7}\cdot0{,}998=2{,}495\cdot10^{-7}.$$ (La soluzione del corso riporta il passaggio $9{,}975\cdot10^{-4}=2{,}5\cdot10^{-7}$, che è un refuso di scrittura: $(0{,}9995)^4=0{,}9980$ e il risultato $2{,}5\cdot10^{-7}$ è corretto.)

(Verificato con Python: parole di codice e pesi, $d_{\min}=4$, sindromi $[0,0,0,0]^T$ e $[0,1,0,0]^T$, decodifica a massima verosimiglianza per enumerazione, $1-h(5\cdot10^{-4})=0{,}993796$, $T\le198{,}76\ \mu$s, $P=2{,}495\cdot10^{-7}$.)

Errori comuni

• Usare $P_{bit}=P_e$ per la 4-PSK: con la codifica di Gray è $P_{bit}\simeq\frac{P_e}2$.
• Confondere periodo di simbolo della 4-PSK ($T=2T_b'$) e periodo di bit sul canale ($T_b'$).
• Concludere "sì, sempre": la condizione $R\le C$ dà un limite sul periodo (cioè sulla velocità del canale).
• Calcolare $H(\mathbf c)=6$ bit contando le componenti: le componenti sono dipendenti e le parole sono solo $4$.
• Dire che il codice è sistematico "perché ha l'identità" senza controllare dove: qui sono i primi due bit.
• Calcolare la probabilità del punto 5 con un solo bit sbagliato, o con $P_{bit}^2$ senza il fattore dei quattro bit corretti.