Matematica Discreta III
Lezione del giorno 7 aprile 2008
Sia data M matrice generatrice di un codice lineare C di lunghezza n e dimensione k (quindi matrice nxk): le sue righe R1, R2,……, Rk sono vettori di Z2k che formano una base del sottospazio C.
Supponiamo di modificare M con una delle seguenti operazioni:
1) Scambio di 2 colonne s,t fra loro
2) Sostituzione di una riga Rs con la somma Rs+Rt della stessa riga s e di un’altra riga t
Dimostriamo che in ambedue i casi i vettori riga R1’, R2’,……, Rk’ della nuova matrice M’ restano linearmente indipendenti.
Nel caso 1), in ogni vettore riga i bits di posto s e posto t sono scambiati fra loro, e si verifica facilmente che se gli scalari α1,….,αk sono tali che:
α1R1’+…..+αkRk’=0 allora anche:
α1R1+…..+αkRk=0
da cui α1=….=αk=0 per l’ipotesi che R1, R2,……, Rk sono linearmente indipendenti.
Nel caso 2), R1’=R1,…,Rs’=Rs+Rt,…., Rt’=Rt,….,Rk’=Rk e se gli scalari α1,….,αk sono tali che:
α1R1’+…. +αsRs’….+αtRt’+….+αkRk’=0=α1R1+…. +αsRs….+(αs+αt)Rt+….+αkRk
si ottiene α1=….=αs+αt=…. =αt=…=αk=0 per l’ipotesi che R1, R2,……, Rk sono linearmente indipendenti, e dunque α1=….=αs=…. =αt=…=αk=0.
Se consideriamo la nuova matrice M’ come matrice generatrice di un nuovo codice lineare C’ di lunghezza n e dimensione k, possiamo affermare che:
nel caso 1) i codici C e C’ sono equivalenti, perché è facile verificare che lo scambio delle colonne s,t produce nelle parole del codice uno scambio dei bits di posto s,t;
nel caso 2) i codici C e C’ coincidono perché i vettori riga di M’ continuano ad appartenere a C (essendo C chiuso rispetto alla somma) ed essendo linearmente indipendenti e in numero di k (dimensione di C) sono una base di C.
Teorema. Sia data M matrice generatrice di un codice lineare C di lunghezza n e dimensione k (quindi matrice nxk). Allora con una successione finita di modifiche del tipo 1) o 2), si può trasformare M in una matrice di forma standard M’, generatrice di un codice lineare sistematico C’
di lunghezza n e dimensione k, che (per quanto osservato sopra) è equivalente a C.
Dimostrazione:
L’obiettivo è quello di trasformare alla fine M in una matrice di forma standard, ossia una matrice in cui le prime k colonne formano la matrice identica Ik (ogni colonna s con s=1,…,k ha tutti valori 0 tranne il valore di posto s che è 1).
Supponiamo di avere già trasformato in maniera opportuna le prime s-1 colonne (con s≤k) e illustriamo un algoritmo che trasforma la colonna s. Siamo dunque per ipotesi già pervenuti ad una matrice della forma:
M* =
. . . α . . 0 0 0
. . . . . . . . .
. . . α . . . . .
. . . . . . . . .
. . . α . . 1 0 0
. . . α . . 0 1 0
. . . α . . 0 0 1
ks ss 3s 2s 1s
in cui le colonne 1,….,s-1 sono già “corrette” e dobbiamo trasformare opportunamente la colonna s.
La prima trasformazione consiste nel rendere αss=1: se αss=0, poiché i valori che precedono αss nella riga sono per costruzione tutti =0, vi sarà almeno un valore αrs=1 con r>s (se così non fosse, la riga s sarebbe tutta con elementi 0, e i vettori riga non potrebbero essere linearmente indipendenti, essendo uno di essi il vettore nullo); scambiamo allora la colonna r e la colonna s fra loro (trasformazione di tipo 1)). Possiamo notare che non abbiamo modificato le righe 1,…,s-1 già
“corrette”. Dopo avere fatto in modo che αss=1, dobbiamo rendere =0 tutti gli altri elementi della colonna s (tranne αss): a tale scopo, per ogni riga r=1,….,k con r≠s, se l’elemento αrs è =1, sostituiamo tale riga r con la somma della stessa riga r e della riga s, ricordando che 1+1=0 (trasformazione di tipo 2)). Di nuovo notiamo che, essendo nulli gli elementi della riga s in colonne che precedono la colonna s, non abbiamo modificato le righe 1,…,s-1 già “corrette”.
Esempio: la matrice dell’esempio precedente
M =
1 1 0 1
0 1 0 1
1 0 1 1
é matrice generatrice del codice di lunghezza 4 e dimensione 3 C = { 0000, 1101, 1010, 1011, 0111, 0110, 0001, 1100 }.
Trasformiamo M in una matrice di forma standard con successive modifiche del tipo 1) e 2), secondo l’algoritmo descritto nella dimostrazione del Teorema.
Trasformazione colonna 1: già l’elemento α11 è =1, dunque basta sostituire la riga 2 e 3 (che hanno il termine in colonna 1 diverso da 0) con la loro somma con la riga 1:
M1 =
0 1 1 0
1 1 1 0
1 0 1 1
In questa trasformazione (tipo 2) il codice generato rimane invariato.
Trasformazione colonna 2: già l’elemento α22 è =1, dunque basta sostituire la riga 1 e 3 (che hanno il termine in colonna 2 diverso da 0) con la loro somma con la riga 2:
M2 =
1 0 0 0
1 1 1 0
0 1 0 1
Di nuovo in questa trasformazione (tipo 2) il codice generato rimane invariato.
Trasformazione colonna 3: l’elemento α33 è =0, dunque, poiché nella colonna 4 l’elemento in riga 3 è =1, scambiamo fra loro le colonne 3 e 4:
M3 =
0 1 0 0
1 1 1 0
1 0 0 1
Basta ora sostituire la riga 2 (che ha il termine in colonna 3 diverso da 0) con la sua somma con la riga 3:
M’ =
0 1 0 0
1 0 1 0
1 0 0 1
In quest’ultima trasformazione (avendo anche usato il tipo 1) si è ottenuto un codice lineare sistematico C’ equivalente a C (precisamente le parole di C’ si ottengono scambiando fra loro 3° e 4° bit, perché nella trasformazione della matrice M si sono scambiate le colonne 3 e 4).
Alla fine si è ottenuta una matrice M’ in forma standard (le prime 3 colonne formano la matrice identica I3), matrice generatrice del seguente codice lineare sistematico equivalente a C:
C’= { 0000, 1001, 0101, 0010, 1100, 1011, 0111, 1110 }
Più precisamente le parole di C’ si ottengono scambiando fra loro 3° e 4° bit, perché in uno dei passaggi di trasformazione della matrice M si sono scambiate fra loro le colonne 3 e 4.
I ragionamenti precedenti permettono, dal punto di vista operativo, di limitarsi (per generare codici di lunghezza n e dimensione k fissate) alla generazione di codici lineari sistematici mediante matrici generatrici in forma standard:
M = [ IkM’] (dove M’ è una matrice binaria kx(n-k))
Da notare che la scelta di M’ può essere arbitraria, perché in ogni caso la matrice M ha i vettori riga linearmente indipendenti (quindi essi formano una base del codice generato) essendo la matrice M di rango k (perché la sottomatrice formata dalle prime k colonne è Ik che ha determinante 10).
Resta naturalmente da dimostrare quali proprietà di M garantiscano che il codice generato abbia una distanza prefissata.
Notiamo anche che la matrice in forma standard di un codice lineare sistematico è univocamente determinata.
Infatti supponiamo M = [ IkM’] , M0 = [ IkM0’] matrici generatrici dello stesso codice C, dove M’ = (βij) , M’ = (ij) con i=1,….,k; j=1,…..,n-k .
Considerato il vettore w=(1,0,0,….,0)Z2k, si ha v=(x1,…..,xn)=wMC, ed esplicitando i calcoli:
(x1,…..,xn)=(1,0,0,….,0, β11, β12, …., β1(n-k)), ossia x1=1, x2=x3=…=xk=0. Essendo anche M0 matrice generatrice di C, esiste una parola z=(y1,y2,….,yk)Z2k tale che v=(x1,…..,xn)=zM=(y1,y2,….,yk,
……), da cui y1=1, y2=y3=…=yk=0, dunque si ottiene zM=(1,0,0,….,0, 11, 12, …., 1(n-k)), 1j=β1j
per ogni j=1,2,…,n-k, e le matrici M’,M0’ hanno la prima colonna uguale. In modo analogo si dimostra che le matrici M’,M0’ hanno tutte le colonne uguali, da cui M’=M0’, M=M’.
Matrice di controllo
Fissata la matrice kx(n-k) in forma standard:
M = [ IkM’] M’ = (βij) i=1,….,k; j=1,…..,n-k
il codice lineare sistematico C generato da M contiene tutte le parole vZ2n per le quali esiste una parola w=(α1,…., αk)Z2k tale che si abbia v = wM. Da ciò segue che, se v=(x1,…..,xn)C, i bits x1,…..,xn soddisfano le seguenti equazioni:
x1=α1, x2=α2,……, xk=αk ; xk+1=α1β11+α2β21+…+αkβk1 ;
……..
xk+(n-k)=xn=α1β1(n-k)+α2β2(n-k)+…+αkβk(n-k)
dunque le seguenti equazioni:
xk+1=x1β11+x2β21+…+xkβk1 ; xk+2=x1β12+x2β22+…+xkβk2 ;
……..
xk+(n-k)=xn=x1β1(n-k)+x2β2(n-k)+…+xkβk(n-k)
e ancora (ricordando che x= -x):
x1β11+x2β21+…+xkβk1+xk+1=0;
x1β12+x2β22+…+xkβk2+xk+2=0; (*)
……..
x1β1(n-k)+x2β2(n-k)+…+xkβk(n-k)+xn=0
Da ciò, segue l’identità matriciale vH=0 (vettore nullo in Z2n-k) dove H è la matrice nx(n-k) con un blocco superiore kx(n-k) coincidente con M’ ed un blocco inferiore (n-k)x(n-k) coincidente con la matrice identica In-k .
E’ facile invertire i passaggi e dimostrare che da vH=0 segue vC.
Dunque si ottiene un criterio necessario e sufficiente per l’appartenenza di una parola di lunghezza n al codice C:
vC vH=0 (dove H è la matrice suddetta, ricavata dalla matrice generatrice M = [ IkM’]) La matrice H è detta matrice di controllo del codice lineare sistematico C.
Nel caso C venga usato per codificare informazioni da spedire lungo un canale di trasmissione, la rilevazione di un errore (che si effettua verificando se la parola ricevuta v appartiene o no al codice C) può essere fatta in un modo algoritmicamente semplice, controllando se vH=0 o vH≠0 (sarebbe molto più complesso confrontare v con le 2k parole di C per verificare se coincide con una di esse).
Se un codice lineare sistematico CZ2n di lunghezza n e dimensione k ha matrice generatrice in forma standard M = [ IkM’] e corrispondente matrice di controllo H, come calcolare a priori la distanza di C, senza generare tutte le parole del codice e calcolare le loro distanze ?
Teorema. Sia H la matrice di controllo di un codice CZ2n di lunghezza n e dimensione k e sia la distanza di C. Fissato un naturale s>1 si ha:
s per ogni numero naturale k<s, la somma di k righe di H (comunque prese) è non nulla Dimostrazione:
Siano R1,….,Rn le n righe di H(vettori in Z2n-k).
(): Per assurdo supponiamo che esistano k righe fra R1,….,Rn (con k<s) di somma nulla.
Costruito il vettore v=(x1,…..,xn) in Z2n che ha =1 tutti i bits di indici uguali a quelli delle righe suddette, e =0 tutti gli altri bits, si avrebbe:
vH = x1R1+…..+xkRk=0
dunque vC e il peso di v sarebbe per costruzione (v)=k<s≤ (contraddizione: la distanza è il peso minimo di una parola non nulla di C).
(): Per assurdo supponiamo <s. Esiste v=(x1,…..,xn)C di peso minimo (v)=. Si avrebbe:
0 = vH = x1R1+…..+xkRk
Ma x1R1+…..+xkRk coinciderebbe con la somma delle righe di H di indici uguali a quelli dei bits
=1 di v, e tale somma sarebbe nulla (in contraddizione con l’ipotesi, essendo <s).
La condizione espressa dal precedente Teorema sulle righe della matrice di controllo H diventa più chiara per valori piccoli di s:
s=2: si avrà 2 nessuna riga di H è nulla
s=3: si avrà 3 nessuna riga di H è nulla e tutte le righe di H sono distinte (perché affermare che la somma di 2 righe Ri, Rj è nulla equivale ad affermare che Ri=Rj , essendo Rj = -Rj)
Dal Teorema segue anche una condizione affinché sia =s. Poiché ciò equivale ad affermare che è vero che s ma che non è vero che s+1:
Corollario. Sia H la matrice di controllo di un codice CZ2n di lunghezza n e dimensione k e sia la distanza di C. Fissato un naturale s>1 si ha:
=s per ogni numero naturale k<s, la somma di k righe di H (comunque prese) è non nulla ma esistono s righe opportune di H di somma nulla.
Esempio. Se vogliamo costruire un codice lineare (sistematico) di lunghezza n, dimensione k, e che abbia distanza =3, basta costruire una matrice di controllo nx(n-k) con righe tutte non nulle e distinte, e in cui esistano 3 righe opportune di somma nulla.
