Matematica Discreta III
Lezione del giorno 22 maggio 2008
Ricordiamo che se M è una matrice ad elementi in {-1,1} (per esempio una matrice di Hadamard), abbiamo definito la matrice M* ottenuta sostituendo ogni -1 con 0.
Per esempio se:
M =
1 1 1 - 1
1 - 1 - 1 1
1 - 1 1 1
1 1 1 - 1 -
Allora:
M* =
1 1 0 1
0 0 1 1
0 1 1 1
1 1 0 0
Notiamo anche che, per ogni generica matrice M ad elementi in {1,-1}, la matrice binaria (-M)* si ottiene trasformando in M* ogni bit nella sua “complementare” (ogni 1 in 0 e viceversa) perché per esempio un bit 0 in (-M)* corrisponde a un -1 in –M dunque a un 1 in M ossia a un 1 in M*; invece un bit 1 in (-M)* corrisponde a un 1 in –M dunque a un -1 in M ossia a uno 0 in M*. Dal punto di vista algebrico la “complementazione” (cioè la trasformazione di 1 in 0 e viceversa) si ottiene sommando in Z2 ogni bit con 1, dunque:
(-M)* = M*+J dove J è la matrice binaria (delle stesse dimensioni di M) con tutti i bits =1.
Consideriamo una matrice di Hadamard Hr di ordine r, e le 2 matrici binarie Hr*, (-Hr)*= Hr*+J (dove J è la matrice 2rx2r con tutti i bits=1): tali 2 matrici binarie hanno in tutto 2r+2r=2r+1 righe, che sono parole binarie di lunghezza 2r,
Dimostreremo, come anticipato nella lezione precedente, che:
le 2r+1 righe delle matrici binarie Hr*, (-Hr)*= Hr*+J sono esattamente le 2r+1 parole del codice RM(r) di Reed-Muller.
Ragioniamo per induzione su r.
Per r=1 si ha per costruzione:
RM(1)= {0,1}2={00,10,01,00}
H1 =
1 - 1
1
1 -H1 =
1 1 -
1 - 1
- H1* =
0 1
1
1 -H1* =
1 0
0
0 e si ha la tesi.
Supponiamo il risultato vero per r e dimostriamolo per r+1.
Le 2r+2 parole del codice RM(r+1) sono della forma (vv+w) dove vRM(r), e w è una delle parole 00…0, 11…1 del codice di ripetizione di lunghezza r, quindi, al variare di vRM(r), sono della forma (vv) oppure (vv+11....1).
Consideriamo una generica riga della matrice
Hr+1* =
* ) (-H
* H
* H
* H
r r
r
r (dove (-Hr)*, come già visto, si ottiene sommando 1 a tutti i bits di Hr*) e dimostriamo che é una parola del codice RM(r+1).
Se la riga é nella prima metà della matrice, essa é una parola della forma (vv), con v riga della matrice Hr* dunque (per l’ipotesi induttiva) vRM(r) ossia (vv)RM(r+1).
Se la riga é nella seconda metà della matrice, essa é una parola della forma (vv+11....1), con v riga della matrice Hr* dunque (per l’ipotesi induttiva) vRM(r) ossia (v v+11....1)RM(r+1).
Con ragionamenti analoghi si dimostra che una generica riga della matrice (-Hr+1)* é una parola del codice RM(r+1), dunque il risultato é dunque vero anche per r+1.
Definiamo ora una funzione {0,1} {-1,1} associando 0 con -1 e 1 con 1: per indicare l’immagine di x{0,1} useremo il simbolo x’ (quindi 0’= -1, 1’=1). Tale funzione non è altro che l’inversa delle funzione x x* già definita da {-1,1} {0,1}. Estendiamo poi tale funzione alle parole v di qualunque lunghezza sull’alfabeto {0,1} (definendo v’ come la parola sull’alfabeto {-1,1} ottenuta sostituendo ogni 0 con -1) e alle matrici M di qualunque dimensione ad elementi in {0,1}
(definendo M’ come la matrice ad elementi in {-1,1} ottenuta sostituendo ogni 0 con -1).
Per esempio se v=010100, allora v’= -11-11-1-1.
Il risultato precedente, che lega le matrici di Hadamard e i codici RM(r) di Reed-Muller, si può allora riformulare come segue: date le 2r+1 parole vi{0,1}n di RM(r), l’insieme delle loro trasformate vi’{-1,1}n coincide con l’insieme formato dalle righe r1,…..,rn della matrice Hr, e dalle righe -r1,…..,-rn della matrice -Hr (con n=2r).
Vedremo ora come costruire un efficiente algoritmo di decodifica per i codici di Reed-Muller.
Ricordiamo che per ogni coppia di parole x,y{-1,1}n sull’alfabeto -1,1 è definito il prodotto scalare <x,y> (pensandole come vettori di lunghezza n sul campo reale): se x=(a1a2….an), y=(b1b2….bn) allora
<x,y> = a1b1+a2b2+….+anbn
Date due parole binarie v,w{0,1}n di lunghezza n, se la loro distanza è (v,w)=t esse differiscono in t degli n bits, dunque lo stesso vale per le parole associate v’,w’{-1,1}n, e se calcoliamo il prodotto scalare <v’,w’> otteniamo (tenendo conto che i bits sono 1) una somma di t addendi uguali a -1 e di (n-t) addendi uguali a 1, concludendo che:
<v’,w’> = n-2t se (v,w)=t (*)
Teorema. Dato il codice RM(r) di Reed-Muller, se vRM(r) è la parola trasmessa, w{0,1}n quella ricevuta, e se il numero di errori di trasmissione è ≤2r-2-1 (dunque (v,w) ≤2r-2-1), allora:
v è l’unica parola di RM(r) tale che <v’,w’> 2r-2r-1+2 Dimostrazione:
Essendo RM(r) un s-codice a correzione d’errore, dove s=2r-2-1, ed essendo il numero di errori di trasmissione per ipotesi ≤s, sappiamo che v è l’unica parola di RM(r) a distanza ≤2r-2-1 da w.
Sia allora z una qualunque parola del codice RM(r) distinta da v, e poniamo c=(v,w), t=(z,w). Per ipotesi c≤2r-2-1, t>2r-2-1 dunque t2r-2.
Si ha allora (per la (*)):
<v’,w’> = 2r-2c 2r-2r-1+2 <z’,w’> = 2r-2t ≤ 2r-2r-1 < 2r-2r-1+2 e si ottiene la tesi.
Come conseguenza del Teorema, si può costruire un algoritmo di decodifica per il codice RM(r) di Reed-Muller, a patto di conoscere un elenco completo delle 2r+1 parole di RM(r)={v1,…….,vn} (dove n=2r+1) e dunque delle 2r+1 parole associate v1’,…….,vn’ sull’alfabeto {1,-1}:
1) Data la parola ricevuta w, si calcola la parola associata w’ sull’alfabeto {1,-1}
2) Si decodifica w come la parola vi tale che <vi’,w’> 2r-2r-1+2 (se il numero di errori è non superiore a 2r-2-1, per il Teorema precedente vi è la parola trasmessa)
In tale algoritmo si tratta di calcolare (al più) 2r+1 prodotti scalari, ognuno ottenuto sommando 2r addendi uguali a 1.
Possiamo però ancora rendere più efficiente l’algoritmo utilizzando le matrici di Hadamard. già introdotte, ricordando che:
date le 2r+1 parole vi{0,1}n di RM(r), l’insieme delle loro trasformate vi’{-1,1}n coincide con l’insieme formato dalle righe r1,…..,rn della matrice Hr, e dalle righe -r1,…..,-rn della matrice -Hr
(con n=2r).
Con tale premessa, l’algoritmo di decodifica di RM(r) illustrato in precedenza diventa:
1) Data la parola ricevuta w, si calcola la parola associata w’ sull’alfabeto {1,-1}
2) Fra i prodotti scalari della forma:
<ri,w’> e <-ri,w’> i=1,….,2r (dove r1,…..,rn sono le righe della matrice Hr)
si individua il prodotto scalare che è 2r-2r-1+2 ; se esso corrisponde ad una ri si decodifica w come la parola binaria ri*, se invece esso corrisponde ad una -ri si decodifica w come la parola binaria (-ri)* ottenuta “complementando” ri* (cioè sommando ad ri* la parola 11…1).
In effetti però si può dimezzare il numero di prodotti scalari da calcolare (da 2r+1 a 2r) con il seguente ragionamento: se il prodotto scalare individuato nel passo 2) corrisponde ad una ri, si ha
<ri,w’> positivo, dunque il valore assoluto di <ri,w’> (coincidente con <ri,w’>) è 2r-2r-1+2; se invece il prodotto scalare individuato nel passo 2) corrisponde ad una -ri, si ha <-ri,w’>= -<ri,w’>
positivo, dunque <ri,w’> negativo, e il valore assoluto di <ri,w’> (coincidente con -<ri,w’>) è ugualmente 2r-2r-1+2.
Basta allora nel passo 2) individuare il prodotto scalare <ri,w’> (i=1,….,2r) il cui valore assoluto sia 2r-2r-1+2. Se tale prodotto scalare è >0, si decodifica w come la parola binaria ri*, se invece esso è <0 si decodifica w come la parola binaria (-ri)* ottenuta “complementando” ri* (cioè sommando ad ri* la parola 11…1).
Esempio. Nel codice RM(3) supponiamo ricevuta la parola w=01110000, e decodifichiamola con l’algoritmo precedente. La parola corrispondente (con coordinate 1) è w’= -1111-1-1-1-1 e calcolando il prodotto scalare di w’ (ordinatamente) per le righe di H3 si ottengono 8 interi relativi:
-2,-2,-2,-2,6,-2,-2,-2
Poiché quello di posto j=5 è quello (unico) di valore assoluto 2r-2r-1+2=6 ed è positivo, la parola v di RM(3) a distanza minima da w è la riga 5 di H3* ossia la riga 5 di H3 trasformata in binario sostituendo -1 con 0, cioè:
v = 11110000
Se invece abbiamo ricevuto la parola w=11010101, la parola corrispondente (con coordinate 1) è w’= 11-11-11-11) e calcolando il prodotto scalare di w’ (ordinatamente) per le righe di H3 si ottengono 8 interi relativi:
2,-6,2,2,2,2,2,2
Poiché quello di posto j=2 è quello (unico) di valore assoluto 2r-2r-1+2=6 ed è negativo, la parola v di RM(3) a distanza minima da w è il complemento della riga 2 di H3 trasformata in binario sostituendo -1 con 0, cioè:
v = 10101010+11111111 = 01010101
Nel caso, per esempio, del codice RM(5) (utilizzato nell’invio delle foto della sonda spaziale Mariner 9), per la decodifica si tratta di costruire la matrice di Hadamard H5 con 32 righe e 32 colonne. Se r1,…..,r32 sono le sue righe, e se la parola ricevuta è w, si calcola la parola associata w’
sull’alfabeto {1,-1}, e si cerca un prodotto scalare fra <ri,w’> che sia in valore assoluto non minore di 2r-2r-1+2=18: se esso è positivo si decodifica w trasformando la riga ri in binario; se esso è negativo si decodifica w trasformando la riga ri in binario e calcolandone il “complemento”.
La matrice H5 si può costruire facilmente induttivamente, dopo avere costruito le matrici Hr con r<5.
Una rappresentazione grafica della matrice H5 è la seguente (dove ogni quadratino nero rappresenta +1, uno bianco -1):
Se si considerano la trasformata in binario H5* e la sua “complementare” (-H5)* (incollata di seguito) si ottiene una matrice 64x32 le cui 64 righe sono le parole del codice RM(5) di Reed- Muller. La rappresentazione grafica di tale matrice 64x32 si ottiene da quella precedente (in cui stavolta un quadratino nero rappresenta un bit 1, uno bianco un bit 0) incollando di seguito il suo
“negativo”:
