Esercizio - codice (6,3) da equazioni con quadrati e matrice di controllo di parità (secondo compitino del 14 gennaio 2025, es. 185)

---

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

Linearità. Nell'aritmetica binaria $0^2=0$ e $1^2=1$: elevare al quadrato un bit non cambia il bit. Quindi $$c_4=b_2^2+b_3^2=b_2+b_3,\qquad c_6=(b_1+b_2+b_3)^2=b_1+b_2+b_3.$$ (la seconda conferma: il quadrato di una somma è la somma dei quadrati modulo $2$, perché il doppio prodotto vale $2xy=0$). Tutti i bit sono somme modulo $2$ di bit di informazione, senza costanti né prodotti: il codice è lineare. La matrice generatrice $G'$ ($6\times3$) ha per righe i coefficienti di $b_1,b_2,b_3$ in ogni equazione: $$G'=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\\0&1&1\\1&1&0\\1&1&1\end{bmatrix}.$$

Rate: $R=\frac kn=\frac36=\frac12$.

Sistematico? No: i primi due bit della parola sono $b_2$ e $b_1$, cioè invertiti rispetto all'informazione.

Forma sistematica con il minimo numero di permutazioni. Basta scambiare le prime due colonne di $G'$ (una sola permutazione di colonne): è un'operazione sulle colonne, quindi il codice è lo stesso (cambia solo quale $\mathbf b$ dà quale parola, 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 →). Si ottiene $$G=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\1&0&1\\1&1&0\\1&1&1\end{bmatrix}=\begin{bmatrix}I_3\\A\end{bmatrix},\qquad A=\begin{bmatrix}1&0&1\\1&1&0\\1&1&1\end{bmatrix}.$$ Le $8$ parole sono (per $\mathbf b=000,001,\dots,111$) $$000000,\ 001101,\ 010011,\ 011110,\ 100111,\ 101010,\ 110100,\ 111001.$$

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

Pesi delle parole non nulle: $001101\to3$, $010011\to3$, $011110\to4$, $100111\to4$, $101010\to3$, $110100\to3$, $111001\to4$. Il peso minimo è $3$ e, per un codice lineare, $d_{min}=w_{min}=3$ (le parole di peso $3$ sono quattro). Quindi

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

3. Decodifica con la sindrome

Dalla $G$ sistematica: $H=[A\mid I_3]$ (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&1&0&0\\1&1&0&0&1&0\\1&1&1&0&0&1\end{bmatrix}.$$ Le colonne sono $[1,1,1]^T$, $[0,1,1]^T$, $[1,0,1]^T$, $[1,0,0]^T$, $[0,1,0]^T$, $[0,0,1]^T$: tutte diverse e non nulle, quindi i sei errori singoli hanno sindromi distinte (coset leader unici) e $d_{min}\ge3$, in accordo con la sezione 2.

$\boldsymbol\xi_1=[0,0,0,0,1,1]^T$. Righe: $[1,0,1,1,0,0]\cdot\boldsymbol\xi_1=0$; $[1,1,0,0,1,0]\cdot\boldsymbol\xi_1=1$; $[1,1,1,0,0,1]\cdot\boldsymbol\xi_1=1$. Sindrome $\boldsymbol\sigma_1=[0,1,1]^T$, che è la colonna $2$ di $H$: il coset leader è $\boldsymbol\varepsilon=[0,1,0,0,0,0]^T$ e $$\boldsymbol\gamma_1=\boldsymbol\xi_1+\boldsymbol\varepsilon=[0,0,0,0,1,1]^T+[0,1,0,0,0,0]^T=[0,1,0,0,1,1]^T.$$ È la parola $010011$ (da $\mathbf b=010$).

$\boldsymbol\xi_2=[1,1,1,0,0,1]^T$. Righe: $1+1=0$ (riga $1$: bit $1$ e $3$); $1+1=0$ (riga $2$: bit $1,2$); $1+1+1+1=0$ (riga $3$: bit $1,2,3,6$). Sindrome $\mathbf 0$: $\boldsymbol\xi_2$ è già una parola di codice (da $\mathbf b=111$) e $\boldsymbol\gamma_2=\boldsymbol\xi_2=[1,1,1,0,0,1]^T$.

4. Probabilità di ricevere $\boldsymbol\xi_1$ trasmettendo $\boldsymbol\gamma_2$

Su un BSC conta il numero di bit diversi: $\boldsymbol\xi_1=000011$ e $\boldsymbol\gamma_2=111001$ differiscono nelle posizioni $1,2,3,5$ (nelle posizioni $4$ e $6$ coincidono: $0,0$ e $1,1$). Quindi $d_H=4$ e $$P[\boldsymbol\xi_1\mid\boldsymbol\gamma_2]=P_{bit}^{\,4}(1-P_{bit})^{\,2}=10^{-16}\cdot0{,}9999^2=9{,}998\cdot10^{-17}.$$

5. Esiste una codifica a errore residuo piccolo a piacere?

La sorgente emette un simbolo ogni $20\ \mu$s da un alfabeto di $4$ simboli: al massimo $\log_24=2$ bit per simbolo, cioè $$R_b=\frac{2}{20\cdot10^{-6}}=100\ \text{kbit/s}$$ (informazione massima, simboli equiprobabili; senza altre informazioni si assume questo valore). Il canale è il BSC con $T=10^{-5}$ s e $P_{bit}=10^{-4}$: $$h(10^{-4})=-10^{-4}\log_210^{-4}-0{,}9999\log_20{,}9999=0{,}001473,\qquad C=\frac{1-h(P_{bit})}{T}=\frac{0{,}998527}{10^{-5}}=99{,}85\ \text{kbit/s}.$$ Poiché $R_b=100>C=99{,}85$ 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 →) non esiste alcuna codifica a errore residuo piccolo a piacere: no. (Il codice $(6,3)$ di questo esercizio, di rate $\frac12$, non basterebbe comunque.)

Errori comuni

• Credere che $b_2^2+b_3^2$ o $(b_1+b_2+b_3)^2$ rendano il codice non lineare: modulo $2$ il quadrato di un bit è il bit stesso.
• Per la forma sistematica scambiare le righe (anche così si arriva alla forma sistematica, ma si cambiano i bit del codice) invece di scambiare le colonne, che lascia il codice invariato.
• Calcolare la sindrome di $\boldsymbol\xi_2$ senza accorgersi che è già una parola (sindrome nulla, nessuna correzione).
• Confrontare $C$ con $\frac{1}{T}$ (il bit-rate del canale) o con il rate del codice $R=\frac12$ invece che con il bit-rate dell'informazione della sorgente.