Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di Hamming

I codici a blocco (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 →) si possono descrivere con una tabella di $2^k$ parole, che diventa impraticabile se $k$ è grande. I codici linearicodici in cui la somma di due parole è ancora una parola: formano uno spazio vettoriale sul campo binario si descrivono con poche righe e si decodificano con un calcolo semplice.

Definizione e distanza minima

Si lavora nel campo binarioi due valori $0$ e $1$ con somma e prodotto modulo $2$: somma e prodotto modulo $2$ ($1+1=0$). Un codice $\mathcal C$ è lineare se $\mathbf c,\mathbf c'\in\mathcal C\Rightarrow\mathbf c\oplus\mathbf c'\in\mathcal C$ (quindi contiene la parola nulla). Conseguenza importante: $$d_H(\mathbf c,\mathbf c')=w_H(\mathbf c\oplus\mathbf c')\quad\Longrightarrow\quad d_{min}=\min_{\mathbf c\ne\mathbf0}w_H(\mathbf c):$$ la distanza minima è il peso minimoil più piccolo numero di uni tra le parole non nulle delle parole non nulle (non servono tutte le coppie).

Esempio di codice non lineare. $00\to0000$, $01\to0111$, $10\to1011$, $11\to1110$: $0111\oplus1011=1100$ ma $1100$ non è una parola ($11\to1110$): non è lineare (anche se è sistematicoi primi $k$ bit della parola di codice coincidono con i bit di informazione).

Matrice generatrice

Una base di $k$ parole di codice linearmente indipendentinessuna è somma modulo $2$ di altre, messe in righe, forma la matrice generatricematrice $k\times n$ le cui righe sono parole di codice: moltiplicata per la parola di informazione dà la parola di codice $G$ ($k\times n$). La parola di informazione $\mathbf m=(m_1,\dots,m_k)$ si codifica con $$\mathbf c=\mathbf m\,G=\sum_im_i\,\mathbf g_i\quad(\text{somma modulo }2\text{ delle righe selezionate}).$$ Il codice è sistematico se $G=[I_k\mid P]$, con $P$ matrice $k\times(n-k)$: i primi $k$ bit sono l'informazione, i restanti $n-k$ sono le parità $\mathbf p=\mathbf mP$. Una $G$ qualsiasi si porta in forma sistematica con somme di righe.

Matrice di controllo di parità e sindrome

La matrice di controllo di paritàmatrice $H$ tale che una parola è di codice se e solo se $\mathbf cH^T=\mathbf 0$ $H$ ($(n-k)\times n$) è tale che $$\mathbf c\in\mathcal C\iff\mathbf cH^T=\mathbf 0,\qquad G H^T=0.$$ Per $G=[I_k\mid P]$: $H=[P^T\mid I_{n-k}]$ (modulo 2 il segno non conta). Se si riceve $\mathbf r=\mathbf c\oplus\mathbf e$ ($\mathbf e$ = vettore di errorevettore con un $1$ nelle posizioni in cui il canale ha sbagliato il bit), la sindromevettore $\mathbf s=\mathbf rH^T$: nullo per le parole di codice e dipendente solo dall'errore $$\mathbf s=\mathbf rH^T=\underbrace{\mathbf cH^T}_{0}\oplus\mathbf eH^T=\mathbf eH^T$$ dipende solo dall'errore, non dalla parola trasmessa. Allora:

• $\mathbf s=\mathbf0$: $\mathbf r$ è una parola di codice (nessun errore, oppure un errore che trasforma una parola in un'altra: non rivelabile);
• $\mathbf s\ne\mathbf0$: errore rivelato;
• per correggere si cerca l'errore più probabile (di peso minimo, il coset leadertra gli errori con una data sindrome, quello di peso minimo, cioè il più probabile) con quella sindrome e lo si sottrae: $\hat{\mathbf c}=\mathbf r\oplus\hat{\mathbf e}$. Per un errore singolo nella posizione $j$, $\mathbf s$ è la $j$-esima colonna di $H$: se le colonne sono tutte diverse e non nulle il codice corregge ogni errore singolo.

Inoltre $d_{min}$ è il minimo numero di colonne di $H$ linearmente dipendenti (la somma di $d_{min}$ colonne è zero): $d_{min}\ge3$ se le colonne sono non nulle e distinte, $d_{min}\ge2$ se sono solo non nulle.

Esempio completo: codice $(4,3)$ e sua estensione

Il codice con parole $X_1=1001$, $X_2=0101$, $X_3=1010$ (e le loro somme, in tutto $8$ parole) ha $k=3$, $n=4$. Riducendo in forma sistematica ($X_3\oplus X_1=0011$) si ottiene $$G=\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\end{pmatrix},\qquad c_4=c_1\oplus c_2\oplus c_3,\qquad H=\begin{pmatrix}1&1&1&1\end{pmatrix}$$ (codice a parità pariil numero di uni di ogni parola è pari). Le $8$ parole hanno peso $0,2,2,2,2,2,2,4$: $d_{min}=2$, rivela $1$ errore, ne corregge $0$.

Si aggiunge un quinto bit $c_5=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}$, $H'=\begin{pmatrix}1&1&1&1&0\\1&1&0&0&1\end{pmatrix}$ (verificato: $G'H'^T=0$). Le $8$ parole di $(5,3)$ hanno pesi $0,2,3,3,3,3,2,4$: ancora $d_{min}=2$ (la parola $00110$ ha peso $2$). Le colonne di $H'$ sono $(1,1),(1,1),(1,0),(1,0),(0,1)$: non sono tutte distinte, quindi non si corregge. Ricevuta $\mathbf r=11010$: $\mathbf s=\mathbf rH'^T=(1+1+0+1,\ 1+1+0)=(1,0)\ne\mathbf0$: errore rivelato; la sindrome $(1,0)$ coincide con le colonne $3$ e $4$ di $H'$, quindi un errore singolo può essere in posizione $3$ ($11010\oplus00100=11110$) o $4$ ($11010\oplus00010=11000$): $11110$ e $11000$ sono entrambe parole di codice ed equidistanti da $\mathbf r$, quindi non si può correggere, solo rivelare.

Codici di Hamming

Per $m\ge2$ il codice di Hammingcodice con $d_{min}=3$ la cui $H$ ha per colonne tutte le sequenze non nulle: corregge un errore ha $n=2^m-1$, $k=2^m-1-m$, $d_{min}=3$ e $H$ con per colonne tutte le $2^m-1$ sequenze binarie non nulle di $m$ bit (quindi colonne distinte e non nulle: $d_{min}\ge3$, e $3$ colonne distinte sommano a zero, per esempio $\mathbf h_1\oplus\mathbf h_2\oplus\mathbf h_3=\mathbf0$ se $\mathbf h_3=\mathbf h_1\oplus\mathbf h_2$). Corregge $t=1$ errore ed è perfettole sfere di Hamming di raggio $t$ attorno alle parole riempiono tutto lo spazio senza sovrapporsi ($2^{n-k}=1+n$). Per $m=3$ si ha l'Hamming $(7,4)$: $$G=\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix},\qquad H=\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}.$$ Decodifica: si calcola $\mathbf s=\mathbf rH^T$; se $\mathbf s\ne\mathbf0$ si inverte il bit $j$ tale che la colonna $j$ di $H$ sia $\mathbf s$. Esempio: $\mathbf m=1011$ dà $\mathbf c=\mathbf mG=(1,0,1,1,0,1,0)$ (parità $m_1\oplus m_2\oplus m_4=0$, $m_1\oplus m_3\oplus m_4=1$, $m_2\oplus m_3\oplus m_4=0$, dalle ultime tre colonne di $G$); se si riceve $\mathbf r=(1,0,1,0,0,1,0)$ (errore in posizione $4$), $\mathbf s=\mathbf rH^T=(1,1,1)$, uguale alla colonna $4$ di $H$: si inverte il bit $4$ e si ritrova $\mathbf c$. (Controllato con Python: tutti i $16\cdot7=112$ errori singoli sono corretti, $d_{min}=3$; con $p=10^{-2}$ la probabilità di parola errata è $2{,}03\cdot10^{-3}$.)

Errori comuni

• Verificare la linearità guardando solo la parola nulla o la somma di una coppia: serve la chiusura per tutte le somme.
• Calcolare $d_{min}$ su tutte le coppie in un codice lineare (basta il peso minimo) o, al contrario, prenderlo da una riga di $G$ qualsiasi.
• Scrivere $H=[P\mid I]$ invece di $[P^T\mid I]$ (la trasposta serve alle dimensioni: $(n-k)\times n$).
• Credere che la sindrome non nulla identifichi sempre l'errore: con colonne uguali o per più errori la correzione è ambigua o sbagliata.