Esercizio - codice (8,4) non sistematico, sistematica equivalente e cascata di due codici (esame del 23 gennaio 2024, es. 172)

---

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 →.

1. Linearità e forma sistematica

a) Lineare. Il codice è definito da una matrice generatrice: $\mathbf c=G\mathbf b$, e l'insieme dei $G\mathbf b$ è lo spazio generato dalle colonne di $G$, un sottospazio. La matrice ha rango $4$ (le righe $[1,0,0,0]$, $[0,1,0,0]$, $[0,0,1,1]$ e $[0,0,0,1]$ sono indipendenti): ci sono $2^4=16$ parole, $n=8$, $k=4$. Il codice è lineare.

b) Sistematico? In un codice sistematico $G=\begin{bmatrix}I_4\\A\end{bmatrix}$. Qui le prime quattro righe sono $[1,0,0,0],[0,1,0,0],[0,0,1,1],[0,0,0,1]$: la terza non è $[0,0,1,0]$, quindi non è in forma sistematica.

Basta una permutazione dei bit? Permutare i bit di tutte le parole significa permutare le righe di $G$. Per ottenere $I_4$ in alto servono quattro righe che valgano $[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]$. Le righe di $G$ sono $[1,0,0,0],[0,1,0,0],[0,0,1,1],[0,0,0,1],[1,1,1,0],[1,0,1,1],[1,1,1,1],[0,1,1,0]$: manca $[0,0,1,0]$. Quindi no, con una permutazione dei bit non si arriva alla forma sistematica.

2. Può essere $d_{min}=5$?

Ogni colonna di $G$ è una parola di codice, quindi $d_{min}$ non supera il peso di nessuna colonna (il peso minimo dà un limite superiore, 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 →). La prima colonna è $[1,0,0,0,1,1,1,0]^T$ e ha peso $4$. Perciò $$d_{min}\le4<5.$$ No, il codice non può avere distanza minima $5$. (Il valore vero è $d_{min}=3$: Python dà $4$ parole di peso $3$, $5$ di peso $4$, $4$ di peso $5$, $2$ di peso $6$; per esempio $\mathbf g_3+\mathbf g_4=[0,0,0,1,1,0,0,1]^T$ ha peso $3$.)

3. Forma sistematica equivalente e matrice di parità

Servono operazioni sulle colonne, che non cambiano il codice. La terza riga è $[0,0,1,1]$ e dovrebbe essere $[0,0,1,0]$: si toglie il $1$ in quarta colonna sostituendo la quarta colonna con la somma della terza e della quarta: $$\mathbf g_3=\begin{bmatrix}0\\0\\1\\0\\1\\1\\1\\1\end{bmatrix},\ \mathbf g_4=\begin{bmatrix}0\\0\\1\\1\\0\\1\\1\\0\end{bmatrix},\qquad \mathbf g_3+\mathbf g_4=\begin{bmatrix}0\\0\\0\\1\\1\\0\\0\\1\end{bmatrix}.$$ La nuova matrice è $$G_s=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&1&1\\1&0&1&0\\1&1&1&0\\0&1&1&1\end{bmatrix}=\begin{bmatrix}I_4\\A\end{bmatrix},\quad A=\begin{bmatrix}1&1&1&1\\1&0&1&0\\1&1&1&0\\0&1&1&1\end{bmatrix}.$$ (Le colonne $1$, $2$ e $3$ sono invariate e la quarta colonna nuova è $[0,0,0,1,1,0,0,1]^T$. Python conferma che $G$ e $G_s$ generano le stesse $16$ parole.)

La matrice di controllo di parità è $H=[A\mid 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&1&1&1&1&0&0&0\\1&0&1&0&0&1&0&0\\1&1&1&0&0&0&1&0\\0&1&1&1&0&0&0&1\end{bmatrix}.$$ Controllo $HG_s=0$ (Python). Le colonne di $H$ sono tutte non nulle e distinte, quindi $d_{min}\ge3$, coerente con la sezione 2.

4. Cascata dei due codici

L'uscita del primo codificatore è $\mathbf c=G\mathbf b$ (otto bit) e questa è l'ingresso del secondo: $\mathbf c'=G_1\mathbf c=G_1(G\mathbf b)=(G_1G)\mathbf b$. Il prodotto di matrici è una trasformazione lineare di $\mathbf b$: la cascata è un codice lineare con matrice generatrice $$G_c=G_1G\qquad(9\times4).$$ Poiché $G_1=\begin{bmatrix}I_8\\\mathbf r\end{bmatrix}$ con $\mathbf r=[1,1,1,0,0,1,0,1]$, il prodotto è $G_c=\begin{bmatrix}G\\\mathbf rG\end{bmatrix}$: le prime otto righe sono quelle di $G$ e la nona è la combinazione delle righe di $G$ dove $\mathbf r$ ha un $1$ (righe $1,2,3,6,8$): $$\mathbf rG=[1,0,0,0]+[0,1,0,0]+[0,0,1,1]+[1,0,1,1]+[0,1,1,0]=[0,0,1,0].$$ (colonna per colonna: $1+0+0+1+0=0$, $0+1+0+0+1=0$, $0+0+1+1+1=1$, $0+0+1+1+0=0$.) Quindi $$G_c=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&1\\0&0&0&1\\1&1&1&0\\1&0&1&1\\1&1&1&1\\0&1&1&0\\0&0&1&0\end{bmatrix}.$$ È un codice $(9,4)$ ($n=9$, $k=4$). Controllo con Python: $d_{min}=4$ (spettro dei pesi $1,\ 0,0,0,\ 9,\ 0,\ 6$ per i pesi $0,\dots,6$): il bit aggiunto aumenta la distanza minima da $3$ a $4$ (le parole di peso $3$ vengono portate a peso $4$), quindi la cascata rivela $3$ errori e ne corregge $1$ (prima rivelava $2$).

5. Cascata con la $G$ sistematica

Con $G_s$ come primo codice, $\mathbf c=G_s\mathbf b=\begin{bmatrix}\mathbf b\\A\mathbf b\end{bmatrix}$ e poi $\mathbf c'=G_1\mathbf c=\begin{bmatrix}\mathbf c\\\mathbf r\mathbf c\end{bmatrix}$ (il secondo codice è sistematico: copia i primi $8$ bit e aggiunge un bit). La cascata è $$\mathbf c'=\begin{bmatrix}\mathbf b\\A\mathbf b\\\mathbf r\mathbf c\end{bmatrix}:$$ i primi quattro bit sono $\mathbf b$, quindi $G_1G_s=\begin{bmatrix}I_4\\A'\end{bmatrix}$ è in forma sistematica, con $A'$ ($5\times4$) formata da $A$ e dalla riga di parità. Ogni codice lineare ha una matrice di controllo di parità, e per un codice con $G$ sistematica la matrice standard è $H_c=[A'\mid I_5]$ ($5\times9$): ammette matrice di parità e questa è in forma sistematica (le ultime $5$ colonne sono l'identità).

Errori comuni

• Pensare che permutando le righe si ottenga sempre la forma sistematica: serve una riga $\mathbf e_i^T$ per ogni $i$; altrimenti servono combinazioni di colonne.
• Calcolare $d_{min}$ come minimo peso delle righe di $G$ invece di quello delle parole (le colonne di $G$ sono parole, e le somme di colonne anche).
• Moltiplicare $G\,G_1$ invece di $G_1G$: l'ordine è dalla destra (prima $G$, poi $G_1$) e le dimensioni lo impongono ($G_1$ è $9\times8$, $G$ è $8\times4$).
• Dimenticare che la cascata di due codici lineari è lineare perché il prodotto di matrici è lineare in $\mathbf b$.