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
.
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.
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:

- Nel caso di un codice lineare
e
coincidono.
Dimostrazione
- 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 è
.
- 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.
Definizione (418 Matrice generatrice)
Una matrice generatrice
di un codice lineare
è una matrice che ha per righe una base di
.
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.
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.
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
).
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:

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:
