Esercizio - matrice di parità a 4 righe, forma sistematica e permutazione delle colonne (esame del 24 gennaio 2025, es. 188)

---

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

1. Lunghezza e numero delle parole

La lunghezza $n$ è il numero di colonne di $H$: $n=6$. Il numero di parole è $2^k$, dove $n-k=\operatorname{rango}(H)$ (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$ ha $4$ righe, e sono linearmente indipendenti: ciascuna ha un $1$ in una colonna dove tutte le altre righe hanno $0$ (riga $1$: colonna $4$; riga $2$: colonna $3$; riga $3$: colonna $6$; riga $4$: colonna $5$). Una combinazione di righe che desse la riga nulla non potrebbe contenere nessuna riga, perché quella colonna "privata" avrebbe $1$ nel risultato. Quindi $\operatorname{rango}(H)=4=n-k$, cioè $k=2$ e le parole sono $2^2=4$.

Si possono anche scrivere: $H\mathbf c=\mathbf 0$ significa $$\begin{cases}c_1+c_2+c_4=0\\c_3=0\\c_1+c_6=0\\c_1+c_2+c_5=0\end{cases}\ \Longrightarrow\ \mathbf c=[c_1,\,c_2,\,0,\,c_1+c_2,\,c_1+c_2,\,c_1]^T$$ con $c_1,c_2$ liberi. Le $4$ parole sono $000000$, $010110$ ($c_1=0,c_2=1$), $100111$ ($c_1=1,c_2=0$), $110001$ ($c_1=c_2=1$). Notare che $c_3=0$ sempre: la seconda riga di $H$ fissa un bit a zero (un bit inutile, che non trasporta informazione).

2. Le due sequenze sono parole?

Si calcola la sindrome $H\boldsymbol\xi$.

$\boldsymbol\xi_1=[1,0,0,0,1,1]^T$. Riga per riga (tutto modulo $2$):

• riga $[1,1,0,1,0,0]$: $1\cdot1+1\cdot0+0\cdot0+1\cdot0+0\cdot1+0\cdot1=1$;
• riga $[0,0,1,0,0,0]$: $0$;
• riga $[1,0,0,0,0,1]$: $1+1=2\equiv0$;
• riga $[1,1,0,0,1,0]$: $1+0+0+0+1+0=2\equiv0$.

Quindi $H\boldsymbol\xi_1=[1,0,0,0]^T\ne\mathbf 0$ e $\boldsymbol\xi_1$ non è una parola di codice. (Notare che $[1,0,0,0]^T$ è la colonna $4$ di $H$: è la sindrome di un errore singolo in posizione $4$, quindi $\boldsymbol\xi_1$ è a distanza $1$ dalla parola $100111$.)

$\boldsymbol\xi_2=[0,0,1,1]$. Ha lunghezza $4\ne6$: non può essere una parola di un codice a $n=6$ (e $H\boldsymbol\xi_2$ non è nemmeno definito, le dimensioni non sono compatibili).

3. È $d_{min}>2$?

$d_{min}$ è il minimo numero di colonne di $H$ che sommano a $\mathbf 0$ (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 →). Le colonne sono $$\mathbf h_1=\begin{bmatrix}1\\0\\1\\1\end{bmatrix},\ \mathbf h_2=\begin{bmatrix}1\\0\\0\\1\end{bmatrix},\ \mathbf h_3=\begin{bmatrix}0\\1\\0\\0\end{bmatrix},\ \mathbf h_4=\begin{bmatrix}1\\0\\0\\0\end{bmatrix},\ \mathbf h_5=\begin{bmatrix}0\\0\\0\\1\end{bmatrix},\ \mathbf h_6=\begin{bmatrix}0\\0\\1\\0\end{bmatrix}.$$

• Nessuna colonna è nulla: non esistono parole di peso $1$ (una parola con un solo $1$ in posizione $i$ darebbe $H\mathbf c=\mathbf h_i\ne\mathbf 0$).
• Le colonne sono tutte diverse tra loro: non esistono parole di peso $2$ (darebbero $\mathbf h_i+\mathbf h_j=\mathbf 0$, cioè $\mathbf h_i=\mathbf h_j$).

Quindi nessuna parola ha peso $\le2$ e $d_{min}\ge3>2$: sì. Anzi $\mathbf h_1+\mathbf h_2=[0,0,1,0]^T=\mathbf h_6$: le colonne $1,2,6$ sommano a zero, la parola $110001$ ha peso $3$ e $d_{min}=3$ (si legge anche nell'elenco delle parole della sezione 1: pesi $3,4,3$).

4. Forma sistematica per permutazione delle colonne

Si vuole $H'=[A\mid I_4]$: le ultime quattro colonne devono essere $\mathbf e_1,\mathbf e_2,\mathbf e_3,\mathbf e_4$ in quest'ordine (le colonne dell'identità). Colonne disponibili: $\mathbf e_1=[1,0,0,0]^T=\mathbf h_4$, $\mathbf e_2=[0,1,0,0]^T=\mathbf h_3$, $\mathbf e_3=[0,0,1,0]^T=\mathbf h_6$, $\mathbf e_4=[0,0,0,1]^T=\mathbf h_5$. Le posizioni $3,4,5,6$ contengono oggi $\mathbf h_3,\mathbf h_4,\mathbf h_5,\mathbf h_6=\mathbf e_2,\mathbf e_1,\mathbf e_4,\mathbf e_3$: bisogna scambiare le colonne $3$ e $4$ e poi le colonne $5$ e $6$. Due scambi sono il minimo (ogni scambio sistema al più due colonne). L'ordine finale delle colonne originali è $(\mathbf h_1,\mathbf h_2,\mathbf h_4,\mathbf h_3,\mathbf h_6,\mathbf h_5)$: $$H'=\begin{bmatrix}1&1&1&0&0&0\\0&0&0&1&0&0\\1&0&0&0&1&0\\1&1&0&0&0&1\end{bmatrix}=[A\mid I_4],\qquad A=\begin{bmatrix}1&1\\0&0\\1&0\\1&1\end{bmatrix}.$$

La matrice generatrice sistematica corrispondente è $G=\begin{bmatrix}I_2\\A\end{bmatrix}$ (perché $H'=[A\mid I]$): $$G=\begin{bmatrix}1&0\\0&1\\1&1\\0&0\\1&0\\1&1\end{bmatrix}.$$ Verifica $H'G=0$: per esempio la riga $[1,1,1,0,0,0]$ per la prima colonna $[1,0,1,0,1,1]^T$ dà $1+0+1=0$ e per la seconda $[0,1,1,0,0,1]^T$ dà $0+1+1=0$; il prodotto completo (Python) è la matrice nulla.

5. I due codici sono uguali? E le prestazioni?

Le parole non sono le stesse. Il codice di $H'$ si ottiene da quello di $H$ scambiando i bit $3\leftrightarrow4$ e $5\leftrightarrow6$ in tutte le parole. Per esempio $010110\to011001$. Le parole del codice di $H'$ sono $000000,\ 011001,\ 101011,\ 110010$, diverse da quelle di $H$ ($000000,\ 010110,\ 100111,\ 110001$): i due codici sono diversi (sono equivalenti per permutazione dei bit).

La probabilità d'errore è la stessa. Su un canale senza memoria ogni bit viene sbagliato con la stessa probabilità $P_{bit}$ e indipendentemente: la verosimiglianza $P_{bit}^{d_H}(1-P_{bit})^{n-d_H}$ dipende solo dalla distanza di Hamming, e una permutazione dei bit conserva tutte le distanze (permuta le stesse posizioni in entrambe le sequenze). Quindi la decodifica a minima distanza dà lo stesso risultato e la stessa probabilità d'errore.

Conferma numerica (Python, con la tabella dei coset leader, $P(E)=1-\sum_{\boldsymbol\sigma}P_{bit}^{w}(1-P_{bit})^{6-w}$): per entrambi i codici $P(E)=7{,}86\cdot10^{-4}$ con $P_{bit}=10^{-2}$ e $7{,}99\cdot10^{-6}$ con $P_{bit}=10^{-3}$. Questi valori sono uguali a quelli di un codice $(5,2)$ con $d_{min}=3$ perché il bit $c_3$ è sempre nullo: aggiunge solo una posizione in cui un errore ha una sindrome tutta sua (la colonna $\mathbf h_3$) e viene corretto senza danni.

Errori comuni

• Contare le righe di $H$ come $k$: $n-k=\operatorname{rango}(H)$ è il numero di righe indipendenti, $k=n-4=2$.
• Cercare la sindrome di una sequenza di lunghezza sbagliata: $\boldsymbol\xi_2$ non ha $n=6$ bit.
• Dire $d_{min}>2$ "perché $n$ è grande": serve guardare le colonne di $H$ (nessuna nulla, nessuna ripetuta).
• Permutare le colonne di $H$ sperando di ottenere le stesse parole: cambiano le parole, restano le prestazioni.