Matrice di controllo di parità, sindrome e coset

La matrice generatrice (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 →) serve a codificare. Per decodificare su un canale binario simmetrico (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 →) occorre trovare, per una sequenza ricevuta qualsiasi, la parola di codice più vicina in distanza di Hamming. Confrontare la sequenza con tutte le $2^k$ parole è impraticabile; la matrice di controllo di parità trasforma il problema in un calcolo di poche righe.

Versione per Ing. Elettronica: 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 → (con i vettori per riga: $\mathbf s=\mathbf rH^T$). Per Ing. delle Telecomunicazioni: Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome →.

1. Matrice di controllo di parità

Definizione. Una matrice $H$ di dimensioni $\ell\times n$ è una matrice di controllo di parità del codice lineare $\mathcal C$ se $$H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C\qquad(\mathbf r\in\{0,1\}^n).$$

Ogni riga di $H$ è un'equazione di controllo: la parola deve avere, nelle posizioni dove la riga ha un $1$, un numero pari di $1$. Per esempio la riga $[1,1,1,0,0]$ dice $r_1\oplus r_2\oplus r_3=0$.

Non servono più di $n-k$ righe indipendenti. Se $\ell>n-k$, esistono $n-k$ righe indipendenti $H'$ e le altre sono combinazioni delle prime: se $H'\mathbf r=\mathbf 0$ allora anche le altre righe valgono $\mathbf 0$ per linearità. Per questo $H$ può avere più righe del necessario senza cambiare il codice.

Teorema. $H$ è una matrice di controllo di parità del codice con generatrice $G$ se e solo se $$HG=0\qquad\text{e}\qquad\operatorname{rango}(H)=n-k.$$ (dimensioni: $H$ è $\ell\times n$, $G$ è $n\times k$, $0$ è $\ell\times k$; da cui $\ell\ge n-k$.)

Dimostrazione ($\Leftarrow$). Se $\mathbf r\in\mathcal C$ allora $\mathbf r=G\mathbf b$ e $H\mathbf r=(HG)\mathbf b=\mathbf 0$. Viceversa, se $H\mathbf r=\mathbf 0$, $\mathbf r$ sta nello spazio nullo di $H$ (Nucleo e immagineIl nucleo (vettori mandati in 0) e l'immagine (vettori raggiunti) di una funzione lineare sono sottospazi; f è iniettiva se e solo se Ker f = {0}; dim Ker f + dim Im f = dim V (nullità + rango); l'antimmagine di un vettore è una soluzione particolare più il nucleo.Nucleo e immagine →), che per il teorema della dimensione ha dimensione $n-\operatorname{rango}(H)=k$, quindi contiene $2^k$ sequenze. Ma le $2^k$ parole di codice stanno già nello spazio nullo (primo verso): non c'è posto per altre. Quindi $H\mathbf r=\mathbf 0\Rightarrow\mathbf r\in\mathcal C$.

($\Rightarrow$). Le colonne di $G$ sono parole di codice, e $H\mathbf r=\mathbf 0$ per ogni parola, quindi $HG=0$. Lo spazio nullo di $H$ è il codice, di dimensione $k$, quindi il rango di $H$ è $n-k$. $\square$

Forma sistematica. Se $G=\begin{bmatrix}I_k\\A\end{bmatrix}$ ($A$ è $(n-k)\times k$), una matrice di controllo è $$H=\begin{bmatrix}A\mid I_{n-k}\end{bmatrix}\qquad((n-k)\times n),$$ che ha rango $n-k$ per la presenza dell'identità e verifica $$HG=\begin{bmatrix}A\mid I_{n-k}\end{bmatrix}\begin{bmatrix}I_k\\A\end{bmatrix}=A\,I_k+I_{n-k}\,A=A+A=0$$ (modulo 2 $A+A=0$). È la regola più usata: dalla $G$ sistematica si legge $H$ e viceversa. Le equazioni di controllo sono quelle dei bit di parità: la riga $i$ di $H$ dice "bit di parità $i$ = combinazione di bit di informazione data dalla riga $i$ di $A$".

Esempio. Il codice $(5,2)$ con $G=\begin{bmatrix}1&0\\0&1\\1&1\\1&0\\1&1\end{bmatrix}$ ha $A=\begin{bmatrix}1&1\\1&0\\1&1\end{bmatrix}$ e $$H=\begin{bmatrix}1&1&1&0&0\\1&0&0&1&0\\1&1&0&0&1\end{bmatrix}.$$ Le equazioni sono $c_3=c_1\oplus c_2$, $c_4=c_1$, $c_5=c_1\oplus c_2$ (le tre parità della $G$). Le $4$ parole sono $00000,\,01101,\,10111,\,11010$ e $H$ le annulla tutte (verificato con Python).

Se $H$ non è in forma sistematica. Si portano le colonne dell'identità a destra con permutazioni delle colonne: una permutazione delle colonne di $H$ permuta i bit del codice (altre parole, stesse distanze e stessa probabilità d'errore sul canale senza memoria). Si legge poi $A$ e si scrive $G=\begin{bmatrix}I\\A\end{bmatrix}$ del codice permutato. Le operazioni sulle righe di $H$ (somme di righe, scambi) non cambiano il codice: sono le stesse equazioni scritte in altro modo.

2. Distanza minima dalle colonne di $H$

Se $\mathbf c$ ha peso $w$, il prodotto $H\mathbf c$ è la somma modulo 2 delle $w$ colonne di $H$ nelle posizioni dei suoi $1$. Quindi $\mathbf c\in\mathcal C$ se e solo se quelle colonne sommano a zero:

Teorema. $d_{min}$ è il minimo numero di colonne di $H$ linearmente dipendenti (che sommano a $\mathbf 0$).

Conseguenze, in ordine:

• colonna nulla in $H$: una parola di peso $1$ ($\mathbf e_i\in\mathcal C$), quindi $d_{min}=1$;
• due colonne uguali: la loro somma è $\mathbf 0$, quindi $d_{min}\le2$;
• tutte le colonne non nulle e distinte: nessuna parola di peso $1$ o $2$, quindi $d_{min}\ge3$; vale $d_{min}=3$ se esistono tre colonne con $\mathbf h_i+\mathbf h_j=\mathbf h_k$.

Nell'esempio precedente le colonne sono $[1,1,1],[1,0,1],[1,0,0],[0,1,0],[0,0,1]$: distinte e non nulle, quindi $d_{min}\ge3$; la somma della prima, della seconda e della quarta è $[1,1,1]+[1,0,1]+[0,1,0]=\mathbf 0$ e dà la parola $11010$ di peso $3$: $d_{min}=3$.

3. La sindrome

Definizione. Data la sequenza ricevuta $\boldsymbol\gamma$ (lunga $n$), la sindrome è $$\boldsymbol\sigma=H\boldsymbol\gamma\qquad(n-k\text{ bit}).$$

Poiché $H\mathbf r=\mathbf 0$ solo sulle parole, $\boldsymbol\sigma=\mathbf 0\iff\boldsymbol\gamma\in\mathcal C$: sindrome non nulla = errore rivelato. Scrivendo la ricevuta come parola trasmessa più errore, $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ (il bit $i$ di $\boldsymbol\varepsilon$ è $1$ se il canale ha sbagliato il bit $i$):

$$\boldsymbol\sigma=H\boldsymbol\gamma=\underbrace{H\mathbf c}_{\mathbf 0}+H\boldsymbol\varepsilon=H\boldsymbol\varepsilon.$$

La sindrome dipende solo dall'errore, non dalla parola trasmessa. Se $\boldsymbol\varepsilon$ ha un solo $1$ in posizione $j$, $\boldsymbol\sigma$ è la colonna $j$ di $H$. La decodifica a minima distanza cerca la parola $\hat{\mathbf c}$ più vicina a $\boldsymbol\gamma$, cioè l'errore di peso minimo $\boldsymbol\varepsilon$ tale che $\boldsymbol\gamma+\boldsymbol\varepsilon\in\mathcal C$; ma $\boldsymbol\gamma+\boldsymbol\varepsilon\in\mathcal C$ equivale a $H(\boldsymbol\gamma+\boldsymbol\varepsilon)=\mathbf 0$, cioè a $H\boldsymbol\varepsilon=\boldsymbol\sigma$.

Algoritmo di decodifica con la sindrome.

1. Calcolare $\boldsymbol\sigma=H\boldsymbol\gamma$.
2. Tra tutti i vettori $\boldsymbol\varepsilon\in\{0,1\}^n$ con $H\boldsymbol\varepsilon=\boldsymbol\sigma$, sceglierne uno di peso di Hamming minimo, $\boldsymbol\varepsilon_{min}$.
3. Decodificare $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. (Poi $\hat{\mathbf b}$ si legge dai primi $k$ bit se $G$ è sistematica.)

4. Coset e coset leader

La sindrome ha $n-k$ bit, quindi esistono $2^{n-k}$ sindromi possibili. Se $\boldsymbol\varepsilon_0$ è un errore con sindrome $\boldsymbol\sigma$, gli altri errori con la stessa sindrome sono tutti e soli $$\boldsymbol\varepsilon_0+\mathbf c,\qquad\mathbf c\in\mathcal C$$ perché $H(\boldsymbol\varepsilon_0+\mathbf c)=H\boldsymbol\varepsilon_0+\mathbf 0$ (e viceversa la differenza di due errori con la stessa sindrome sta nel codice).

Definizione. L'insieme $\boldsymbol\varepsilon_0+\mathcal C$ degli errori con sindrome $\boldsymbol\sigma$ è il coset associato a $\boldsymbol\sigma$. Un coset leader è un vettore del coset di peso di Hamming minimo.

Ci sono $2^{n-k}$ coset, ciascuno con $2^k$ vettori: in tutto $2^{n-k}\cdot2^k=2^n$, cioè i coset partizionano lo spazio di tutte le sequenze (il coset della sindrome nulla è il codice stesso). Un coset può avere più leader dello stesso peso: sono sequenze equidistanti da più parole, e il decodificatore ML è in parità; la scelta di uno qualunque non cambia la probabilità d'errore.

Si costruisce la tabella dei coset leader: una riga per sindrome. La decodifica è: calcolo $\boldsymbol\sigma$, leggo $\boldsymbol\varepsilon_{min}$, sommo. Occupa $n(2^{n-k}-1)$ bit (la riga della sindrome nulla non serve), contro i $2^kn$ bit del confronto con tutte le parole.

Esempio 1 (codice di parità $(3,2)$). $G=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}$, $H=[1\ 1\ 1]$ (una sola riga: $n-k=1$). Ci sono $2$ coset:

$\boldsymbol\sigma$	leader	altri vettori del coset
$0$	$000$	$101,\ 011,\ 110$
$1$	$100$	$010,\ 001,\ 111$

(i vettori con sindrome $1$ sono quelli di peso dispari; $100$, $010$ e $001$ sono tutti di peso $1$, scelto $100$.) Si riceve $\boldsymbol\gamma=111$: $\boldsymbol\sigma=1+1+1=1$, quindi $\boldsymbol\varepsilon_{min}=100$ e $\hat{\mathbf c}=111+100=011$. Ma si poteva anche scegliere $010$ (decodificando $101$) o $001$ (decodificando $110$): le tre parole sono equidistanti da $111$. Il codice ha $d_{min}=2$ e non corregge.

Esempio 2 (il codice $(5,2)$ della sezione 1). $H$ ha $n-k=3$ righe, quindi $8$ sindromi; i $8$ coset sono (con la sindrome scritta come $\sigma_1\sigma_2\sigma_3$):

$\boldsymbol\sigma$	leader	coset (tutti i $4$ vettori)
$000$	$00000$	$00000,\ 01101,\ 11010,\ 10111$
$001$	$00001$	$00001,\ 01100,\ 10110,\ 11011$
$010$	$00010$	$00010,\ 11000,\ 10101,\ 01111$
$011$	$00011$ oppure $10100$	$00011,\ 10100,\ 01110,\ 11001$
$100$	$00100$	$00100,\ 01001,\ 10011,\ 11110$
$101$	$01000$	$01000,\ 00101,\ 10010,\ 11111$
$110$	$00110$ oppure $10001$	$00110,\ 10001,\ 01011,\ 11100$
$111$	$10000$	$10000,\ 01010,\ 00111,\ 11101$

I leader di peso $1$ sono i cinque errori singoli: le loro sindromi sono le cinque colonne di $H$ ($111,101,100,010,001$) e coincidono con le righe $111,101,100,010,001$ della tabella. Restano due sindromi, $011$ e $110$, che corrispondono a doppi errori (peso $2$, con due leader ciascuna). La tabella si controlla con Python (enumerando i $32$ vettori).

Decodifiche. $\boldsymbol\gamma=11110$: $\boldsymbol\sigma=H\boldsymbol\gamma=[1+1+1,\ 1+1,\ 1+1]=100$, leader $00100$, $\hat{\mathbf c}=11110+00100=11010\in\mathcal C$. $\boldsymbol\gamma=00111$: $\boldsymbol\sigma=111$, leader $10000$, $\hat{\mathbf c}=10111$. $\boldsymbol\gamma=00011$: $\boldsymbol\sigma=011$, leader $00011$ (decodifica $00000$) o $10100$ (decodifica $10111$): parità, entrambe le parole sono a distanza $2$.

Il numero di coset con leader di peso $1$ è il numero di colonne distinte e non nulle di $H$ (colonne uguali danno la stessa sindrome e stanno nello stesso coset): è la risposta alle domande sulle sindromi con più leader.

5. Probabilità di decodifica corretta con la tabella dei coset

Sul BSC il decodificatore a coset leader decide giusto se e solo se l'errore effettivo $\boldsymbol\varepsilon$ è il leader scelto per la sua sindrome. Quindi, indipendentemente dalla parola trasmessa, $$P(C)=\sum_{\boldsymbol\sigma}P(\boldsymbol\varepsilon=\boldsymbol\varepsilon_{\boldsymbol\sigma})=\sum_{\boldsymbol\sigma}P_{bit}^{\,w_{\boldsymbol\sigma}}(1-P_{bit})^{\,n-w_{\boldsymbol\sigma}},$$ con $w_{\boldsymbol\sigma}$ il peso del leader scelto. Si sommano $2^{n-k}$ termini, uno per coset (con più leader si conta uno solo).

Esempio. Per il codice $(5,2)$: un coset con leader di peso $0$, cinque di peso $1$, due di peso $2$: $$P(C)=(1-P_{bit})^5+5P_{bit}(1-P_{bit})^4+2P_{bit}^2(1-P_{bit})^3.$$ Con $P_{bit}=10^{-2}$: $P(C)=0{,}999214$, cioè $P(E)=7{,}86\cdot10^{-4}$. La limitazione di 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 → ($P(\text{più di }1\text{ errore})=9{,}80\cdot10^{-4}$) conta tutti gli eventi con $2$ o più errori come errori; il decodificatore invece corregge anche $2$ dei $\binom52=10$ doppi errori possibili (quelli scelti come leader). Con $P_{bit}=0{,}1$: $P(E)=0{,}0669$ contro la limitazione $0{,}0815$ (valori controllati con Python).

6. Ricostruire $H$ dai coset

Per i problemi inversi (note sindromi e leader, si chiede $H$) servono due regole:

• un leader di peso $1$ con $1$ in posizione $j$ e sindrome $\boldsymbol\sigma$ dice che la colonna $j$ di $H$ è $\boldsymbol\sigma$;
• un leader di peso $2$ con $1$ in $i$ e $j$ dice che $\mathbf h_i+\mathbf h_j=\boldsymbol\sigma$.

Se il codice è sistematico le ultime $n-k$ colonne sono quelle dell'identità; da una colonna e dalla somma si ricavano le altre. Una sindrome di lunghezza $\ell$ dice che $H$ ha $\ell$ righe, cioè $n-k=\ell$.

Errori comuni

• Calcolare la sindrome con la matrice sbagliata: con la $G$ non si trova nulla di utile, serve $H$ ($(n-k)\times n$).
• Scrivere $H=[I\mid A]$ con $G=\begin{bmatrix}I\\A\end{bmatrix}$: l'identità sta a destra, $H=[A\mid I]$.
• Credere che la sindrome non nulla identifichi sempre l'errore: se la sindrome è una colonna ripetuta di $H$, ci sono più errori singoli possibili (più coset leader).
• Dimenticare che la correzione è garantita solo per gli errori con peso minimo del coset: con più errori del previsto la parola decisa può essere un'altra parola valida.
• Contare tutti i leader di un coset nella probabilità di decodifica corretta: se ne usa uno solo.

Domande d'esame

1. Dato $H$, dimostrare che $d_{min}>2$. Se $H$ non ha colonne nulle (niente parole di peso $1$) né colonne uguali (niente parole di peso $2$, perché $H\mathbf c$ sarebbe la somma di due colonne distinte, diversa da $\mathbf 0$), allora $d_{min}\ge3$. Esercizio - matrice di parità a 4 righe, forma sistematica e permutazione delle colonne (esame del 24 gennaio 2025, es. 188)
2. Un codice lineare ha $n=5$, $k=3$: quante sindromi, quanti coset, quanti vettori per coset? Quanti bit occupa la tabella dei leader? $2^{n-k}=4$ sindromi e coset, $2^k=8$ vettori per coset; $n(2^{n-k}-1)=5\cdot3=15$ bit.
3. Decodificare $\boldsymbol\gamma=111$ con $H=[1\ 1\ 1]$. $\boldsymbol\sigma=1$, leader $100$, $\hat{\mathbf c}=011$ (ma $101$ e $110$ sono ugualmente vicine).

Esercizi svolti

• Esercizio - matrice di parità a 4 righe, forma sistematica e permutazione delle colonne (esame del 24 gennaio 2025, es. 188): matrice di parità a quattro righe, forma sistematica per permutazione delle colonne.
• Esercizio - codice (6,2) con 4-QAM, matrice di parità, decodifica e capacità del canale (esame del 30 agosto 2024, es. 181): decodifica con la sindrome e capacità del BSC realizzato con la 4-QAM.
• Esercizio - codice (5,3) lineare dalle parole di codice, sindrome e periodo di simbolo massimo (esame dell'8 febbraio 2024, es. 175): matrice di parità e decodifica di un codice dato da parole di codice.
• Esercizio - codice (6,2) da matrice di parità non sistematica, decodifica e capacità con 4-QAM (secondo compitino del 12 gennaio 2024, es. 169): matrice di parità non sistematica, decodifica e capacità con la 4-QAM.
• Esercizio - codice (6,4) con colonne uguali in H, coset leader multipli e bit di parità aggiunto (esame del 25 gennaio 2023, es. 154): colonne uguali in H, coset leader multipli e bit di parità aggiunto.
• Esercizio - codice (6,3) accorciato di Hamming, sindrome e peso minimo (esame del 6 settembre 2022, es. 146): codice accorciato di Hamming, sindrome e peso minimo.
• Esercizio - codice (6,3) con G sistematica, numero di coset e bucatura (esame del 29 agosto 2021, es. 128): numero di coset, coset con leader di peso 1 e bucatura.