Codici lineari

Definizione di codice lineare[modifica | modifica wikitesto]

Supponiamo che l'alfabeto sia un campo, con elementi. Nota che lo spazio di Hamming è uno spazio vettoriale di dimensione su .


Definizione (413 Codice lineare)

Un codice si dice lineare se è un sottospazio vettoriale di .

 


Osservazione (414)

Osservo che ha come cardinalità una potenza di , della forma . Sia una base di . Ora un elemento generico di si scrive come per una scelta univoca di nel campo . Per la scelta di ognuno dei coefficienti ho possibilità, quindi in totale ho elementi.

 

Peso di un codice[modifica | modifica wikitesto]

Definizione (415 Peso di una parola)

Il peso di una parola è per definizione , ossia il numero di coordinate diverse da 0 ( sta per "weight").

 


Definizione (416 Peso di un codice lineare)

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

 

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


Proposizione (417)

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

  1. Nel caso di un codice lineare e coincidono.
 
Dimostrazione
  1. Per il punto 1, basta osservare che è il numero di coordinate per cui differisce da , ma allora è uguale al numero di coordinate per cui differisce da 0, quindi è .
  2. Devo dimostrare le due disuguaglianze:


disuguaglianza 1: . Infatti, il minimo che compare nella definizione di viene fatto su tutte le coppie con , mentre il minimo di viene fatto solo sulle coppie con .


Disuguaglianza 2:

e per il punto 1:
ma è lineare, allora , e . Allora

 


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

Matrice generatrice[modifica | modifica wikitesto]

Definizione (418 Matrice generatrice)

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

 
Osservazione (419)

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

 


Definizione (420 Matrice di parità)

Dato un codice lineare , di dimensione , una base di ha elementi e una matrice generatrice è della forma . La matrice di parità per si denota con , è una matrice per cui

 


Esempio (421)

Se , e ha dimensione , servono cinque equazioni lineari per descrivere .

 


Esempio (422)

Sull'alfabeto , considero la matrice , data da un'unica riga con entrate uguali a 1. Allora

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

 


Proposizione (423)

Siano matrici con righe linearmente indipendenti, tali che è una matrice e è una matrice , allora sono rispettivamente la matrice generatrice e la matrice di parità di un codice se e solo se .

 
Dimostrazione

Questo è vero perché implica che le righe di stanno in , e quindi siccome e sono entrambi sottospazi vettoriali di dimensione , allora essi coincidono.

 

Costruzione di H a partire da G e viceversa[modifica | modifica wikitesto]

Sia una matrice , e sia ( ha la matrice identica nel blocco a sinistra e la matrice nel blocco accanto). Allora la matrice di parità è data da:

Infatti in particolare osservo che

questo significa che le righe di sono linearmente indipendenti. Vale il viceversa: se ha matrice di parità , allora .


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[modifica | modifica wikitesto]

Proposizione (424)

Un codice lineare ha distanza minima se e solo se comunque prese colonne di , esse sono linearmente indipendenti.

 
Dimostrazione

Supponiamo che ha distanza minima , e sia il numero minimo di colonne di linearmente dipendenti. Dobbiamo dimostrare che . Supponiamo che le colonne linearmente dipendenti di siano le prime . Allora, se chiamo queste colonne , si ha che

dove sono coefficienti scalari non nulli.


Prendo il vettore di lunghezza . Allora

e quindi è una parola del codice , perché risolve l'equazione , e ha peso (infatti coordinate sono non nulle). Allora
Ho quindi dimostrato che . Se prendo colonne di queste sono linearmente indipendenti.

 
Esempio (425)

Sull'alfabeto , se consideriamo un codice con dimensione e parole di lettere, si ha che il codice ha elementi. Calcolare il peso minimo richiederebbe molte operazioni, e quindi si può usare la proposizione sulla distanza minima appena dimostrata, e verificare se colonne della matrice generatrice sono indipendenti.

 

Codifica di un messaggio per codici lineari[modifica | modifica wikitesto]

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


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


Riassumendo, la k-upla viene codificata in . (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 ).

Decodifica e correzione degli errori[modifica | modifica wikitesto]

Per la decodifica serve la matrice di parità . Per fissare le idee, supponiamo che ha distanza minima e che sia correttore di errori, con .


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

infatti e quindi . Allora

Definizione (426 Sindrome)

è detta sindrome.

 

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

Proposizione (427)

Siano errori distinti, allora (anche le sindromi sono distinte)

 
Dimostrazione

Siano errori distinti ma con la stessa sindrome, cioè tali che , allora . Questo implica che è una parola del codice, non nulla perché per ipotesi . Quindi perché è il peso minimo. Per la disuguaglianza triangolare

hanno peso minore di perché nel nostro canale avvengono al massimo errori, e si ottiene e questo è assurdo.

 


Esempio (428)

Riprendendo l'esempio del giochino, sia , , .

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 vettori della base canonica.


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


Supponiamo che

allora
La sindrome è alla quarta colonna di , quindi l'errore associato è , e devo correggere la quarta coordinata di , quindi la parola trasmessa è .


Matrice generatrice: per calcolarla voglio portare nella forma , e per farlo scambio la prima e la settima riga, la seconda e la sesta riga, la quarta e la quinta riga

Allora ottengo:
e rifacendo gli scambi appena effettuati:

 

Codici di Hamming[modifica | modifica wikitesto]

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

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

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

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

ha righe perché le colonne sono vettori di lunghezza . Le colonne sono tante quante le classi di equivalenza. Il numero totale di vettori non nulli è , allora il numero di classi di equivalenza è

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

  • Il codice di Hamming con parametri è un codice lineare con matrice di parità .

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


Nota che ha distanza minima per costruzione, perché le colonne non sono l'una multiplo dell'altra.


Esempio (429)

Sia , e . Allora ha tre righe e colonne. Le colonne sono vettori di lunghezza 3 non nulli, e colonne diverse devono essere una multiplo dell'altra, ad esempio, se è una colonna, non lo sarà.


Le colonne di sono:

 
 Precedente