Matrice di Walsh

In matematica, una matrice di Walsh è una matrice quadrata, avente come numero delle righe e delle colonne una potenza di  $2$,  con i valori possibili degli elementi della matrice limitati a  $+1$  e  $-1$, tale che il prodotto scalare fra due righe distinte (o fra due colonne distinte) sia zero.

La matrice di Walsh può essere ottenuta a partire da una matrice di Hadamard ordinata naturalmente mediante la formula ricorsiva sotto riportata. Nella matrice di Hadamard ordinata sequenzialmente si risistemano le righe in modo che il numero dei cambiamenti di segno sia in ordine crescente. Ogni riga di una matrice di Walsh è associata a una funzione di Walsh.

La matrice di Walsh e la funzione di Walsh sono usate per calcolare la trasformata di Walsh e hanno applicazioni nelle implementazioni efficienti di alcune operazioni che servono al processo dei segnali.

Formule

Ordinata naturalmente

Le matrici di Hadamard di dimensione  $2^{k}$  per  $k\in N$  sono ottenute mediante la seguente formula ricorsiva

$H(1)={\begin{bmatrix}1\end{bmatrix}}$

$H(2)={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$

$H(4)={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}$

e in generale

$H(2^{k})={\begin{bmatrix}H(2^{k-1})&H(2^{k-1})\\H(2^{k-1})&-H(2^{k-1})\end{bmatrix}}=H(2)\otimes H(2^{k-1}),$

per  $2\leq k\in N$,  dove  $\otimes$  denota il prodotto di Kronecker fra matrici.

Ordinata sequenzialmente

L'ordinamento delle righe della matrice di Walsh può essere ottenuto a partire dall'ordinamento della matrice di Hadamard applicando in primo luogo la permutazione a bit invertito e poi la permutazione del codice di Gray.

Utilizzo nella tecnologia CDMA

Teorizzazione

Nella tecnologia CDMA (Code Division Multiple Access) che sta alla base di tecnologie più conosciute come l'UMTS si fa uso delle matrici di Walsh a causa delle loro particolari proprietà. L'obiettivo è quello di identificare in modo univoco quando un terminale sta iniziando una comunicazione, per far ciò le opzioni sono due:

1. dividere la banda disponibile in frequenza e temporalmente in modo da dividere i segnali di ogni terminale e poterli riconoscere senza particolari conversioni (semplificando si prendono i dati inviati nella frequenza indicata e nell'intervallo di tempo scelto) ed è l'idea su cui si basano i protocolli AMPS, GSM e simili.
2. lasciare che tutti trasmettano contemporaneamente utilizzando una codifica diversa (idea a volte nota in letteratura con la metafora del "party internazionale").

La seconda idea, per quanto controintuitiva, è quella su cui si basano il CDMA e derivati. L'unico accorgimento necessario per far funzionare il tutto, è quello di prendere dei codici ortogonali tra di loro. In questo modo, immaginando le comunicazioni come uno spazio multidimensionale dove ogni codice ha il suo asse, facendo il prodotto scalare su tutti gli assi disponibili, se il punto trovato sull'asse corrisponde all'origine, non c'è stata comunicazione, viceversa c'è stata comunicazione e il prodotto scalare del punto indica esattamente quale parola è stata utilizzata.

Un generico punto P(x,y,z)

Semplifichiamo l'idea con un esempio tridimensionale dove ci sono le comunicazioni col codice "x", quello "y" e quello "z".

• Se la persona col codice x parla, il punto risultante si sposta dall'origine O(0,0,0) al punto (per esempio) R(1,0,0) dove 1 indica che ha mandato la prima parola.
• Se anche la persona col codice y parla, il punto si sposta nuovamente ma questa volta lungo l'asse y. Il punto risultante è quindi Q(1,5,0) dove 5 indica che è stata spedita la quinta parola del codice y.
• Se poi la terza persona col codice z tace, il punto non si sposta quindi il punto finale risultante è: Q(1,5,0) che rappresenta un certo punto nello spazio che è stato definito. Ricevendo il punto Q(1,5,0) si fa quindi il prodotto scalare rispetto all'asse x, vedendo così che il numero risultante è 1 quindi la parola inviata dalla persona col codice x è 1, quindi facciamo il prodotto scalare rispetto a y e vediamo che la parola è la quinta, infine facciamo il prodotto scalare rispetto a z e notiamo che il punto che troviamo è l'origine, pertanto la terza persona non ha trasmesso.

Se invece di 3 dispositivi ne abbiamo "n", basta aumentare il numero degli assi passando da uno spazio tri-dimensionale ad uno spazio "n-dimensionale".

Spostandoci quindi da questa rappresentazione "spaziale" dell'idea proposta all'effettivo utilizzo pratico, si è pensato di utilizzare le matrici di Walsh. Era infatti necessario creare dei linguaggi ortogonali tra di loro in modo tale che tutte le loro parole di un codice si situino sul suo asse ma non in quello degli altri codici, per non interferire con la comunicazione di un altro dispositivo.

Le matrici di Walsh hanno proprio la proprietà fondamentale che ogni riga della matrice rappresenta un linguaggio che è ortogonale rispetto ai linguaggi di tutte le altre righe e che il suo inverso (ovvero, scambiando gli uni con zeri e viceversa, quindi passando da 1 1 0 0 a 0 0 1 1 per esempio) fa ancora parte del linguaggio. Nelle matrici di Walsh si utilizza la cifra -1 invece che lo 0 per contraddistinguere il messaggio inverso all'uno. Esso torna utile per motivi computazionali, ma da un punto di vista del calcolatore essi rappresentano la medesima informazione (ovvero, il messaggio opposto a 1).

Un altro vantaggio molto utile delle matrici di Walsh è che sono particolarmente facili da "aumentare" se i nostri dispositivi aumentano come potenze di due. Nel paragrafo precedente si è infatti visto come la matrice H₁ abbia al suo interno solo un 1, mentre la matrice H₂ siano tutti 1, tranne l'ultimo che è -1. Induttivamente, basta infatti prendere la matrice di ordine immediatamente inferiore, metterla nei primi 2 campi e nel terzo così com'è e invertirla nel quarto. Sempre nel paragrafo precedente si vede quindi la "ovvia" generazione della matrice H₄ che è generata da 3 matrici H₂ "normali" più la quarta invertita (ed è presente la formula per generare matrici di Walsh grandi a piacere).

Il problema principale che c'è nell'utilizzare questo tipo di matrici è che crescono come potenze di due. Se invece noi abbiamo solo 9 dispositivi (quindi non una potenza di due) la questione si complica. Infatti, con questo sistema l'unico modo è utilizzare 16 codici, assegnarne 9 e lasciare che gli altri 7 codici rimangano inutilizzati (il che corrisponde ad avere 7 dispositivi che di fatto non comunicano). Per quanto questo sistemi funzioni, non è economico da un punto di vista computazionale visto che spesso i dispositivi coinvolti non sono poche manciate, ma sono parecchi e per esempio la differenza tra 256 e 512 non è poca.

Gli studi riguardo a questo tipi di matrici hanno portato ai seguenti risultati:

• 1867: Sylvester riesce a scoprire e dimostrare quanto appena spiegato, ovvero la realizzazione di matrici che aumentano come potenze di 2.
• 1893: Hadamard scopre le matrici con linguaggi ortogonali con 12 e 20 righe.
• 1933: Paley scopre un metodo per creare le matrici che abbiano un numero di righe uguale a p+1 dove p è un numero primo.
• 1962: utilizzando il computer, si riesce a trovare e dimostrare la correttezza di tutte le matrici con righe fino ad un numero massimo di 428.
• 2004: si passa al limite attuale di 668 righe (a piacimento, le matrici con potenze di 2 o con p+1 righe sono ovviamente ancora generabili oltre questo numero).

Utilizzo pratico

La domanda a questo punto è: come si utilizzano questo tipo di matrici nel protocollo CDMA?

Innanzi tutto ricordiamo che ogni riga ha la proprietà fondamentale che la sua inversa è ancora una parola del linguaggio. Pertanto, per ogni codice abbiamo a disposizione 3 opzioni: trasmettere il codice dato dalla matrice di riferimento, trasmettere il suo inverso o non trasmettere.

Spieghiamo l'utilizzo pratico tramite un esempio applicativo, anche questa volta utilizzando pochi dispositivi. Questa volta per semplicità ne useremo 4, utilizzeremo quindi la matrice vista in precedenza, ovvero la seguente:

$H(4)={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}$

Saranno quindi disponibili 4 codici:

• Il codice A che ha le parole: 1 1 1 1 e -1 -1 -1 -1 (la sua inversa)
• Il codice B che ha le parole: 1 -1 1 -1 e -1 1 -1 1
• Il codice C che ha le parole: 1 1 -1 -1 e -1 -1 1 1
• Il codice D che ha le parole: 1 -1 -1 1 e -1 1 1 -1

Supponiamo quindi per esempio:

• che il primo dispositivo trasmetta la prima delle due parole che ha disposizione (1,1,1,1) utilizzando il codice A che gli è stato assegnato,
• che il secondo dispositivo trasmetta la seconda parola che ha disposizione (-1,1,-1,1) col codice B.
• che il terzo dispositivo non abbia nulla da trasmettere (quindi tace).
• che il quarto dispositivo trasmetta la prima parola che ha disposizione (1,-1,-1,1) col codice D.

Si sommano quindi le parole trasmesse (quindi solo quelle del primo, del secondo e del quarto dispositivo visto che il terzo non ha trasmesso) semplicemente mettendole una sopra l'altra e sommando per colonna, quindi:

 1  1  1  1
 +  +  +  +
-1  1 -1  1
 +  +  +  +
 1 -1 -1  1

 ↓  ↓  ↓  ↓
 1  1 -1  3

Pertanto il risultato, ovvero quello che verrà trasmesso, è: 1, 1, -1, 3. A prima vista sembra impossibile risalire da questo numero al messaggio trasmesso. Invece dato che il provider sa quanti dispositivi sono connessi alla rete e che codice stanno utilizzando per comunicare, basta soltanto che la centralina controlli se i dispositivi che sta gestendo hanno trasmesso qualcosa o meno ogni volta che gli arriva un segnale.

• La centralina si domanda se il primo dispositivo ha mandato un segnale. Per verificare si limita a moltiplicare il valore risultante (1,1,-1,3) per una parola del linguaggio del primo dispositivo, quindi per esempio (1,1,1,1) (si poteva fare lo stesso tipo di calcoli anche con la parola inversa, il procedimento è analogo). Anche qui la moltiplicazione è per colonna:

1  1 -1  3
*  *  *  *
1  1  1  1
↓  ↓  ↓  ↓
1  1 -1  3

• Una volta trovati questi valori, li si sommano: 1+1-1+3 = 4.
• Questo vuol dire che c'è una parola inviata dalla prima persona e che questa è la prima delle due parole che poteva trasmettere. Pertanto, il primo dispositivo ha trasmesso (1,1,1,1).

Se invece il valore trovato fosse stato negativo, la parola trasmessa sarebbe stata l'inversa, quindi (-1,-1,-1,-1). Se il valore fosse stato 0, allora il dispositivo non avrebbe trasmesso.

Verifichiamo che è veramente così: proviamo a vedere se riusciamo a desumere cos'hanno trasmesso anche altri due dispositivi, il secondo (che ha trasmesso la parola inversa) e il terzo che non ha trasmesso nulla.

• Secondo: (1,1,-1,3) * (1,-1,1,-1) = 1 -1 -1 -3 = -4. Il valore è negativo, infatti la parola trasmessa non era la prima, ma la seconda cioè l'inversa.
• Terzo: (1,1,-1,3) * (1,1,-1,-1) = 1 + 1 + 1 -3 = 0. Il valore è 0, infatti il terzo dispositivo non ha trasmesso.

Questo sistema funziona molto bene visto che non richiede calcoli complessi e visto che la moltiplicazione e l'addizione sono le operazioni base di qualsiasi calcolatore quindi sono quelle implementate nel modo più veloce possibile. Questo sistema è molto superiore ai precedenti per due motivi fondamentali:

1. lo spettro non viene diviso in frequenza quindi viene utilizzato completamente.
2. quando una persona non trasmette non occupa il canale ed essendo il 35/40% del tempo dei dialoghi composto da pause, questo appesantiva molto la rete negli standard precedenti. La frequenza e il tempo venivano infatti comunque riservati anche se non utilizzati, mentre ora ciò non provoca nessuno spreco di banda che può essere utilizzata al massimo da ogni dispositivo.

L'unico accorgimento che bisogna seguire per far funzionare il sistema correttamente, è quello di calibrare la potenza del segnale del dispositivo in base alla distanza dalla centrale. Se la distanza è alta la potenza sarà maggiore e viceversa. In questo modo la centrale riceve i segnali tutti con la stessa potenza e i segnali si sommano correttamente nel modo visto precedentemente, altrimenti i segnali più vicini avrebbero avuto un'influenza maggiore rispetto agli altri nel risultato finale. La centrale quindi, col suo segnale di potenza fissa di riferimento, è l'unica stazione che può decifrare i messaggi visto che il segnale dei dispositivi è calibrato in base alla distanza da lei e da nessun altro.

Bibliografia

• C. Yuen (1972): Remarks on the Ordering of Walsh Functions, IEEE Transactions on Computers, C-21: 1452.
• Lezione dell'insegnamento di Reti e Sicurezza del corso della laurea in Informatica dedicata alla spiegazione dello standard CDMA tenuta a Padova nell'anno accademico 2010/2011 dal professor Massimo Marchiori.

Voci correlate

• Wavelet Haar

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla matrice di Walsh