Esercizio - codice (6,2) con 4-QAM, matrice di parità, decodifica e capacità del canale (esame del 30 agosto 2024, es. 181)

---

Teoria usata: 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 →, 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 →, 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 →, 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 →.

1. Rate e matrice generatrice

$H$ ha $6$ colonne e $4$ righe, e la sua parte destra è l'identità $I_4$: è già nella forma sistematica $H=[A\mid I_{n-k}]$, con $n=6$ e $n-k=4$, quindi $k=2$. Il rate è $$R=\frac kn=\frac26=\frac13.$$ Si legge $A$ nelle prime due colonne e si scrive $G=\begin{bmatrix}I_k\\A\end{bmatrix}$ (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 →): $$A=\begin{bmatrix}1&0\\1&1\\1&1\\1&0\end{bmatrix},\qquad G=\begin{bmatrix}1&0\\0&1\\1&0\\1&1\\1&1\\1&0\end{bmatrix}.$$ Le $4$ parole sono $\mathbf b=00\to000000$, $\mathbf b=01\to010110$ (seconda colonna di $G$), $\mathbf b=10\to101111$ (prima colonna), $\mathbf b=11\to111001$ (somma). Si controlla che $H$ le annulli (Python: nucleo di $H$ = queste $4$ parole).

2. Distanza minima, peso minimo, errori rivelati e corretti

Pesi: $010110\to3$, $101111\to5$, $111001\to4$. Il peso minimo è $3$, quindi per un codice lineare $d_{min}=w_{min}=3$ (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 →). Lo stesso risultato si ottiene da $H$: le colonne sono tutte non nulle e distinte (nessuna parola di peso $1$ o $2$) e le colonne $2,4,5$ sommano a zero ($[0,1,1,0]^T+[0,1,0,0]^T+[0,0,1,0]^T=\mathbf 0$), che corrisponde alla parola $010110$.

• Errori rivelati sempre: $d_{min}-1=2$.
• Errori corretti sempre: $\lfloor\frac{3-1}2\rfloor=1$.

3. Decodifica di $\boldsymbol\xi=[1,1,1,0,1,1]^T$

Sindrome, riga per riga (modulo $2$):

• riga $[1,0,1,0,0,0]$: $\xi_1+\xi_3=1+1=0$;
• riga $[1,1,0,1,0,0]$: $\xi_1+\xi_2+\xi_4=1+1+0=0$;
• riga $[1,1,0,0,1,0]$: $\xi_1+\xi_2+\xi_5=1+1+1=1$;
• riga $[1,0,0,0,0,1]$: $\xi_1+\xi_6=1+1=0$.

$\boldsymbol\sigma=[0,0,1,0]^T$ non è nulla: errore rivelato. È la colonna $5$ di $H$ e le colonne sono tutte diverse, quindi il coset leader è unico: $\boldsymbol\varepsilon=[0,0,0,0,1,0]^T$. La parola decodificata è $$\boldsymbol\gamma=\boldsymbol\xi+\boldsymbol\varepsilon=[1,1,1,0,1,1]^T+[0,0,0,0,1,0]^T=[1,1,1,0,0,1]^T,$$ che è la parola $111001$ (da $\mathbf b=11$): l'errore era sul quinto bit.

4. Massimo bit-rate con probabilità d'errore piccola a piacere

Per il teorema di Shannon (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 →) si può ottenere una probabilità d'errore residua piccola a piacere con un bit-rate di informazione fino alla capacità del canale (esclusa). Il canale è il BSC realizzato con la 4-QAM; il suo periodo di simbolo è $T=1\ \mu$s per ogni uso del BSC, cioè per ogni bit.

Probabilità d'errore sul bit. Nella 4-QAM con mappa di Gray ogni bit viaggia su un asse come una binaria antipodale: $P_{bit}=Q\!\left(\sqrt{\frac{E_s}{N_0}}\right)$ con $N_0=2\sigma_I^2$ (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 →). Qui $$\frac{E_s}{N_0}=\frac{E_s}{2\sigma_I^2}=\frac{2\cdot10^{-7}}{2\cdot10^{-8}}=10,\qquad P_{bit}=Q(\sqrt{10})=Q(3{,}162)=7{,}83\cdot10^{-4}.$$

Capacità del BSC. $$h(P_{bit})=-P_{bit}\log_2P_{bit}-(1-P_{bit})\log_2(1-P_{bit})=0{,}00921,$$ $$C=\frac{1-h(P_{bit})}{T}=\frac{1-0{,}00921}{10^{-6}}=990{,}8\ \text{kbit/s}\approx991\ \text{kbit/s}.$$

Il massimo bit-rate è quindi circa $991$ kbit/s (con una codifica molto più sofisticata e lunga: il codice $(6,2)$ di questo esercizio trasporta soltanto $R\cdot\frac1T=\frac13\cdot1$ Mbit/s $=333$ kbit/s di informazione ed è lontanissimo dal limite). Il valore è calcolato assumendo che il periodo di simbolo di $1\ \mu$s sia quello del canale binario (un bit per $\mu$s), come fa la soluzione del corso.

Errori comuni

• Dimenticare che $G$ si legge da $H=[A\mid I]$ con la stessa $A$ (non $A^T$): in questo corso $G=\begin{bmatrix}I\\A\end{bmatrix}$ e $H=[A\mid I]$.
• Dire che con $d_{min}=3$ il codice "corregge due errori": ne corregge uno e ne rivela due.
• Prendere $E_s/N_0=E_s/\sigma_I^2$ (manca il fattore $2$): $N_0=2\sigma_I^2$.
• Calcolare la capacità con $\frac1T$ del simbolo QAM invece che del bit senza dichiarare l'ipotesi.