Matematica Discreta III
Lezione del giorno 4 aprile 2008
Vediamo ora come generare dei codici lineari, di lunghezza e dimensione (quindi cardinalità) prefissate.
Tutte le matrici di cui ci occuperemo saranno matrici binarie (o booleane) nel senso che avranno elementi 0,1Z2. Dato un naturale m, indicheremo con Im la matrice identica che ha tutti 1 nella diagonale principale e gli altri elementi nulli. Ricordiamo che possiamo identificare una matrice binaria 1xn (con 1 sola riga) con un vettore di Z2n (quindi con una parola di lunghezza n).
Dato un [n, k, ]-codice lineare C, essendo k la dimensione di C come Z2-spazio vettoriale esiste in C una base di n parole B = {v1,…..,vk} tale che ogni parola vC sia combinazione lineare di tali parole a coefficienti in Z2.
Costruiamo la matrice kxn M le cui righe sono i vettori v1,…..,vk della basedi C.
Tale matrice M è detta matrice generatrice del codice lineare C (essa non è univocamente determinata, perché il sottospazio C in generale ha diverse basi).
Se consideriamo una generica parola (vettore) v=(x1,…..,xn)C Z2n esistono opportuni scalari α1,
…., αk Z2 tali che v=(x1,…..,xn)=α1v1+….. αkvk .
Ciò si può tradurre in termini di prodotto fra matrici: se identifichiamo v=(x1,…..,xn)Z2n e w=(α1,
…., αk)Z2k con vettori “riga” (cioè matrici 1xn ed 1xk rispettivamente), le eguaglianze precedenti equivalgono alla seguente eguaglianza matriciale:
wM = α1v1+….. αkvk = v
Dunque, dal punto di vista algoritmico, data una matrice generatrice M del codice lineare C(matrice kxn dove k è la dimensione di C ed n la lunghezza di C), per generare le 2k parole del codice C basta far variare w=(α1,…., αk)Z2k e calcolare le diverse parole wM = v.
Se il codice C si utilizza per la codifica di (al più) 2k simboli di informazione di un insieme S, si può allora pensare che una preliminare codifica dei simboli dell’insieme S avvenga con una funzione iniettiva f: S Z2k che associa ad ogni simbolo sS una parola w lunghezza k e poi l’effettiva codifica avvenga calcolando la parola di lunghezza wM = v di lunghezza n (che è trasmessa attraverso il canale di trasmissione): in questo senso k bits della parola trasmessa v contengono l’effettiva informazione, mentre i rimanenti n-k bits (bits di “ridondanza” o di “controllo”) possono essere opportunamente utilizzati per cercare di rilevare e correggere gli errori.
Se vogliamo costruire un codice lineare C di lunghezza n e dimensione k prefissate (con 1≤k≤n), basta fissare una matrice (binaria) M con k righe ed n colonne (in cui i vettori riga siano linearmente indipendenti) e generare le parole del codice nel modo indicato sopra.
Nota: da alcuni risultati di Algebra Lineare segue che la condizione precedente sui vettori riga di M equivale alla condizione che il rango della matrice M coincida con il numero delle righe k (dunque che si possa estrarre da M una matrice quadrata kxk con determinante non nullo).
Esempio: la seguente matrice 3x4
M =
1 1 0 1
0 1 0 1
1 0 1 1
ha rango 3 (come si verifica facilmente), ed è dunque la matrice generatrice di un codice lineare C di lunghezza n=4 e dimensione k=3 (contenente 23=8 parole). Per generare le parole di C, basta far variare la parola w=(α1, α2, α3)Z23 e calcolare le diverse parole wM = v.
Per esempio se w=(1, 0, 1) si ottiene v = wM = (0, 1, 1, 0)=0110C etc….
Sviluppando i calcoli si ottengono le parole del codice C:
C = { 0000, 1101, 1010, 1011, 0111, 0110, 0001, 1100 }.
Si tratta di un [4,3,]-codice lineare, dove la distanza =1 (la parola di peso minimo in C ha peso 1).
Vedremo in seguito da quali caratteristiche della matrice generatrice si può dedurre la distanza del codice generato.
Una matrice M (binaria) kxn (con 1≤k≤n) è detta in forma standard se la matrice quadrata formata dalle prime k colonne coincide con la matrice identica Ik. In tale caso, se con M’ indichiamo la matrice kx(n-k) formata dalle ultime (n-k) colonne, scriveremo:
M = [ IkM’]
Per esempio data la matrice 3x5 in forma standard:
M =
1 1 1 0 0
1 0 0 1 0
0 1 0 0 1
si ha M = [ I3M’] dove
M’ =
1 1
1 0
0 1
La stessa matrice identica In si considera in forma standard (in questo caso M’ è la matrice “vuota”
con k righe e 0 colonne). Notiamo che una matrice kxn in forma standard (con 1≤k≤n ) ha certamente rango k, perché la matrice identica Ik ha determinante 10.
Un caso interessante si ha quando un codice C di lunghezza n e dimensione k ha una matrice generatrice M in forma standard:
M = [ IkM’]
con
M’ = (βij) i=1,….,k; j=1,…..,n-k
In tale caso per generare le parole del codice C al variare del vettore w=(α1,…., αk)Z2k calcoliamo le parole:
v = wM = (α1,…., αk, α1β11+α2β21+….+ αkβk1, …….., α1β1(n-k)+α2β2(n-k)+….+ αkβk(n-k))
Si vede dunque che, nella codifica, i primi k bits “di informazione” restano invariati, mentre i rimanenti (n-k) bits “di controllo” si ottengono come combinazioni lineari dei bits di informazione con coefficienti presi dalla matrice M’ : questo permette anche in termini algoritmici una codifica più semplice ed efficiente per il calcolo della parola da trasmettere nel canale d’informazione.
Purtroppo non tutti i codici lineari hanno una matrice generatrice in forma standard.
Definiamo codice lineare sistematico un codice che ha una matrice generatrice in forma standard.
Dimostreremo comunque che un codice lineare generico è “molto simile” (in un senso che definiremo fra poco) ad un codice lineare sistematico.
Dati due codici lineari C e C’ di lunghezza n, diremo che C è equivalente a C’ (e scriveremo CC’) se esiste un’opportuna permutazione degli indici 1,….,n tale che le parole di C’ si ottengano dalle parole di C permutando le posizioni dei bits secondo la permutazione :
C’ = { x(1)x(2)… x(n) / x1x2… xnC }
Tale relazione è una relazione di equivalenza definita nell’insieme dei codici di lunghezza n, come si dimostra facilmente. Codici lineari equivalenti sono molto simili in termini operativi e in particolare hanno, oltre che la stessa lunghezza, anche la stessa cardinalità e quindi la stessa dimensione (perché la funzione f : C C’ definita da f(x1x2… xn)= x(1)x(2)… x(n) è biunivoca), e inoltre la stessa distanza (è ovvio, perché la permutazione delle posizioni dei bits non cambia il peso della parola).
Esempio: applicando nell’ultimo esempio di codice lineare di lunghezza 5:
C = { 0000, 1101, 1010, 1011, 0111, 0110, 0001, 1100 }
la permutazione definita da (1)=4, (2)=2, (3)=3, (4)=1, si ottiene il codice equivalente:
C’= { 0000, 1101, 0011, 1011, 1110, 0110, 1000, 0101 }
