Esercizio - codice (6,3) accorciato di Hamming, sindrome e peso minimo (esame del 6 settembre 2022, es. 146)

---

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 di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →, 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 generatrice

$H$ ha $n=6$ colonne e $3$ righe; le ultime tre colonne sono $[1,0,0]^T,[0,1,0]^T,[0,0,1]^T$, cioè $I_3$: $H=[A\mid I_3]$ è in forma sistematica con $n-k=3$, $k=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 →) e $$A=\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}.$$ La generatrice è $G=\begin{bmatrix}I_3\\A\end{bmatrix}$: $$G=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\0&1&1\\1&0&1\\1&1&0\end{bmatrix}.$$ Le parità sono $c_4=b_2+b_3$, $c_5=b_1+b_3$, $c_6=b_1+b_2$. Le $8$ parole sono $000000,\ 001110,\ 010101,\ 011011,\ 100011,\ 101101,\ 110110,\ 111000$ ($HG=0$ e nucleo di $H$ verificati con Python).

2. È un codice di Hamming?

Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle lunghe $n-k$ (Codici di Hamming e bound di HammingIl bound di Hamming (sphere packing) lega tasso e capacità di correzione: $2^k\sum_{r=0}^t\binom nr\le2^n$, cioè $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$, perché le $2^k$ sfere di raggio $t$ attorno alle parole sono disgiunte. Un codice di Hamming ha per colonne di $H$ tutte le sequenze non nulle di $n-k$ bit, ciascuna una volta, quindi $n=2^{n-k}-1$ (parametri $(2^m-1,,2^m-1-m)$: $(7,4)$, $(15,11)$, $(63,57)$, $(255,247)$). Non ha colonne nulle né ripetute e tre colonne sommano a zero: $d_{min}=3$, corregge $1$ errore e ne rivela $2$. Rispetta il bound di Hamming con l'uguaglianza ($t=1$): è un codice perfetto, per cui la probabilità d'errore di parola sul BSC è esattamente $P(\text{almeno 2 errori})$.Codici di Hamming e bound di Hamming →). Qui $n-k=3$ e le sequenze non nulle di $3$ bit sono $2^3-1=7$, ma $H$ ha solo $6$ colonne: $[0,1,1]^T,[1,0,1]^T,[1,1,0]^T,[1,0,0]^T,[0,1,0]^T,[0,0,1]^T$. Manca $[1,1,1]^T$. Quindi non è un codice di Hamming: condizione $n=2^{n-k}-1$ non soddisfatta ($6\ne7$).

È un codice di Hamming $(7,4)$ accorciato: si toglie la colonna $[1,1,1]^T$ da $H$ (equivale a tenere solo le parole con un bit nullo e a eliminarlo) e restano $n=6$, $k=3$. Conserva $d_{min}=3$ (colonne ancora distinte e non nulle) ma non è perfetto: la sindrome $[1,1,1]^T$ non corrisponde a nessun errore singolo.

3. Sindrome di $[1,0,0,1,0,1]^T$

La sindrome è la somma modulo $2$ delle colonne di $H$ nelle posizioni dove la sequenza ha un $1$: posizioni $1,4,6$. $$\boldsymbol\sigma=\mathbf h_1+\mathbf h_4+\mathbf h_6=\begin{bmatrix}0\\1\\1\end{bmatrix}+\begin{bmatrix}1\\0\\0\end{bmatrix}+\begin{bmatrix}0\\0\\1\end{bmatrix}=\begin{bmatrix}1\\1\\0\end{bmatrix}.$$ (riga per riga: $0+1+0=1$; $1+0+0=1$; $1+0+1=0$ ✓.) La sindrome è diversa da $\mathbf 0$: non è una parola di codice. Poiché $[1,1,0]^T=\mathbf h_3$, un errore sul terzo bit la riporterebbe nel codice: $[1,0,0,1,0,1]^T+[0,0,1,0,0,0]^T=[1,0,1,1,0,1]^T=101101\in\mathcal C$.

4. Peso minimo $3$

$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 →), e per un codice lineare coincide con il peso minimo.

• Nessuna colonna è nulla: non esistono parole di peso $1$.
• Le sei colonne sono tutte diverse: non esistono parole di peso $2$ (due $1$ in posizioni $i\ne j$ darebbero $\mathbf h_i+\mathbf h_j\ne\mathbf 0$).

Quindi il peso minimo è almeno $3$. Si trova una parola di peso $3$ con tre colonne che sommano a zero: $\mathbf h_1+\mathbf h_2+\mathbf h_3=[0,1,1]^T+[1,0,1]^T+[1,1,0]^T=[0,0,0]^T$ (riga per riga: $0+1+1=0$, $1+0+1=0$, $1+1+0=0$). La sequenza con tre $1$ nelle posizioni $1,2,3$, cioè $[1,1,1,0,0,0]^T$, è una parola di codice di peso $3$ (infatti $\mathbf b=[1,1,1]$ dà $c_4=c_5=c_6=1+1=0$). Il peso minimo è esattamente $3$. Le parole di peso $3$ sono quattro: $111000$, $001110$, $010101$, $100011$. Lo spettro dei pesi (Python) è: $1$ parola di peso $0$, $4$ di peso $3$ e $3$ di peso $4$ ($011011$, $101101$, $110110$), in tutto $8$.

5. Probabilità di ricevere la parola trovata

Si trasmette $\mathbf 0=000000$ e si riceve $111000$: bit diversi nelle posizioni $1,2,3$, quindi $d_H=3$, e nelle altre $3$ posizioni i bit coincidono. Sul BSC senza memoria $$P[\boldsymbol\xi=111000\mid\mathbf c=\mathbf 0]=P_{bit}^{\,3}(1-P_{bit})^{\,3}=0{,}1^3\cdot0{,}9^3=7{,}29\cdot10^{-4}.$$ (La soluzione del corso scrive "su $5$ bit" ma la lunghezza è $n=6$: il calcolo $0{,}1^3\cdot0{,}9^3=7{,}3\cdot10^{-4}$ è lo stesso.) È la probabilità che il canale commetta proprio quei $3$ errori; ciascuna delle $4$ parole di peso $3$ ha la stessa probabilità.

Errori comuni

• Dire che è un Hamming perché ha $d_{min}=3$: serve che $H$ contenga tutte le colonne non nulle ($n=2^{n-k}-1$).
• Calcolare la sindrome con $G$ o con una riga sola di $H$: serve il prodotto $H\boldsymbol\xi$ completo.
• Prendere $P_{bit}^3$ senza il fattore $(1-P_{bit})^3$ per i bit corretti.
• Pensare che $\mathbf h_i+\mathbf h_j=\mathbf 0$ possa valere con colonne diverse: sommando due colonne diverse non si ottiene mai $\mathbf 0$.