Esercizio - codice (6,3) con G sistematica, numero di coset e bucatura (esame del 29 agosto 2021, es. 128)

---

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. Matrice di parità e distanza minima

$G$ ha $n=6$ righe e $k=3$ colonne ed è in forma sistematica: $G=\begin{bmatrix}I_3\\A\end{bmatrix}$ con $$A=\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix}.$$ (le parità sono $c_4=b_1+b_2$, $c_5=b_2+b_3$, $c_6=b_1+b_3$). La matrice di controllo è $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&1&0&1&0&0\\0&1&1&0&1&0\\1&0&1&0&0&1\end{bmatrix}.$$ Verifica $HG=0$: per esempio la prima riga di $H$ per la prima colonna di $G$ $[1,0,0,1,0,1]^T$ dà $1+1=0$, per la seconda $[0,1,0,1,1,0]^T$ dà $1+1=0$, per la terza $[0,0,1,0,1,1]^T$ dà $0$; le altre righe sono analoghe (controllato con Python).

Distanza minima da $H$. Le colonne sono $$\mathbf h_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\ \mathbf h_2=\begin{bmatrix}1\\1\\0\end{bmatrix},\ \mathbf h_3=\begin{bmatrix}0\\1\\1\end{bmatrix},\ \mathbf h_4=\begin{bmatrix}1\\0\\0\end{bmatrix},\ \mathbf h_5=\begin{bmatrix}0\\1\\0\end{bmatrix},\ \mathbf h_6=\begin{bmatrix}0\\0\\1\end{bmatrix}.$$ $d_{min}$ è il minimo numero di colonne che sommano a $\mathbf 0$.

• Nessuna colonna è nulla: nessuna parola di peso $1$.
• Le colonne sono tutte diverse: nessuna parola di peso $2$ (la somma di due colonne diverse non è $\mathbf 0$).
• Tre colonne sommano a zero: $\mathbf h_4+\mathbf h_6=[1,0,1]^T=\mathbf h_1$, cioè $\mathbf h_1+\mathbf h_4+\mathbf h_6=\mathbf 0$. La sequenza $[1,0,0,1,0,1]^T$ è una parola di peso $3$.

Quindi $d_{min}=3$ (il codice rivela $2$ errori e ne corregge $1$). Le $8$ parole sono $000000,\ 001011,\ 010110,\ 011101,\ 100101,\ 101110,\ 110011,\ 111000$: pesi $0$, $3$ (quattro parole), $4$ (tre parole).

2. Numero di coset

I coset sono in corrispondenza con le sindromi, e la sindrome è un vettore di $n-k=3$ bit. Quindi i coset sono $$2^{n-k}=2^3=8.$$ Ognuno ha $2^k=8$ vettori, in tutto $8\cdot8=64=2^6$. Tutte le $8$ sindromi si possono ottenere (le colonne di $H$ generano tutto lo spazio di dimensione $3$), quindi non ci sono coset "vuoti".

3. Coset con leader di peso 1

Un errore singolo in posizione $j$ ha per sindrome la colonna $\mathbf h_j$. Le $6$ colonne sono tutte diverse e non nulle, quindi i $6$ errori singoli stanno in $6$ coset diversi e in ciascuno sono l'unico leader (peso $1$ è il minimo possibile per una sindrome non nulla). I $6$ coset hanno leader di peso $1$ e non ci sono altri coset di questo tipo. I coset restanti sono $8-6=2$: quello della sindrome nulla (leader di peso $0$, il codice stesso) e quello della sindrome $[1,1,1]^T$, che non è nessuna delle colonne e ha tre leader di peso $2$ ($001100$, $010001$, $100010$; Python). Il numero di coset con leader di peso $1$ è $6$.

4. Bucare un codice

Bucare significa togliere da tutte le parole i bit in certe posizioni.

Rate. La lunghezza passa da $n$ a $n-s$ (se si tolgono $s$ bit), mentre il numero di parole resta $2^k$ se non si perde informazione: il rate $\frac k{n-s}$ aumenta.

Distanza minima. Due parole diverse $\mathbf c,\mathbf c'$ a distanza $d$ hanno $d$ posizioni diverse. Togliendo un bit si perde una posizione: se quel bit era una delle posizioni in cui differiscono, la distanza scende di $1$; altrimenti resta uguale. Quindi la distanza minima non aumenta mai: diminuisce di al più $1$ per ogni bit tolto, e resta invariata solo se i bit tolti sono uguali in tutte le coppie a distanza minima. Per questo codice ogni posizione compare tra i $1$ di due delle quattro parole di peso $3$: togliere un qualunque bit porta a $d_{min}=2$ (e togliendone due o tre si arriva a $d_{min}=1$; Python, tutte le $6$ posizioni controllate: $d_{min}=2$ e $8$ parole distinte), con rate che sale da $\frac36=0{,}5$ a $\frac35=0{,}6$.

In sintesi: bucare aumenta il rate e diminuisce (o al più lascia invariata) la distanza minima; è il compromesso opposto all'aggiunta di bit di parità (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 →).

Errori comuni

• Dimenticare che le sindromi sono $2^{n-k}$ (le righe di $H$), non $2^k$ né $2^n$.
• Contare i coset con leader di peso $1$ come $n$ anche quando due colonne di $H$ sono uguali: allora sono meno ($n$ meno le colonne ripetute).
• Dire che bucare "aumenta la protezione perché i bit sono meno": toglie ridondanza, la distanza scende.
• Confondere bucatura e accorciamento: l'accorciamento toglie colonne da $H$ e parole dal codice, la bucatura toglie bit da tutte le parole.