Esercizio - codice (6,4) con colonne uguali in H, coset leader multipli e bit di parità aggiunto (esame del 25 gennaio 2023, es. 154)

---

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 di parole

La lunghezza è il numero di colonne di $H$: $n=6$. $H$ ha $2$ righe e sono indipendenti (la seconda non è nulla e non è uguale alla prima), quindi $\operatorname{rango}(H)=n-k=2$ e $k=4$. Le parole sono $2^k=16$ su $2^6=64$ sequenze.

2. Matrice generatrice e forma sistematica

Le ultime due colonne di $H$ sono $[1,0]^T$ (quinta) e $[0,1]^T$ (sesta): formano l'identità $I_2$. Quindi $H$ è già nella forma $[A\mid I_{n-k}]$ (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 →), con $$A=\begin{bmatrix}1&1&1&1\\1&0&1&0\end{bmatrix}\qquad(\text{le prime quattro colonne}).$$ La matrice generatrice è $G=\begin{bmatrix}I_4\\A\end{bmatrix}$: $$G=\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\end{bmatrix}.$$ È in forma sistematica: i primi quattro bit sono i bit di informazione, gli ultimi due sono le parità $c_5=b_1+b_2+b_3+b_4$ e $c_6=b_1+b_3$. Verifica: $HG=0$ (Python, e a mano: la prima riga di $H$ per la prima colonna di $G$ dà $1+1=0$, per la seconda $1+1=0$, ecc.).

3. Più coset leader per la sindrome $[1,0]^T$?

Le colonne di $H$ sono $$\mathbf h_1=\begin{bmatrix}1\\1\end{bmatrix},\ \mathbf h_2=\begin{bmatrix}1\\0\end{bmatrix},\ \mathbf h_3=\begin{bmatrix}1\\1\end{bmatrix},\ \mathbf h_4=\begin{bmatrix}1\\0\end{bmatrix},\ \mathbf h_5=\begin{bmatrix}1\\0\end{bmatrix},\ \mathbf h_6=\begin{bmatrix}0\\1\end{bmatrix}.$$ Un errore singolo in posizione $j$ ha per sindrome $\mathbf h_j$. La sindrome $[1,0]^T$ compare nelle colonne $2$, $4$ e $5$: i tre errori singoli $\boldsymbol\varepsilon=\mathbf e_2,\mathbf e_4,\mathbf e_5$ hanno la stessa sindrome e lo stesso peso minimo ($1$, la sindrome non è nulla). Quindi sì: esistono tre coset leader per $[1,0]^T$ (e nessun errore di peso $0$). Una sequenza ricevuta con questa sindrome è equidistante da tre parole diverse e il decodificatore a minima distanza è in parità.

(Per completezza: la sindrome $[1,1]^T$ ha due leader, $\mathbf e_1$ ed $\mathbf e_3$; $[0,1]^T$ ne ha uno solo, $\mathbf e_6$; $[0,0]^T$ è il caso senza errore. Le $4$ sindromi sono tutte coperte da errori di peso $\le1$.)

4. Parola più probabile per $\boldsymbol\xi=[1,1,1,1,0,1]^T$

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

• riga $[1,1,1,1,1,0]$: $1+1+1+1+0+0=4\equiv0$;
• riga $[1,0,1,0,0,1]$: $1+0+1+0+0+1=3\equiv1$.

$\boldsymbol\sigma=[0,1]^T$, la colonna $6$, e nessun'altra colonna le è uguale: il coset leader è unico, $\boldsymbol\varepsilon=[0,0,0,0,0,1]^T$. La parola più probabile (a minima distanza di Hamming, 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 →) è $$\hat{\mathbf c}=\boldsymbol\xi+\boldsymbol\varepsilon=[1,1,1,1,0,1]^T+[0,0,0,0,0,1]^T=[1,1,1,1,0,0]^T,$$ che è la parola di $\mathbf b=[1,1,1,1]^T$ (parità $c_5=1+1+1+1=0$, $c_6=1+1=0$).

5. Aggiunta di un bit di parità sui bit di informazione

Il nuovo bit è $c_7=b_1+b_2+b_3+b_4$: si aggiunge a $G$ la riga $[1,1,1,1]$, $$G'=\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&1\end{bmatrix}\qquad(n=7,\ k=4).$$ La nuova matrice di controllo (stessa $A'$ con una riga in più, $A'=\begin{bmatrix}1&1&1&1\\1&0&1&0\\1&1&1&1\end{bmatrix}$) è $H'=[A'\mid I_3]$: $$H'=\begin{bmatrix}1&1&1&1&1&0&0\\1&0&1&0&0&1&0\\1&1&1&1&0&0&1\end{bmatrix}.$$ Verifica $H'G'=0$ con Python.

Distanza. Nella nuova matrice le colonne $1$ e $3$ sono ancora uguali ($[1,1,1]^T$ entrambe), e anche le colonne $2$ e $4$ ($[1,0,1]^T$). Due colonne uguali sommano a $\mathbf 0$: la sequenza con due $1$ nelle posizioni $1$ e $3$ è una parola di codice (è la parola di $\mathbf b=[1,0,1,0]^T$, che con $c_5=c_6=c_7=0$ vale $1010000$). Quindi il nuovo codice ha ancora parole di peso $2$, e $d_{min}=2$ come il codice originale (nel codice originale la stessa coppia di colonne uguali già dava $d_{min}=2$): la distanza è uguale. Il bit aggiunto è la somma dei soli bit di informazione, non di tutta la parola: non rende pari il peso di ogni parola. Per ottenere $d_{min}=3$ servirebbe che nessuna coppia di colonne fosse uguale. Il numero di parole di peso $2$ scende da $4$ a $2$ (spettro dei pesi: Python), ma la distanza minima non cambia.

Errori comuni

• Pensare che aggiungere un bit di parità aumenti sempre di $1$ la distanza: lo fa solo se è la parità di tutta la parola e se la distanza minima era dispari.
• Contare i coset leader solo dal peso del vettore: una sindrome ripetuta in due o più colonne di $H$ ha più leader di peso $1$.
• Decodificare la sequenza con sindrome $[1,0]^T$ scegliendo un errore a caso: la parola decodificata non è garantita.
• Dimenticare di aggiungere la colonna $\mathbf e_3$ (la nuova identità $I_3$) alla matrice di controllo.