Esercizio - codice (6,2) da matrice di parità non sistematica, decodifica e capacità con 4-QAM (secondo compitino del 12 gennaio 2024, es. 169)

---

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. Linearità, rate, forma sistematica

Lineare. Il codice è l'insieme delle $\mathbf r$ con $H\mathbf r=\mathbf 0$, cioè lo spazio nullo di una matrice: è un sottospazio, quindi lineare.

Rate. $H$ ha $6$ colonne ($n=6$) e $4$ righe indipendenti (il rango è $4$: la prima riga è l'unica con $1$ in colonna $4$, la seconda l'unica in colonna $5$, la quarta l'unica in colonna $6$, la terza è l'unica con $1$ in colonna $2$). Quindi $n-k=4$, $k=2$, $R=\frac26=\frac13$. Le parole sono $2^2=4$.

Sistematico? Una matrice di controllo in forma sistematica ha l'identità $I_4$ nelle ultime quattro colonne, nell'ordine $\mathbf e_1,\mathbf e_2,\mathbf e_3,\mathbf e_4$. Le colonne di $H$ sono $$\mathbf h_1=\begin{bmatrix}0\\1\\1\\0\end{bmatrix},\ \mathbf h_2=\begin{bmatrix}0\\0\\1\\0\end{bmatrix},\ \mathbf h_3=\begin{bmatrix}1\\1\\1\\1\end{bmatrix},\ \mathbf h_4=\begin{bmatrix}1\\0\\0\\0\end{bmatrix},\ \mathbf h_5=\begin{bmatrix}0\\1\\0\\0\end{bmatrix},\ \mathbf h_6=\begin{bmatrix}0\\0\\0\\1\end{bmatrix}.$$ Le colonne $3,4,5,6$ sono $[1,1,1,1]^T,\mathbf e_1,\mathbf e_2,\mathbf e_4$: non sono l'identità, quindi $H$ non è in forma sistematica.

Forma sistematica con il minimo di permutazioni dei bit. Le colonne $\mathbf e_1,\mathbf e_2,\mathbf e_3,\mathbf e_4$ sono $\mathbf h_4,\mathbf h_5,\mathbf h_2,\mathbf h_6$ e devono occupare le posizioni $3,4,5,6$ in questo ordine: $\mathbf h_4$ passa in posizione $3$, $\mathbf h_5$ in $4$, $\mathbf h_2$ in $5$ ($\mathbf h_6$ è già al suo posto). Le colonne non identità $\mathbf h_1,\mathbf h_3$ vanno nelle posizioni $1,2$. L'ordine nuovo è $(\mathbf h_1,\mathbf h_3,\mathbf h_4,\mathbf h_5,\mathbf h_2,\mathbf h_6)$, cioè la seconda colonna viene spostata in quinta posizione: $$H'=\begin{bmatrix}0&1&1&0&0&0\\1&1&0&1&0&0\\1&1&0&0&1&0\\0&1&0&0&0&1\end{bmatrix}=[A\mid I_4],\qquad A=\begin{bmatrix}0&1\\1&1\\1&1\\0&1\end{bmatrix}.$$ Si legge la generatrice $G=\begin{bmatrix}I_2\\A\end{bmatrix}$: $$G=\begin{bmatrix}1&0\\0&1\\0&1\\1&1\\1&1\\0&1\end{bmatrix}.$$ Le parole del codice sistematico associato sono $000000$, $100110$ ($\mathbf b=10$: prima colonna), $011111$ ($\mathbf b=01$) e $111001$ ($\mathbf b=11$). Sono le parole del codice originale con i bit permutati (la posizione $2$ finisce in quinta, le altre scorrono), quindi lo stesso comportamento su canale senza memoria: stessa $d_{min}$, stesse probabilità d'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 →).

Osservazione. Il codice originale ha le parole $000000,\ 011111,\ 101101,\ 110010$ (nucleo di $H$, controllato con Python) e i loro primi due bit sono $00,01,10,11$: il codice, come insieme di parole, ha già i primi due bit liberi, quindi con operazioni sulle righe di $H$ (che non cambiano il codice) e sulle colonne di $G$ si arriva a $G=\begin{bmatrix}1&0\\0&1\\1&1\\1&1\\0&1\\1&1\end{bmatrix}$ senza permutare alcun bit. La soluzione del corso permuta una colonna, e i punti successivi (punti 3 e 5) vanno letti sul codice permutato. Se si decodificasse sul codice originale la sequenza $\boldsymbol\xi_1$ darebbe un pareggio (sezione 3).

2. Distanza minima, peso minimo, errori

Pesi delle parole non nulle del codice sistematico: $100110\to3$, $011111\to5$, $111001\to4$. Il peso minimo è $3$ e, per un codice lineare, $d_{min}=w_{min}=3$ (stesso valore per il codice originale, con pesi $5,4,3$). Si ritrova da $H'$: le colonne sono tutte non nulle e tutte diverse, quindi nessuna parola ha peso $1$ o $2$ ($d_{min}\ge3$), e le colonne $1,4,5$ sommano a zero ($[0,1,1,0]^T+[0,1,0,0]^T+[0,0,1,0]^T=\mathbf 0$), cioè la parola $100110$ di peso $3$ esiste (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 →). Quindi

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

3. Decodifica con il codice sistematico associato

$\boldsymbol\xi_1=[1,1,1,0,1,1]^T$. Con $H'$, riga per riga:

• riga $[0,1,1,0,0,0]$: $\xi_2+\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 $[0,1,0,0,0,1]$: $\xi_2+\xi_6=1+1=0$.

Sindrome $\boldsymbol\sigma=[0,0,1,0]^T$: è 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$, e $$\boldsymbol\gamma_1=\boldsymbol\xi_1+\boldsymbol\varepsilon=[1,1,1,0,1,1]^T+[0,0,0,0,1,0]^T=[1,1,1,0,0,1]^T.$$ È la parola $111001$ (da $\mathbf b=11$).

$\boldsymbol\xi_2=[1,1,1,0,0,1]^T$. Righe: $1+1=0$; $1+1+0=0$; $1+1+0=0$; $1+1=0$. Sindrome $\mathbf 0$: $\boldsymbol\xi_2$ è già una parola e $\boldsymbol\gamma_2=\boldsymbol\xi_2=[1,1,1,0,0,1]^T$. (Quindi anche $\boldsymbol\xi_1$ viene decodificata in $\boldsymbol\xi_2$, come dice la soluzione del corso: $\boldsymbol\gamma_1=\boldsymbol\gamma_2$.)

Con il codice originale (parole $000000,011111,101101,110010$) $\boldsymbol\xi_1$ è a distanza $2$ sia da $011111$ sia da $110010$ (e $3$ da $101101$, $5$ da $\mathbf 0$): pareggio, non correggibile in modo unico, come previsto da $d_{min}=3$ che garantisce solo un errore. Per questo il testo parla del "codice sistematico associato".

4. Esiste un codice per $99$ kbit/s?

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 →) con un bit-rate di informazione minore della capacità la probabilità d'errore residua si può rendere piccola a piacere: anche sotto $10^{-30}$ (resta un numero fissato, e "piccola a piacere" lo include). Il canale è il BSC con $P_{bit}=10^{-4}$ e $T=10^{-5}$ s per bit: $$h(10^{-4})=0{,}001473,\qquad C=\frac{1-h(P_{bit})}{T}=\frac{0{,}998527}{10^{-5}}=99{,}85\ \text{kbit/s}.$$ $R_b=99<99{,}85$ kbit/s: sì, è possibile. (Il margine è sottile, di $0{,}85$ kbit/s: servirebbero parole molto lunghe.)

5. Con la modulazione 4-QAM

Probabilità d'errore sul bit. Per la 4-QAM con Gray $P_{bit}=Q\!\left(\sqrt{E_s/(2\sigma_I^2)}\right)$ (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 →): $$\frac{E_s}{2\sigma_I^2}=\frac{8\cdot10^{-7}}{2\cdot10^{-7}}=4,\qquad P_{bit}=Q(\sqrt4)=Q(2)=2{,}275\cdot10^{-2}.$$ (È anche la formula generale per la QAM, $\frac4{\log_2M}\left(1-\frac1{\sqrt M}\right)Q\!\left(\sqrt{\frac3{M-1}\frac{E_s}{2\sigma_I^2}}\right)$, con $M=4$: $2\cdot\frac12\cdot Q(2)$.)

Capacità. Il periodo di simbolo della 4-QAM è $T=10^{-5}$ s e ogni simbolo porta $2$ bit, quindi i bit del BSC equivalente si succedono ogni $T_b=\frac T2=5\ \mu$s: $$h(0{,}02275)=0{,}1566,\qquad C=\frac{1-h(P_{bit})}{T_b}=\frac{1-0{,}1566}{5\cdot10^{-6}}=168{,}7\ \text{kbit/s}.$$ Con questa lettura $R_b=99<C=168{,}7$ kbit/s: sì, è possibile (calcolo verificato con Python).

Osservazione sulla soluzione del corso. La soluzione riporta lo stesso valore, $169$ kbit/s, ma conclude "no, perché è inferiore al rate della sorgente". Ora $169>99$, quindi con quel valore la risposta è sì. La conclusione "no" sarebbe vera se i $10\ \mu$s fossero il periodo di un bit (non di un simbolo QAM a due bit): allora $C=\frac{1-0{,}1566}{10^{-5}}=84{,}3$ kbit/s, minore di $99$ kbit/s. Con la formulazione "lo stesso periodo di simbolo" della modulazione, la lettura coerente è quella a due bit per simbolo e la risposta è sì.

Errori comuni

• Dire che $H$ è già sistematica perché "ha una sotto-matrice identità": le ultime quattro colonne devono essere $\mathbf e_1,\dots,\mathbf e_4$ in ordine.
• Passare da $H'=[A\mid I]$ a $G=\begin{bmatrix}A\I\end{bmatrix}$ o a $[A\mid I]^T$ invece di $\begin{bmatrix}I\A\end{bmatrix}$.
• Decodificare con la $H$ originale dopo aver permutato il codice, o viceversa.
• Calcolare la capacità della 4-QAM con il periodo del simbolo anziché del bit (due bit per simbolo).
• Dimenticare che $N_0=2\sigma_I^2$ nella probabilità d'errore sul bit.