Codici lineari

Definizione di codice lineare

Supponiamo che l'alfabeto $Q$$Q$ sia un campo, con $q$$q$ elementi. Nota che lo spazio di Hamming $H(n,Q)$$H(n,Q)$ è uno spazio vettoriale di dimensione $n$$n$ su $Q$$Q$.

Definizione (413 Codice lineare)

Un codice $C$$C$ si dice lineare se $C$$C$ è un sottospazio vettoriale di $H(n,Q)$$H(n,Q)$.

 

Osservazione (414)

Osservo che $C$$C$ ha come cardinalità una potenza di $q$$q$, della forma $q^{k}$$q^{k}$. Sia $\{c_{1},c_{2},\dots ,c_{k}\}$$\{c_{1},c_{2},\dots ,c_{k}\}$ una base di $C$$C$. Ora un elemento generico di $C$$C$ si scrive come $\alpha _{1}c_{1}+\dots +\alpha _{k}c_{k}$$\alpha _{1}c_{1}+\dots +\alpha _{k}c_{k}$ per una scelta univoca di $\alpha _{1},\dots ,\alpha _{k}$$\alpha _{1},\dots ,\alpha _{k}$ nel campo $Q$$Q$. Per la scelta di ognuno dei coefficienti $\alpha _{k}$$\alpha _{k}$ ho $q$$q$ possibilità, quindi in totale ho $q^{k}$$q^{k}$ elementi.

 

Peso di un codice

Definizione (415 Peso di una parola)

Il peso di una parola $w$$w$ è per definizione ${\rm {{wt}(w)=d(w,0)}}$${\rm {{wt}(w)=d(w,0)}}$, ossia il numero di coordinate diverse da 0 (${\rm {wt}}$${\rm {wt}}$ sta per "weight").

 

Definizione (416 Peso di un codice lineare)

Il peso di un codice lineare$C$$C$ è il minimo dei pesi delle parole non nulle del codice $C$$C$, cioè

$${\rm {{wt}(C)=\min _{c\in C,c\neq 0}\{{\rm {{wt}(c)\}.}}}}$$

$${\rm {{wt}(C)=\min _{c\in C,c\neq 0}\{{\rm {{wt}(c)\}.}}}}$$

 

Da un punto di vista computazionale per calcolare il peso di un codice bisogna fare $|C|-1$$|C|-1$ controlli (uno per ogni parola del codice, escluso lo zero). Calcolare la distanza minima tra due elementi invece costa $|C|^{2}$$|C|^{2}$ operazioni, ma con la proposizione seguente si ha che nel caso di codici lineari anche per calcolare la distanza minima bastano $|C|-1$$|C|-1$ operazioni, perché, in base alla proposizione che segue, il peso minimo coincide con la distanza minima.

Proposizione (417)

Detta $d$$d$ la distanza minima di uno spazio di Hamming, si ha:

1. $$d(v,w)={\rm {{wt}(v-w),\,\forall v,w\in H(n,q)}}$$

   $$d(v,w)={\rm {{wt}(v-w),\,\forall v,w\in H(n,q)}}$$
2. Nel caso di un codice lineare $d$$d$ e ${\rm {{wt}(C)}}$${\rm {{wt}(C)}}$ coincidono.

 

Dimostrazione

1. Per il punto 1, basta osservare che $d(v,w)$$d(v,w)$ è il numero di coordinate per cui $v$$v$ differisce da $w$$w$, ma allora è uguale al numero di coordinate per cui $v-w$$v-w$ differisce da 0, quindi è ${\rm {{wt}(v-w)}}$${\rm {{wt}(v-w)}}$.
2. Devo dimostrare le due disuguaglianze:

disuguaglianza 1: $d(C)\leq {\rm {{wt}(C)}}$$d(C)\leq {\rm {{wt}(C)}}$. Infatti, il minimo che compare nella definizione di $d(C)$$d(C)$ viene fatto su tutte le coppie $(c_{1},c_{2})$$(c_{1},c_{2})$ con $c_{1}\neq c_{2}$$c_{1}\neq c_{2}$, mentre il minimo di ${\rm {{wt}(C)}}$${\rm {{wt}(C)}}$ viene fatto solo sulle coppie $(0,c)$$(0,c)$ con $c\neq 0$$c\neq 0$.

Disuguaglianza 2: $d(C)\geq {\rm {{wt}(C)}}$$d(C)\geq {\rm {{wt}(C)}}$

$$d(C)=\min _{(c_{1},c_{2})\in C,\,c_{1}\neq c_{2}}d(c_{1},c_{2})$$

$$d(C)=\min _{(c_{1},c_{2})\in C,\,c_{1}\neq c_{2}}d(c_{1},c_{2})$$

e per il punto 1:

$$=\min _{c_{1},c_{2}\in C,\,c_{1}\neq c_{2}}{\rm {{wt}(c_{1}-c_{2})}}$$

$$=\min _{c_{1},c_{2}\in C,\,c_{1}\neq c_{2}}{\rm {{wt}(c_{1}-c_{2})}}$$

ma $C$$C$ è lineare, allora $c_{1},c_{2}\in C\longrightarrow c_{1}-c_{2}\in C$$c_{1},c_{2}\in C\longrightarrow c_{1}-c_{2}\in C$, e $c_{1}-c_{2}\neq 0$$c_{1}-c_{2}\neq 0$. Allora

$$=\min _{c\neq 0,c\in C}{\rm {{wt}(c)={\rm {{wt}(C).}}}}$$

$$=\min _{c\neq 0,c\in C}{\rm {{wt}(c)={\rm {{wt}(C).}}}}$$

 

Quindi i codici lineari si usano perché con questi è più comodo calcolare la minima distanza.

Matrice generatrice

Definizione (418 Matrice generatrice)

Una matrice generatrice$G$$G$ di un codice lineare $C$$C$ è una matrice che ha per righe una base di $C$$C$.

 

Osservazione (419)

Nota che data una matrice $G$$G$, il codice lineare $C$$C$ è univocamente dato, perché i suoi elementi sono combinazioni lineari di elementi di $G$$G$ (e questo è il secondo vantaggio, oltre alla riduzione dei costi computazionali, di usare codici lineari).

 

Definizione (420 Matrice di parità)

Dato un codice lineare $C$$C$, di dimensione $k$$k$, una base di $C$$C$ ha $k$$k$ elementi e una matrice generatrice è della forma $k\times n$$k\times n$. La matrice di parità per $C$$C$ si denota con $H$$H$, è una matrice $n-k\times n$$n-k\times n$ per cui

$$C:=\{v\in H(n,Q)\,t.c.\,v\times H^{t}=0\}=\ker H.$$

$$C:=\{v\in H(n,Q)\,t.c.\,v\times H^{t}=0\}=\ker H.$$

 

Esempio (421)

Se $n=15$$n=15$, e $C$$C$ ha dimensione $k=10$$k=10$, servono cinque equazioni lineari per descrivere $C$$C$.

 

Esempio (422)

Sull'alfabeto $\mathbb {Z} _{2}$$\mathbb {Z} _{2}$, considero la matrice $H$$H$, data da un'unica riga con entrate uguali a 1. Allora

$$C=\{v\,t.c.\,vH^{t}=0\}$$

$$C=\{v\,t.c.\,vH^{t}=0\}$$

$$=\{v\,t.c.\,\sum _{i=1}^{n}v_{i}=0\}$$

$$=\{v\,t.c.\,\sum _{i=1}^{n}v_{i}=0\}$$

$$=\{v\,t.c.\,{\hbox{v ha un numero pari di coordinate uguali a 1}}\}$$

$$=\{v\,t.c.\,{\hbox{v ha un numero pari di coordinate uguali a 1}}\}$$

(da qui viene il nome "matrice di parità")

 

Proposizione (423)

Siano $G,H$$G,H$ matrici con righe linearmente indipendenti, tali che $G$$G$ è una matrice $k\times n$$k\times n$ e $H$$H$ è una matrice $n-k\times n$$n-k\times n$, allora $G,H$$G,H$ sono rispettivamente la matrice generatrice e la matrice di parità di un codice $C$$C$ se e solo se $GH^{t}=0$$GH^{t}=0$.

 

Dimostrazione

Questo è vero perché $GH^{t}=0$$GH^{t}=0$ implica che le righe $g_{1},\dots ,g_{k}$$g_{1},\dots ,g_{k}$ di $G$$G$ stanno in $\ker H$$\ker H$, e quindi siccome $\ker H$$\ker H$ e ${\rm {{span}(g_{1},\dots ,g_{k})}}$${\rm {{span}(g_{1},\dots ,g_{k})}}$ sono entrambi sottospazi vettoriali di dimensione $k$$k$, allora essi coincidono.

 

Costruzione di H a partire da G e viceversa

Sia $A$$A$ una matrice $k\times n-k$$k\times n-k$, e sia $G=(I_{k}\,A)$$G=(I_{k}\,A)$ ($G$$G$ ha la matrice identica $k\times k$$k\times k$ nel blocco a sinistra e la matrice $A$$A$ nel blocco accanto). Allora la matrice di parità $H$$H$ è data da:

$$H=(-A^{t}\,I_{n-k})$$

$$H=(-A^{t}\,I_{n-k})$$

Infatti in particolare osservo che

$$GH^{t}=-A+A=0$$

$$GH^{t}=-A+A=0$$

questo significa che le righe di $H$$H$ sono linearmente indipendenti. Vale il viceversa: se $C$$C$ ha matrice di parità $H=(-A^{t}\,I_{n-k})$$H=(-A^{t}\,I_{n-k})$, allora $G=(I_{k}\,A)$$G=(I_{k}\,A)$.

Data una matrice che non è della forma descritta sopra, la si può portare in tale forma con l'eliminazione di Gauss.

Determinazione della distanza minima di un codice

Proposizione (424)

Un codice lineare $C$$C$ ha distanza minima $\geq d$$\geq d$ se e solo se comunque prese $d-1$$d-1$ colonne di $H$$H$, esse sono linearmente indipendenti.

 

Dimostrazione

Supponiamo che $C$$C$ ha distanza minima $\geq d$$\geq d$, e sia $l$$l$ il numero minimo di colonne di $H$$H$ linearmente dipendenti. Dobbiamo dimostrare che $l\geq d$$l\geq d$. Supponiamo che le colonne linearmente dipendenti di $H$$H$ siano le prime $l$$l$. Allora, se chiamo queste colonne $v_{1},\dots ,v_{l}$$v_{1},\dots ,v_{l}$, si ha che

$$\alpha _{1}v_{1}+\alpha _{2}v_{2}+\dots +\alpha _{l}v_{l}=0$$

$$\alpha _{1}v_{1}+\alpha _{2}v_{2}+\dots +\alpha _{l}v_{l}=0$$

dove $\alpha _{1},\dots ,\alpha _{l}$$\alpha _{1},\dots ,\alpha _{l}$ sono coefficienti scalari non nulli.

Prendo il vettore $c=(\alpha _{1},\alpha _{2},\dots ,\alpha _{l},0,0,\dots )$$c=(\alpha _{1},\alpha _{2},\dots ,\alpha _{l},0,0,\dots )$ di lunghezza $n$$n$. Allora

$$cH^{t}=\alpha _{1}v_{1}+\dots +\alpha _{l}v_{l}+0=0.$$

$$cH^{t}=\alpha _{1}v_{1}+\dots +\alpha _{l}v_{l}+0=0.$$

e quindi $c$$c$ è una parola del codice $C$$C$, perché risolve l'equazione $vH^{t}=0$$vH^{t}=0$, e ha peso $l$$l$ (infatti $l$$l$ coordinate sono non nulle). Allora

$$l={\rm {{wt}(c)\geq {\rm {{wt}(C)=d(C).}}}}$$

$$l={\rm {{wt}(c)\geq {\rm {{wt}(C)=d(C).}}}}$$

Ho quindi dimostrato che $l\geq {\rm {{wt}(C)}}$$l\geq {\rm {{wt}(C)}}$. Se prendo $d-1$$d-1$ colonne di $H$$H$ queste sono linearmente indipendenti.

 

Esempio (425)

Sull'alfabeto $Q=\{0,1\}$$Q=\{0,1\}$, se consideriamo un codice con dimensione $k=4$$k=4$ e parole di $n=7$$n=7$ lettere, si ha che il codice ha $2^{4}$$2^{4}$ elementi. Calcolare il peso minimo richiederebbe molte operazioni, e quindi si può usare la proposizione sulla distanza minima appena dimostrata, e verificare se $d-1$$d-1$ colonne della matrice generatrice sono indipendenti.

 

Codifica di un messaggio per codici lineari

Per la codifica serve la matrice generatrice. L'insieme dei messaggi sono k-uple di vettori a coefficienti nell'alfabeto $Q$$Q$. Data una tale k-upla $v$$v$, associamo ad essa l'elemento $v*G$$v*G$, che è una parola del codice perché è combinazione lineare delle righe di $G$$G$.

La funzione che manda $v$$v$ in $vG$$vG$ è una funzione da $C$$C$ in sé ed è iniettiva perché le righe di $G$$G$ sono linearmente indipendenti, e quindi è anche suriettiva perché sto lavorando su insiemi finiti.

Riassumendo, la k-upla $v$$v$ viene codificata in $v*G$$v*G$. (come nel giochino, in cui i messaggi, cioè i numeri da 0 a 15 in rappresentazione binaria, venivano codificati nel vettore di 7 elementi corrispondente alle risposte alle 7 domande, attraverso il prodotto $vG$$vG$).

Decodifica e correzione degli errori

Per la decodifica serve la matrice di parità $H$$H$. Per fissare le idee, supponiamo che $C$$C$ ha distanza minima $d$$d$ e che sia correttore di $e$$e$ errori, con $d\geq 2e+1$$d\geq 2e+1$.

Diciamo che sia stata spedita $c$$c$ e che sia stata ricevuta $w$$w$, e che siano stati commessi al massimo $e$$e$ errori. Allora da $w$$w$ vogliamo ricostruire $c$$c$. Si ha $w=c+u$$w=c+u$, con $u$$u$ errore. Quindi

$$wH^{t}=(c+u)H^{t}=cH^{t}+uH^{t}=uH^{t}$$

$$wH^{t}=(c+u)H^{t}=cH^{t}+uH^{t}=uH^{t}$$

infatti $c\in C$$c\in C$ e quindi $cH^{t}=0$$cH^{t}=0$. Allora $wH^{t}=uH^{t}$$wH^{t}=uH^{t}$

Definizione (426 Sindrome)

$wH^{t}$$wH^{t}$ è detta sindrome.

 

Mostriamo ora che errori diversi hanno sindromi diverse. Questo permetterà di correggere l'errore $u$$u$ utilizzando una tavola precompilata con due colonne: la prima costituita da tutte le sindromi, e la seconda costituita dagli errori.

Proposizione (427)

Siano $u_{1},u_{2}$$u_1,u_2$ errori distinti, allora $u_{1}H^{t}\neq u_{2}H^{t}$$u_{1}H^{t}\neq u_{2}H^{t}$ (anche le sindromi sono distinte)

 

Dimostrazione

Siano $u_{1},u_{2}$$u_1,u_2$ errori distinti ma con la stessa sindrome, cioè tali che $u_{1}H^{t}=u_{2}H^{t}$$u_{1}H^{t}=u_{2}H^{t}$, allora $(u_{1}-u_{2})H^{t}=0$$(u_{1}-u_{2})H^{t}=0$. Questo implica che $u_{1}-u_{2}$$u_{1}-u_{2}$ è una parola del codice, non nulla perché per ipotesi $u_{1}\neq u_{2}$$u_{1}\neq u_{2}$. Quindi ${\rm {{wt}(u_{1}-u_{2})\geq d}}$${\rm {{wt}(u_{1}-u_{2})\geq d}}$ perché $d$$d$ è il peso minimo. Per la disuguaglianza triangolare

$$2e+1\leq {\rm {{wt}(u_{1}-u_{2})\leq {\rm {{wt}(u_{1})+{\rm {{wt}(u_{2}).}}}}}}$$

$$2e+1\leq {\rm {{wt}(u_{1}-u_{2})\leq {\rm {{wt}(u_{1})+{\rm {{wt}(u_{2}).}}}}}}$$

$u_{1},u_{2}$$u_1,u_2$ hanno peso minore di $e$$e$ perché nel nostro canale avvengono al massimo $e$$e$ errori, e si ottiene $2e\geq 2e+1$$2e\geq 2e+1$ e questo è assurdo.

 

Esempio (428)

Riprendendo l'esempio del giochino, sia $n=7$$n=7$, $k=4$$k=4$, $Q=\{0,1\}$$Q=\{0,1\}$.

$$H={\begin{array}{ccccccc}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{array}}$$

$$H={\begin{array}{ccccccc}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{array}}$$

$d=3$$d=3$ perché prese due colonne, una non può essere multiplo dell'altra però le prime tre colonne sono linearmente dipendenti e quindi la distanza minima non può essere 4. Il codice è correttore di 1 errore. Gli errori sono tutti i vettori con peso 1, e quindi sono $e_{1},e_{2},\dots ,e_{7}$$e_{1},e_{2},\dots ,e_{7}$ vettori della base canonica.

In questo caso la tavola delle sindromi è semplice, perché all'errore $e_{i}$$e_{i}$ basta associare l'i-esima colonna di $H$$H$.

Supponiamo che

$$w=(1,1,1,1,0,0,0)$$

$$w=(1,1,1,1,0,0,0)$$

allora

$$w*H^{t}=(1,0,0)$$

$$w*H^{t}=(1,0,0)$$

La sindrome $(1,0,0)$$(1,0,0)$ è alla quarta colonna di $H$$H$, quindi l'errore associato è $e_{4}$$e_{4}$, e devo correggere la quarta coordinata di $w$$w$, quindi la parola trasmessa è $C=(1,1,1,0,0,0,0)$$C=(1,1,1,0,0,0,0)$.

Matrice generatrice: per calcolarla voglio portare $H$$H$ nella forma $(-A^{t},I_{3})$$(-A^{t},I_{3})$, e per farlo scambio la prima e la settima riga, la seconda e la sesta riga, la quarta e la quinta riga

$$H'={\begin{array}{ccccccc}1&1&0&1&1&0&0\\1&1&1&0&0&1&0\\1&0&1&1&0&0&1\end{array}}$$

$$H'={\begin{array}{ccccccc}1&1&0&1&1&0&0\\1&1&1&0&0&1&0\\1&0&1&1&0&0&1\end{array}}$$

Allora ottengo:

$$G'=(I_{4},A)$$

$$G'=(I_{4},A)$$

$$={\begin{array}{ccccccc}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&0&1&1\\0&0&0&1&1&0&1\end{array}}$$

$$={\begin{array}{ccccccc}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&0&1&1\\0&0&0&1&1&0&1\end{array}}$$

e rifacendo gli scambi appena effettuati:

$$={\begin{array}{ccccccc}1&1&0&1&0&0&1\\0&1&0&1&0&1&0\\1&1&1&0&0&0&0\\1&0&0&1&1&0&0\end{array}}$$

$$={\begin{array}{ccccccc}1&1&0&1&0&0&1\\0&1&0&1&0&1&0\\1&1&1&0&0&0&0\\1&0&0&1&1&0&0\end{array}}$$

 

Codici di Hamming

I codici di Hamming sono i codici correttori di un errore più utilizzati.

• Fisso $q$$q$, numero di elementi dell'alfabeto, e $l$$l$, intero positivo.

Sull'insieme di tutti i vettori non nulli di lunghezza $l$$l$, definisco una relazione di equivalenza: $v\sim w$$v\sim w$ se $v$$v$ e $w$$w$ sono multipli l'uno dell'altro.

• Sia $H$$H$ una matrice che ha per colonne rappresentanti di ciascuna classe di equivalenza.

$H$$H$ ha $l$$l$ righe perché le colonne sono vettori di lunghezza $l$$l$. Le colonne sono tante quante le classi di equivalenza. Il numero totale di vettori non nulli è $q^{l}-1$$q^{l}-1$, allora il numero di classi di equivalenza è

$${\frac {q^{l}-1}{q-1}}$$

$${\frac {q^{l}-1}{q-1}}$$

($q-1$$q-1$ è il numero di elementi in una classe di equivalenza, perché gli scalari per cui posso moltiplicare un vettore per ottenere i suoi multipli è proprio $q-1$$q-1$).

• Il codice di Hamming con parametri $q,l$$q,l$ è un codice lineare con matrice di parità $H$$H$.

Per essere correttore di 1 errore, la distanza minima dev'essere 3, quindi due colonne di $H$$H$ non nulle non devono essere l'una multiplo dell'altra.

Nota che $C$$C$ ha distanza minima $d\geq 3$$d\geq 3$ per costruzione, perché le colonne non sono l'una multiplo dell'altra.

Esempio (429)

Sia $q=3$$q=3$, $Q=\{0,1,2\}$$Q=\{0,1,2\}$ e $l=3$$l=3$. Allora $H$$H$ ha tre righe e ${\frac {3^{3}-1}{3-1}}=13$${\frac {3^{3}-1}{3-1}}=13$ colonne. Le colonne sono vettori di lunghezza 3 non nulli, e colonne diverse devono essere una multiplo dell'altra, ad esempio, se $(0,0,1)$$(0,0,1)$ è una colonna, $(0,0,2)$$(0,0,2)$ non lo sarà.

Le colonne di $H$$H$ sono:

$$(0,0,1),\,(0,1,0),\,(0,1,1),\,(0,1,2),\,(1,0,0),\,(1,0,1),\,(1,0,2),\,(1,1,0),\,(1,1,1),\,(1,1,2),\,(1,2,0),\,(1,2,1),\,(1,2,2)$$

$$(0,0,1),\,(0,1,0),\,(0,1,1),\,(0,1,2),\,(1,0,0),\,(1,0,1),\,(1,0,2),\,(1,1,0),\,(1,1,1),\,(1,1,2),\,(1,2,0),\,(1,2,1),\,(1,2,2)$$