Esercizio 30codice a blocco lineare (4,3) esteso a (5,3), matrici e sindrome (temi d'esame gennaio e luglio 2017)

---

Teoria usata: Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di HammingUn codice a blocco è lineare se la somma (bit a bit, modulo 2) di due parole di codice è una parola di codice. Si descrive con la matrice generatrice $G$ ($k\times n$, $\mathbf c=\mathbf mG$) e con la matrice di controllo di parità $H$ ($(n-k)\times n$, $G H^T=0$); in forma sistematica $G=[I_k\mid P]$ e $H=[P^T\mid I_{n-k}]$. La distanza minima è il peso minimo delle parole non nulle. La sindrome $\mathbf s=\mathbf rH^T$ dipende solo dall'errore: se è nulla la parola è valida, altrimenti identifica l'errore (un solo errore ha per sindrome la colonna di $H$ corrispondente). I codici di Hamming $(2^m-1,,2^m-1-m)$ hanno $d_{min}=3$.Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di Hamming →, Codifica di canale - codici a blocco, distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza ai bit per rivelare o correggere gli errori del canale. Un codice a blocco $(n,k)$ trasforma $k$ bit in $n$ bit (rendimento $R_c=\frac kn$). Con la distanza di Hamming minima $d_{min}$ il codice rivela fino a $d_{min}-1$ errori e ne corregge $t=\left\lfloor\frac{d_{min}-1}2\right\rfloor$ (decodifica a minima distanza). Vale il limite di Singleton $d_{min}\le n-k+1$. Su un canale binario simmetrico con errore $p$, la probabilità di parola sbagliata è $P_w\le\sum_{i>t}\binom nip^i(1-p)^{n-i}$ e, con $p$ piccola, $P_{bit}\approx\frac{d_{min}}n\binom n{t+1}p^{t+1}$.Codifica di canale - codici a blocco, distanza minima, rivelazione e correzione →.

(1) Matrici $G$ e $H$

Le tre parole sono linearmente indipendenti, quindi generano un codice con $2^3=8$ parole. In forma sistematica $G=[I_3\mid P]$: servono parole che abbiano i primi $3$ bit uguali a $100$, $010$, $001$.

• $100\to X_1=1001$ ✓ (parità $1$);
• $010\to X_2=0101$ ✓ (parità $1$);
• $001$: $X_3\oplus X_1=1010\oplus1001=0011$ ✓ (parità $1$).

$$G=\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\end{pmatrix}=[I_3\mid P],\quad P=\begin{pmatrix}1\\1\\1\end{pmatrix},\qquad H=[P^T\mid I_1]=\begin{pmatrix}1&1&1&1\end{pmatrix}.$$ Il bit di parità è $c_4=c_1\oplus c_2\oplus c_3$ (codice a parità pari): $\mathbf cH^T=c_1\oplus c_2\oplus c_3\oplus c_4=0$ per ogni parola.

(2) Rivelazione e correzione

Le $8$ parole sono $0000,\,0011,\,0101,\,0110,\,1001,\,1010,\,1100,\,1111$, di pesi $0,2,2,2,2,2,2,4$: $d_{min}=2$ (codice lineare: peso minimo $\ne0$). Il codice rivela $d_{min}-1=1$ errore e corregge $\left\lfloor\frac{2-1}2\right\rfloor=0$ errori. (Un errore singolo dà una parola a peso dispari, non valida; due errori danno una parola di peso pari che può essere valida.)

(3) Il codice esteso $(5,3)$

Si aggiunge $c_5=c_1\oplus c_2$. Le parti di parità diventano $\mathbf p=(c_4,c_5)=(c_1\oplus c_2\oplus c_3,\ c_1\oplus c_2)$: $$G'=\begin{pmatrix}1&0&0&1&1\\0&1&0&1&1\\0&0&1&1&0\end{pmatrix},\qquad P'=\begin{pmatrix}1&1\\1&1\\1&0\end{pmatrix},\qquad H'=[P'^T\mid I_2]=\begin{pmatrix}1&1&1&1&0\\1&1&0&0&1\end{pmatrix}.$$ Verifica: $G'H'^T=0$ (righe di $G'$: $10011\to(1+1,\,1+1)=(0,0)$; $01011\to(0,0)$; $00110\to(1+1,\,0)=(0,0)$). Le $8$ parole di $(5,3)$ sono $00000,\,00110,\,01011,\,01101,\,10011,\,10101,\,11000,\,11110$, di pesi $0,2,3,3,3,3,2,4$: $d_{min}=2$ (le parole $00110$ e $11000$ hanno peso $2$). Il rendimento scende a $\frac35$ ma la distanza non cresce: l'estensione non è utile per la correzione.

(4) Sindrome della sequenza $11010$

$$\mathbf s=\mathbf rH'^T=\left(1\oplus1\oplus0\oplus1\oplus0,\ \ 1\oplus1\oplus0\oplus0\oplus0\right)=(1,\,0)\ne(0,0).$$ Errore rivelato. Per cercare un errore singolo si confronta $\mathbf s$ con le colonne di $H'$: $\mathbf h_1=(1,1)$, $\mathbf h_2=(1,1)$, $\mathbf h_3=(1,0)$, $\mathbf h_4=(1,0)$, $\mathbf h_5=(0,1)$. La sindrome $(1,0)$ coincide con $\mathbf h_3$ e con $\mathbf h_4$: l'errore può essere nella posizione $3$ (parola $11010\oplus00100=11110$) o nella $4$ ($11010\oplus00010=11000$), che sono due parole di codice ugualmente vicine a $\mathbf r$ (distanza $1$). Il codice non può correggere (è coerente con $d_{min}=2$): la parola decodificata non è determinabile in modo univoco; si può solo dire che c'è un errore e chiedere la ritrasmissione, oppure scegliere a caso tra $11110$ e $11000$ ($50\%$ di probabilità di sbagliare).

(Verificato con Python: $G'H'^T=0$, $d_{min}=2$ per entrambi i codici, sindrome $(1,0)$.)

Errori comuni

• Dimenticare che per un codice lineare $d_{min}$ è il peso minimo delle parole non nulle ($2$ qui), e rispondere che corregge un errore.
• Calcolare la sindrome con $H$ del codice $(4,3)$ su una parola di $5$ bit: serve $H'$ ($2\times5$).
• Concludere che la sindrome identifica sempre la posizione dell'errore: colonne uguali ($\mathbf h_3=\mathbf h_4$) lasciano ambiguità.
• Credere che aggiungere un bit di parità aumenti la distanza: qui $d_{min}$ resta $2$.