Esercizio - codice di Hamming (63,57), bound di Hamming e bit di parità aggiunto (secondo compitino dell'11 gennaio 2022, es. 132)

---

Teoria usata: 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 →, 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. Esistenza del codice di Hamming

Un codice di Hamming con $n$ bit di parola e $k$ di informazione esiste se e solo se $n=2^{n-k}-1$ (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 →): le colonne di $H$ sono tutte le sequenze non nulle di $n-k$ bit, e queste sono $2^{n-k}-1$. Qui $n=63$, $k=57$, $n-k=6$ e $$2^{6}-1=64-1=63=n.$$ Quindi esiste. Equivalentemente il bound di Hamming con $t=1$ vale con l'uguaglianza: $2^k(1+n)=2^{57}\cdot64=2^{57}\cdot2^6=2^{63}=2^n$.

2. Errori corretti e rivelati

Un codice di Hamming ha $d_{min}=3$. Quindi corregge sempre $\left\lfloor\frac{3-1}2\right\rfloor=1$ errore e rivela sempre $d_{min}-1=2$ errori.

3. Matrice di parità sistematica a pesi decrescenti

a) Descrizione. $H$ ha $n-k=6$ righe e $n=63$ colonne ($6\times63$), in forma sistematica $H=[A\mid I_6]$.

• Le ultime $6$ colonne sono quelle dell'identità $I_6$: sequenze di peso $1$.
• Le prime $57$ colonne sono tutte le altre sequenze non nulle di $6$ bit, cioè quelle di peso $\ge2$, e sono tutte diverse. Le sequenze di $6$ bit con peso $w$ sono $\binom6w$: $1$ di peso $6$, $6$ di peso $5$, $15$ di peso $4$, $20$ di peso $3$, $15$ di peso $2$, in tutto $1+6+15+20+15=57$ ✓.
• Con il peso decrescente da sinistra a destra: la prima colonna è $[1,1,1,1,1,1]^T$ (peso $6$), poi le $6$ colonne di peso $5$, le $15$ di peso $4$, le $20$ di peso $3$, le $15$ di peso $2$ e infine, a destra, le $6$ colonne dell'identità (peso $1$, il più basso). (Dentro lo stesso peso l'ordine non è fissato dal testo.)

b) Decodifica. La sequenza $\boldsymbol\gamma$ ha $\gamma_1=1$, gli ultimi sei bit (posizioni $58,\dots,63$) uguali a $1$ e tutti gli altri a $0$. La sindrome è la somma delle colonne di $H$ nelle posizioni dei $1$ (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 →): $$\boldsymbol\sigma=\mathbf h_1+\underbrace{\mathbf h_{58}+\dots+\mathbf h_{63}}_{\text{colonne di }I_6}=\begin{bmatrix}1\\1\\1\\1\\1\\1\end{bmatrix}+\begin{bmatrix}1\\1\\1\\1\\1\\1\end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\\0\\0\end{bmatrix}.$$ (La somma delle colonne di $I_6$ è $[1,\dots,1]^T$, uguale alla prima colonna di $H$; $1+1=0$ in ogni riga. Verificato con Python costruendo $H$ per intero.) La sindrome è nulla: $\boldsymbol\gamma$ è una parola di codice e la decodifica restituisce $\hat{\mathbf c}=\boldsymbol\gamma$ (nessun errore da correggere). È coerente con la struttura sistematica: $\mathbf b=[1,0,\dots,0]^T$ ha le parità uguali alla prima colonna di $A$, tutta di $1$, quindi la parola è proprio $1$ seguito da $56$ zeri e da sei $1$.

4. Il bit aggiunto non basta per $d_{min}=5$

Il nuovo codice ha $n'=64$ e lo stesso $k=57$ (il nuovo bit dipende dai bit di informazione).

Con il bound di Hamming. Se il nuovo codice avesse $d_{min}\ge5$ correggerebbe $t=2$ errori e dovrebbe soddisfare (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 →) $$\frac kn\le1-\frac1n\log_2\sum_{r=0}^{2}\binom nr.$$ Con $n=64$, $k=57$: $\sum=1+64+\binom{64}2=1+64+2016=2081$ e $\log_22081=11{,}02$: $$\frac{57}{64}=0{,}8906\ \overset?\le\ 1-\frac{11{,}02}{64}=0{,}8278.$$ La disuguaglianza è falsa ($0{,}8906>0{,}8278$): un codice $(64,57)$ con $d_{min}\ge5$ non può esistere. Quindi $d_{min}<5$. Detto con le sfere: servirebbero $2^{57}\cdot2081\le2^{64}$, cioè $2081\le2^7=128$, falso.

Alternativa. Aggiungere un bit a un codice può far crescere $d_{min}$ al massimo di $1$ ($3\to4$), mai di $2$: quindi $d_{min}\le4<5$.

Valore esatto. Il bit $c_{64}$ è la somma dei soli bit di informazione, non di tutta la parola. Nel codice di Hamming esiste una parola di peso $3$ con due $1$ nella parte di informazione e uno nella parte di parità: per esempio le colonne $\mathbf h_i=[1,1,0,0,0,0]^T$ e $\mathbf h_j=[1,1,1,0,0,0]^T$ (entrambe di peso $\ge2$, quindi tra le prime $57$) sommano a $[0,0,1,0,0,0]^T$, la terza colonna dell'identità: la sequenza con tre $1$ in quelle posizioni è una parola (controllata con Python, $H\mathbf c=\mathbf 0$). Per questa parola $c_{64}=b_i+b_j=1+1=0$: il peso resta $3$. Quindi il nuovo codice ha $d_{min}=3$ (non $4$): la distanza è $3<5$, e il tasso scende da $\frac{57}{63}=0{,}905$ a $\frac{57}{64}=0{,}891$ senza alcun vantaggio in capacità correttiva.

Errori comuni

• Verificare l'esistenza solo guardando $d_{min}=3$: bisogna mostrare $n=2^{n-k}-1$.
• Mettere nella parte sinistra di $H$ le sequenze di peso $1$: quelle sono l'identità, a destra; la parte sinistra contiene le sequenze di peso $\ge2$.
• Cercare di "correggere" $\boldsymbol\gamma$ senza calcolare la sindrome: la sindrome nulla dice che è una parola.
• Credere che aggiungere un bit di parità di una parte dei bit alzi $d_{min}$ come la parità dell'intera parola: qui ($c_{64}$ somma dei soli bit di informazione) la distanza resta $3$.