Codici a blocco lineari e sindrome

Nella nota Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione → un codice era un elenco di $2^k$ parole, e per trovare $d_{min}$ bisognava confrontare tutte le coppie; per decodificare, cercare la parola più vicina in tutto l'elenco. Con $k=16$ sono $65\,536$ parole: impraticabile. I codici lineari aggiungono una struttura algebrica che rende tutto più semplice: si descrivono con una matrice, $d_{min}$ si trova con un passaggio solo e la decodifica si fa con una piccola tabella.

Vedi anche la versione per Ing. Elettronica (convenzione a vettore riga): 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 →.

Algebra su $\mathbb Z_2$

L'insieme $\mathcal A=\mathbb Z_2=\{0,1\}$ con il prodotto AND (indicato con $\cdot$) e la somma XOR (indicata con $+$, ovvero somma modulo $2$: $0+0=0$, $0+1=1$, $1+1=0$) è un campo (CampiUn campo è un insieme di numeri con somma e prodotto che rispettano le regole usuali (associativa, commutativa, neutri, opposti, inversi, distributiva): è ciò che serve per risolvere le equazioni di primo grado. Esempi: Q, R, C e i campi finiti.Campi →). Dal fatto che $1+1=0$ segue che ogni elemento è l'opposto di sé stesso, per cui $-x=x$ e la sottrazione coincide con la somma: $\boldsymbol\gamma_1-\boldsymbol\gamma_2=\boldsymbol\gamma_1+\boldsymbol\gamma_2$ (e per questo $A$ e $-A$ sono la stessa matrice).

L'insieme $\mathbb Z_2^n$ delle sequenze di $n$ bit, con la somma bit a bit e il prodotto per gli scalari $0$ e $1$, è uno spazio vettoriale (Spazi vettorialiUno spazio vettoriale su un campo K è un insieme con una somma di vettori e un prodotto per scalari che rispettano 7 proprietà. Esempi fondamentali: K^n (somma componente per componente), le funzioni da R in R, i polinomi.Spazi vettoriali →) di dimensione $n$ e con $2^n$ elementi. Non ha un prodotto scalare, ma ha la distanza di Hamming $d_H$, che induce una norma:

Definizione (peso di Hamming). $\|\mathbf c\|_H=d_H(\mathbf c,\mathbf 0)=$ numero di bit uguali a $1$ in $\mathbf c$ $=\sum_{j=1}^nc_j$ (somma in $\mathbb R$, non modulo $2$), dove $\mathbf 0$ è la parola nulla (tutti zeri). Vale $d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)=\|\boldsymbol\gamma_1-\boldsymbol\gamma_2\|_H=\|\boldsymbol\gamma_1+\boldsymbol\gamma_2\|_H$.

Esempio. $\boldsymbol\gamma_1=1011$, $\boldsymbol\gamma_2=0110$: $\boldsymbol\gamma_1+\boldsymbol\gamma_2=1101$, peso $3=d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)$ (le posizioni $1,2,4$ differiscono).

Codice lineare

Definizione (codice lineare). Un codice a blocco è lineare se l'insieme delle parole $\mathcal C=\mu_C(\mathbb Z_2^k)$ è un sottospazio (Sottospazi vettorialiUn sottospazio vettoriale è un sottoinsieme che è spazio vettoriale con le stesse operazioni: basta che sia chiuso per somma e per prodotto per scalari. Deve contenere il vettore nullo. In R^2 i sottospazi sono {0}, le rette per l'origine e tutto R^2.Sottospazi vettoriali →) di $\mathbb Z_2^n$.

Un sottospazio è chiuso rispetto alle combinazioni lineari; in $\mathbb Z_2$ l'unica combinazione lineare non banale è la somma, quindi la definizione si riduce a: $$\boldsymbol\gamma_1,\boldsymbol\gamma_2\in\mathcal C\ \Rightarrow\ \boldsymbol\gamma_1+\boldsymbol\gamma_2\in\mathcal C.$$ Corollari: vale anche $\boldsymbol\gamma_1-\boldsymbol\gamma_2\in\mathcal C$ (è la stessa cosa) e soprattutto $\mathbf 0=\boldsymbol\gamma+\boldsymbol\gamma\in\mathcal C$: ogni codice lineare contiene la parola nulla. È un criterio comodo per scartare i codici non lineari: se $\mathbf 0\notin\mathcal C$ il codice non è lineare.

Teorema (distanza minima di un codice lineare). In un codice lineare $d_{min}$ coincide con il peso di Hamming minimo delle parole non nulle: $$d_{min}=\min_{\boldsymbol\gamma\in\mathcal C\setminus\{\mathbf0\}}\|\boldsymbol\gamma\|_H.$$ Dimostrazione. Per definizione $d_{min}=\min_{\gamma_1\ne\gamma_2}d_H(\gamma_1,\gamma_2)=\min\|\gamma_1-\gamma_2\|_H$. Basta mostrare che l'insieme delle differenze $\boldsymbol\gamma_1-\boldsymbol\gamma_2$ con $\boldsymbol\gamma_1\ne\boldsymbol\gamma_2$ è esattamente l'insieme delle parole di codice non nulle. Una differenza è una parola di codice (linearità) e non è nulla perché $\gamma_1\ne\gamma_2$. Viceversa, sia $\boldsymbol\gamma\in\mathcal C$ non nulla: allora $\boldsymbol\gamma=\boldsymbol\gamma-\mathbf0$ è la differenza di due parole del codice, perché $\mathbf0\in\mathcal C$. $\square$

Il vantaggio è grande: invece di confrontare tutte le coppie ($\sim2^{2k-1}$) si fa un solo passaggio sulle $2^k-1$ parole non nulle.

Esempio. Il codice $\mu_1$ dell'Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato, $\{0011,0110,1010,1100\}$, non è lineare: manca $\mathbf 0$. Il $\mu_2$, $\{0000,0110,1011,1101\}$, lo è: pesi $0,2,3,3$, $d_{min}=2$.

Rappresentazione matriciale

Se $\mu_C:\mathbb Z_2^k\to\mathbb Z_2^n$ è una mappa lineare (Funzioni lineari e isomorfismiUna funzione tra spazi vettoriali è lineare se rispetta somma e prodotto per uno scalare; manda 0 in 0, è determinata dalle immagini di una base e si chiama isomorfismo quando è anche biiettiva.Funzioni lineari e isomorfismi →), ogni bit di codice è combinazione lineare di bit di informazione: $$c_i=g_{i1}b_1+g_{i2}b_2+\dots+g_{ik}b_k\quad(i=1,\dots,n),\qquad g_{ij}\in\{0,1\},$$ cioè, con i vettori scritti in colonna ($\mathbf c$ è $n\times1$, $\mathbf b$ è $k\times1$), $$\mathbf c=G\,\mathbf b,\qquad G\ \text{matrice } n\times k.$$ (Alcuni testi usano la convenzione a riga, con $G$ trasposta e post-moltiplicata: $\mathbf c=\mathbf bG^T$; per questo la $G$ di altri libri e delle note di Elettronica ha le righe e le colonne scambiate.) Per una codifica invertibile $G$ ha rango pieno $=k$ (Operazioni tra matriciLe matrici m×n formano uno spazio vettoriale (somma e prodotto per scalare elemento per elemento); il prodotto righe per colonne corrisponde alla composizione di funzioni lineari, è associativo ma non commutativo; la trasposta scambia righe e colonne e (AB)^T = B^T A^T.Operazioni tra matrici →, 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 →). Poiché le parole di informazione sono sempre equiprobabili, interessa solo l'insieme $\mathcal C$ delle parole, che è anche lo span (il sottospazio generato) delle colonne di $G$.

Definizione (matrice generatrice). Se si prendono $k$ parole di codice linearmente indipendenti $\boldsymbol\gamma_1,\dots,\boldsymbol\gamma_k$ (Combinazioni lineari e dipendenza lineareUna combinazione lineare è una somma di vettori moltiplicati per scalari. I vettori sono linearmente indipendenti se l'unica combinazione che dà il vettore nullo è quella con tutti i coefficienti nulli; altrimenti sono dipendenti, e allora uno di essi è combinazione lineare degli altri.Combinazioni lineari e dipendenza lineare →) e le si mettono in colonna si ottiene $G=[\boldsymbol\gamma_1\ \boldsymbol\gamma_2\ \dots\ \boldsymbol\gamma_k]$ ($n\times k$), una matrice generatrice del codice. Le $\boldsymbol\gamma_j$ sono una base di $\mathcal C$ (Generatori e basiDei vettori generano V se ogni vettore di V è loro combinazione lineare; una base è un insieme di generatori linearmente indipendenti, e allora ogni vettore si scrive in modo unico come combinazione dei vettori di base. Lemma dello scambio: i vettori indipendenti non sono mai più dei generatori.Generatori e basi →, DimensioneTutte le basi di uno spazio vettoriale hanno lo stesso numero di vettori, la dimensione (dim K^n = n). Da ogni sistema di generatori si estrae una base, ogni insieme di vettori indipendenti si completa a una base, e in dimensione n bastano n vettori indipendenti (o n generatori) per avere una base.Dimensione →: $\dim\mathcal C=k$).

Ci sono più matrici generatrici dello stesso codice (basta scegliere un'altra base): la generazione riguarda l'insieme delle parole, non la mappa specifica $\mu_C$, che cambia.

Esempio. Il codice $\mu_2$ dell'esercizio, $c_1=b_1$, $c_2=b_2$, $c_3=b_1+b_2$, $c_4=c_2+c_3=b_1$, ha $$G=\begin{pmatrix}1&0\\0&1\\1&1\\1&0\end{pmatrix}.$$ La prima colonna è $(1,0,1,1)^T=1011$ (la parola associata a $\mathbf b=10$), la seconda $(0,1,1,0)^T=0110$ (per $\mathbf b=01$); la parola per $\mathbf b=11$ è la loro somma $1101$, e per $\mathbf b=00$ si ha $0000$.

Codici sistematici

Teorema (forma di $G$ per un codice sistematico). Un codice lineare sistematico ammette una matrice generatrice $$G=\begin{pmatrix}I_k\\ A\end{pmatrix},$$ con $I_k$ la matrice identità $k\times k$ e $A$ una matrice $(n-k)\times k$ detta matrice di parità. Dimostrazione. Per definizione di sistematico $c_j=b_j$ per $1\le j\le k$: le prime $k$ righe di $G$ sono $I_k$. Gli altri $n-k$ bit sono combinazioni lineari dei $b_j$ e le loro righe formano $A$. $\square$

Esempi. Ripetizione ($c_j=b_j$, $c_{j+k}=b_j$, …, $m$ volte): $G=\begin{pmatrix}I_k\\\vdots\\I_k\end{pmatrix}$ ($m$ blocchi), $A=(m-1)$ copie di $I_k$. Un bit di parità $c_{k+1}=\sum_{j=1}^kb_j$: $G=\binom{I_k}{1\ 1\ \dots\ 1}$, $A$ è il vettore riga di soli uni.

Codice di Hamming $(7,4)$ (esempio guida del capitolo), sistematico con $$G=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\hline1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix},\quad A=\begin{pmatrix}1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}.$$ I bit di parità sono $c_5=b_1+b_2+b_4$, $c_6=b_1+b_3+b_4$, $c_7=b_2+b_3+b_4$. Dalle colonne $\boldsymbol\gamma_1=1000110$, $\boldsymbol\gamma_2=0100101$, $\boldsymbol\gamma_3=0010011$, $\boldsymbol\gamma_4=0001111$ si vedono subito $4$ parole oltre alla nulla; le altre $11$ sono le somme, ad esempio $\boldsymbol\gamma_5=\boldsymbol\gamma_1+\boldsymbol\gamma_2=1100011$. Tutte le $16$ parole: $0000000,\ 0001111,\ 0010011,\ 0011100,\ 0100101,\ 0101010,\ 0110110,\ 0111001,\ 1000110,\ 1001001,\ 1010101,\ 1011010,\ 1100011,\ 1101100,\ 1110000,\ 1111111$ (enumerate al calcolatore).

Come si trova $d_{min}$ guardando $G$

In linea di principio si guardano tutte le parole e si prende il peso minimo: per il $(7,4)$ i pesi sono $0$ (una parola), $3$ (sette parole), $4$ (sette parole), $7$ (una parola): $d_{min}=3$. Dalla sola $G$ si può dire $d_{min}\le3$ (le colonne $\boldsymbol\gamma_1,\boldsymbol\gamma_2,\boldsymbol\gamma_3$ hanno peso $3$ e la $\boldsymbol\gamma_4$ ha peso $4$). Per escludere $d_{min}=1$ e $2$ ci sono trucchi:

• non può essere $1$: una parola di peso $1$ avrebbe un solo bit di informazione uguale a $1$ e tutte le parità nulle, cioè una colonna di $A$ nulla; qui nessuna colonna di $A$ è nulla (e una parola con parte sistematica nulla è la parola nulla, che non conta);
• non può essere $2$: una parola di peso $2$ avrebbe o (i) due bit di informazione a $1$ e parità nulle, cioè due colonne di $A$ uguali (la somma di due colonne uguali è nulla), oppure (ii) un solo bit di informazione a $1$ e una sola parità a $1$, cioè una colonna di $A$ di peso $1$. Le colonne di $A$ del $(7,4)$ sono $110,\ 101,\ 011,\ 111$: tutte diverse e di peso $\ge2$.

Un modo più sistematico, con $H$, è nella sezione sulla matrice di controllo.

Permutazioni elementari ed equivalenza

Si consideri la matrice $H_{ij}$ ottenuta dall'identità scambiando le righe $i$ e $j$ (una matrice di permutazione), e la matrice $K_{ij}$ ottenuta dall'identità aggiungendo un $1$ fuori diagonale (che somma una riga o una colonna a un'altra). Come operazioni su $G$:

• post-moltiplicando per matrici $k\times k$ ($G'=GH_{ij}$ oppure $G'=GK_{ij}$) si operano trasformazioni elementari sulle colonne: $H_{ij}$ scambia le colonne $i$ e $j$ (stessa base, stesso sottospazio $\mathcal C$), $K_{ij}$ sostituisce la colonna $\boldsymbol\gamma_j$ con $\boldsymbol\gamma_i+\boldsymbol\gamma_j$ (sempre una base di $\mathcal C$). Cambia la mappa $\mu_C$ ma non il codice.
• pre-moltiplicando per matrici $n\times n$ ($G'=H_{ij}G$) si scambiano le righe, cioè si permutano i bit delle parole di codice: il sottospazio cambia, ma si ottiene un codice equivalente, con gli stessi pesi, la stessa $d_{min}$ e gli stessi poteri di rivelazione e correzione. Lo stesso vale per $K_{ij}$.

Esempio. $\mathcal C=\{0000,0101,1010,1111\}$ scambiando i bit $2$ e $3$ diventa $\mathcal C'=\{0000,0011,1100,1111\}$: stessi pesi $(0,2,2,4)$, $d_{min}=2$.

Lemma. Ogni codice lineare ha un equivalente sistematico. Idea della dimostrazione. Data una $G$ a rango pieno, con operazioni elementari su righe e colonne (l'eliminazione di Gauss-Jordan, Eliminazione di GaussCon tre operazioni elementari sulle righe (scambio, moltiplicazione per uno scalare non nullo, somma di un multiplo di un'altra riga) ogni matrice si riduce a scala senza cambiare il rango; serve a calcolare ranghi, risolvere sistemi, trovare relazioni di dipendenza e matrici che riducono a scala.Eliminazione di Gauss →) la si riduce a $G'=\binom{I_k}{A}$.

Teorema (limite di Singleton). Per ogni codice lineare $(n,k)$, $d_{min}\le n-k+1$. Dimostrazione. Si usa il lemma. Ogni colonna di $G'=\binom{I_k}{A}$ è una parola di codice che ha al più un $1$ nella parte superiore ($I_k$) e al più $n-k$ uni nella parte inferiore ($A$): peso $\le1+(n-k)$. Quindi esiste una parola non nulla di peso $\le n-k+1$ e $d_{min}\le n-k+1$. $\square$

Esempi. $(7,4)$: $3\le4$. Ripetizione $(3,1)$: $3\le3$ (uguaglianza). Un bit di parità $(5,4)$: $2\le2$. Il limite è piuttosto lasco, ma conferma che per avere $d_{min}$ alta bisogna sacrificare il tasso: $d_{min}\uparrow\Rightarrow k/n\downarrow$.

Matrice di controllo di parità e sindrome

Definizione (matrice di controllo di parità). Per un codice lineare $(n,k)$ la matrice di controllo di parità è una matrice $H$ di tipo $\ell\times n$ (in generale $\ell\ge n-k$, in pratica $\ell=n-k$) tale che $$H\mathbf c=\mathbf 0\iff\mathbf c\in\mathcal C,$$ dove $\mathbf 0$ è il vettore nullo con $\ell$ elementi. (Non va confusa con la matrice di parità $A$, che è un'altra cosa.)

Se si conosce $H$ si ha un controllo rapido: ricevuta $\tilde{\mathbf c}$ ci si chiede se è una parola di codice e si calcola il vettore $$\boldsymbol\sigma=H\tilde{\mathbf c},\qquad\text{detto \textbf{sindrome} dell'errore}\ (\text{error syndrome}).$$ Se la sindrome è nulla non ci sono errori (a meno che l'errore non sia non rivelato, cioè $\tilde{\mathbf c}$ è un'altra parola di codice); se è non nulla, l'errore è rivelato.

Teorema (proprietà caratteristica). $H$ ($\ell\times n$) è la matrice di controllo del codice con matrice generatrice $G$ se e solo se $HG=O$ e $\mathrm{rank}(H)=n-k$. Dimostrazione (sketch). ($\Rightarrow$) $G$ è fatta di parole di codice, quindi $H\boldsymbol\gamma_j=\mathbf0$ per ogni colonna: $HG=O$ (la matrice nulla $\ell\times k$). ($\Leftarrow$) $\mathcal C$ è lo 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 ha dimensione $n-\mathrm{rank}(H)=n-(n-k)=k$; e $HG=O$ dice che lo span di $G$ (dimensione $k$) è contenuto nel nucleo di $H$: avendo la stessa dimensione coincidono. $\square$

Questo giustifica $\ell=n-k$ nei casi pratici (per avere rango pieno senza righe ridondanti).

Teorema (matrice $H$ di un codice sistematico). Se $G=\binom{I_k}{A}$ allora $$H=[\,-A\mid I_{n-k}\,]=[\,A\mid I_{n-k}\,]\quad\text{in }\mathbb Z_2.$$ Dimostrazione. $H$ ha rango $n-k$ per la presenza di $I_{n-k}$. Inoltre $HG=[-A\mid I_{n-k}]\binom{I_k}{A}=-A\,I_k+I_{n-k}A=-A+A=O$. Per la proprietà caratteristica $H$ è la matrice di controllo. $\square$ (Il teorema vale anche sui campi non binari, dove il segno conta.)

Esempio. Hamming $(7,4)$ ($n-k=3$): $$H=[A\mid I_3]=\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}.$$ Controllo su $\boldsymbol\gamma_1=1000110$: la prima riga di $H$ somma i bit $1,2,4,5$ di $\boldsymbol\gamma_1$ ($1+0+0+1=0$), la seconda i bit $1,3,4,6$ ($1+0+0+1=0$), la terza i bit $2,3,4,7$ ($0+0+0+0=0$): $H\boldsymbol\gamma_1=\mathbf0$. Lo stesso vale per $\boldsymbol\gamma_2,\boldsymbol\gamma_3,\boldsymbol\gamma_4$ ($HG=O$, verificato al calcolatore). Le colonne di $H$ sono $110,\ 101,\ 011,\ 111,\ 100,\ 010,\ 001$: tutte le $7$ sequenze non nulle di $3$ bit, e quindi tutte distinte e non nulle.

Come $H$ dà $d_{min}$

$H\mathbf c=\sum_jc_j\mathbf h_j$ ($\mathbf h_j$ = colonna $j$ di $H$): una parola di codice di peso $w$ corrisponde a $w$ colonne di $H$ che sommano a $\mathbf0$. Quindi $d_{min}$ è il minimo numero di colonne di $H$ linearmente dipendenti. Se nessuna colonna è nulla, $d_{min}\ge2$; se inoltre sono tutte distinte, nessuna coppia somma a zero e $d_{min}\ge3$. Per il $(7,4)$ le colonne sono distinte e non nulle, quindi $d_{min}\ge3$; e la terna $\mathbf h_1,\mathbf h_2,\mathbf h_3$ è dipendente: $110+101+011=000$. Quindi $d_{min}=3$. Questo è il criterio con cui, nella simulazione d'esame 2013, si vede quanti errori un codice può rivelare.

Un'analogia: la prova del nove. Per controllare $33108+62613=95721$ si sostituiscono i numeri con la somma ripetuta delle loro cifre (con $9\to0$): $33108\to3+3+1+0+8=15\to6$; $62613\to18\to9\to0$; $95721\to24\to6$. Se $6+0=6$ coincide con $6$ i numeri sono "probabilmente" giusti; se non coincide c'è sicuramente un errore. È il calcolo di un numero modulo $9$ (perché $10^i=9\dots9+1$, quindi $a\cdot10^4+\dots+e=9999a+\dots+9d+(a+b+c+d+e)$): la differenza è la sindrome, e se non è divisibile per $9$ c'è un errore.

Decodifica con la sindrome

La sindrome è un vettore di $n-k$ bit: ci sono $2^{n-k}$ sindromi possibili, ma i vettori $\tilde{\mathbf c}$ sono $2^n$. Quindi più vettori hanno la stessa sindrome: quanti? $2^k$. Infatti $H\tilde{\mathbf c}=\boldsymbol\sigma$ è un sistema di $n-k$ equazioni in $n$ incognite (sottodeterminato) con $2^k$ soluzioni; verifica: per $\boldsymbol\sigma=\mathbf0$ le soluzioni sono le parole di codice, $2^k$.

"Avere la stessa sindrome" è una relazione di equivalenza (riflessiva, simmetrica, transitiva) su $\mathbb Z_2^n$, e le relazioni di equivalenza inducono partizioni. (Altro esempio: $\mathbb Z_2$ come partizione di $\mathbb Z$ nelle classi dei resti modulo $2$, pari e dispari.)

Definizione (laterale, o coset). Ognuna delle classi della partizione si chiama coset: $\mathbb Z_2^n$ è partizionato in $2^{n-k}$ coset, ciascuno associato a una sindrome e con $2^k$ elementi; uno di essi (sindrome nulla) è l'insieme delle parole di codice $\mathcal C$.

Definizione (coset leader). A ogni sindrome $\boldsymbol\sigma$ si associa un elemento speciale $$\varepsilon(\boldsymbol\sigma)=\arg\min_{\mathbf c\in\mathbb Z_2^n:\ H\mathbf c=\boldsymbol\sigma}\|\mathbf c\|_H,$$ cioè l'elemento del coset di peso di Hamming minimo. Se più elementi hanno peso minimo se ne sceglie uno con una regola qualsiasi. Evidentemente $\varepsilon(\mathbf0_{n-k})=\mathbf0_n$.

Teorema (decodifica a sindrome). Ricevuto $\tilde{\mathbf c}$ con sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$, la decodifica a distanza minima (MD) è $$\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)\ \ (=\tilde{\mathbf c}+\varepsilon(\boldsymbol\sigma)\text{ in }\mathbb Z_2).$$ Dimostrazione. Primo, $\hat{\mathbf c}$ è una parola di codice: $H\hat{\mathbf c}=H\tilde{\mathbf c}-H\varepsilon(\boldsymbol\sigma)=\boldsymbol\sigma-\boldsymbol\sigma=\mathbf0$. Poi, come funziona MD? Se $\mathcal C=\{\boldsymbol\gamma_1,\dots,\boldsymbol\gamma_{2^k}\}$ si fanno $2^k$ ipotesi: $\tilde{\mathbf c}=\boldsymbol\gamma_j+\tilde{\mathbf e}_j$, dove $\tilde{\mathbf e}_j$ è il possibile vettore d'errore (con un $1$ nei bit invertiti), e si sceglie quello con meno uni (distanza di Hamming minima). I vettori $\tilde{\mathbf e}_j$ (1) sono tutti diversi, (2) sono $2^k$, (3) hanno tutti sindrome $\boldsymbol\sigma$: infatti $\boldsymbol\sigma=H\tilde{\mathbf c}=H(\boldsymbol\gamma_j+\tilde{\mathbf e}_j)=H\tilde{\mathbf e}_j$. Sono quindi tutto il coset di $\boldsymbol\sigma$, e quello di peso minimo è per definizione $\varepsilon(\boldsymbol\sigma)$. La decodifica MD è $\tilde{\mathbf c}=\hat{\mathbf c}+\varepsilon(\boldsymbol\sigma)$, cioè quanto affermato. $\square$

Corollari. Se $\tilde{\mathbf c}\in\mathcal C$ la sindrome è nulla e il coset leader è $\mathbf0$: nessuna correzione, coerente con MD. Più in generale il coset leader coincide con la sindrome stessa solo in casi particolari.

Il vantaggio pratico: i coset leader si mettono in una tabella con $2^{n-k}$ righe (in genere poche). Ricevuta $\tilde{\mathbf c}$: si calcola $\boldsymbol\sigma=H\tilde{\mathbf c}$, si legge $\varepsilon(\boldsymbol\sigma)$ e si sottrae.

Esempio completo: il codice $(4,2)$ $\mu_2$

$G=\begin{pmatrix}1&0\\0&1\\1&1\\1&0\end{pmatrix}$, quindi $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ e $H=[A\mid I_2]=\begin{pmatrix}1&1&1&0\\1&0&0&1\end{pmatrix}$ (controllo: $HG=O$). Le $4$ sindromi dividono i $16$ vettori in $4$ coset da $4$ elementi:

Si riceve $\tilde{\mathbf c}=1110$: $\boldsymbol\sigma=H\tilde{\mathbf c}=(1+1+1+0,\ 1+0+0+0)=(1,1)$, coset leader $1000$, $\hat{\mathbf c}=1110+1000=0110$ (è una parola di codice). Nel coset $10$ i leader $0010$ e $0100$ hanno lo stesso peso: la decodifica sceglie uno dei due, ma l'errore è a distanza $1$ da due parole di codice diverse, quindi non è garantita la correzione (coerente con $d_{min}=2$, $t<1$: nessun errore correggibile). Qui il leader del coset $11$ è unico: la parola decodificata $0110$ è a distanza $1$ da $\tilde{\mathbf c}$, mentre le altre parole di codice ($0000$, $1011$, $1101$) sono a distanza $3$, $2$ e $2$.

Esempio con Hamming $(7,4)$

La tabella dei coset leader del $(7,4)$ ha $2^3=8$ righe: la sindrome nulla ($\mathbf0$) e le $7$ sindromi non nulle, ciascuna uguale a una colonna di $H$, hanno per leader il vettore con un solo $1$ nella posizione di quella colonna:

Esempio: $\mathbf b=1011$, $\mathbf c=G\mathbf b=1011010$ (parità: $b_1+b_2+b_4=1+0+1=0$, $b_1+b_3+b_4=1+1+1=1$, $b_2+b_3+b_4=0+1+1=0$). Se il canale sbaglia il bit $4$ si riceve $\tilde{\mathbf c}=1010010$ e $\boldsymbol\sigma=H\tilde{\mathbf c}=(1,1,1)$: è la colonna $4$ di $H$, quindi $\varepsilon=0001000$ e $\hat{\mathbf c}=1010010+0001000=1011010=\mathbf c$ ✓. Una sola sindrome per ognuno dei $7$ errori singoli: il codice li corregge tutti (112 casi = $16\cdot7$ verificati al calcolatore). Con $2$ errori invece la decodifica sbaglia sempre: la sindrome è la somma di due colonne, che è una terza colonna, e si "corregge" il bit sbagliato aggiungendo un terzo errore.

Il codice del compito 2013

$G=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&0&1\\0&1&1\\1&0&0\\0&1&0\end{pmatrix}$ (colonne $\boldsymbol\gamma_1=1001010$, $\boldsymbol\gamma_2=0100101$, $\boldsymbol\gamma_3=0011100$): è sistematico (le prime tre righe sono $I_3$), $(n,k)=(7,3)$, e $H=[A\mid I_4]$ con $A=\begin{pmatrix}1&0&1\\0&1&1\\1&0&0\\0&1&0\end{pmatrix}$. I pesi delle $8$ parole sono $0,3,3,4,3,4,6,5$: $d_{min}=3$, rivela fino a $2$ errori. Il calcolo completo è nell'Esercizio - Quattro domande brevi su capacità, TDMA e FDMA, entropia e codice lineare (simulazione d'esame 2013).

Errori comuni

• Verificare la linearità con una sola somma: serve la chiusura per tutte le coppie (o basta controllare che $\mathbf 0\in\mathcal C$ per scartare un codice).
• Calcolare $d_{min}$ su tutte le coppie in un codice lineare, o prenderlo dal peso di una colonna di $G$ qualsiasi (è solo un limite superiore).
• Scrivere $H=[I\mid A]$ con $G=\binom{I}{A}$: l'identità va dalla parte dei bit di parità, $H=[A\mid I_{n-k}]$ (verificare sempre $HG=O$).
• Confondere $G$ ($n\times k$ in questo corso) con quella dell'altra convenzione ($k\times n$): conta l'ordine del prodotto.
• Credere che una sindrome non nulla identifichi sempre l'errore: con colonne uguali o con due o più errori la correzione è ambigua o sbagliata.

Collegamenti

Il codice di Hamming e il CRC sono in Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →. Per le basi algebriche: Spazi vettorialiUno spazio vettoriale su un campo K è un insieme con una somma di vettori e un prodotto per scalari che rispettano 7 proprietà. Esempi fondamentali: K^n (somma componente per componente), le funzioni da R in R, i polinomi.Spazi vettoriali →, 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 →, DimensioneTutte le basi di uno spazio vettoriale hanno lo stesso numero di vettori, la dimensione (dim K^n = n). Da ogni sistema di generatori si estrae una base, ogni insieme di vettori indipendenti si completa a una base, e in dimensione n bastano n vettori indipendenti (o n generatori) per avere una base.Dimensione →. Esercizi: Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato, Esercizio - Test del DNA con 4, 5 e 7 provette.