Matricea Walsh

În matematică , o matrice Walsh este o matrice pătrată , având o putere de cât numărul de rânduri și coloane $2$ ${\ displaystyle 2}$ $2$ , cu valorile posibile ale elementelor matricei limitate la $+1$ ${\ displaystyle +1}$ $+1$ Și $-1$ ${\ displaystyle -1}$ $-1$ , astfel încât produsul scalar dintre două rânduri distincte (sau între două coloane distincte) este zero.

Matricea Walsh poate fi obținută pornind de la o matrice Hadamard ordonată natural folosind formula recursivă de mai jos. În matricea Hadamard ordonată secvențial , rândurile sunt rearanjate astfel încât numărul modificărilor semnelor să fie în ordine crescătoare. Fiecare rând al unei matrice Walsh este asociat cu o funcție Walsh .

Matricea Walsh și funcția Walsh sunt utilizate pentru a calcula transformarea Walsh și au aplicații în implementări eficiente ale unor operații care servesc procesării semnalului.

Formule

Ordonat desigur

Matricile de dimensiune Hadamard $2^{k}$ ${\ displaystyle 2 ^ {k}}$ ${\ displaystyle 2 ^ {k}}$ pentru $k\in N$ ${\ displaystyle k \ in N}$ ${\ displaystyle k \ in N}$ sunt obținute folosind următoarea formulă recursivă

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

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

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

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

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

{\ displaystyle 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}}

{\ displaystyle H (4) = {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 și 1 \\\ end {bmatrix}}}

{\ displaystyle H (4) = {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 și 1 \\\ end {bmatrix}}}

și în general

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}),

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

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

pentru $2\leq k\in N$ ${\ displaystyle 2 \ leq k \ in N}$ $2 \ leq k \ in N$ , unde este $\otimes$ ${\ displaystyle \ otimes}$ $\ otimes$ denotă produsul Kronecker între matrice.

Comandate secvențial

Ordonarea rândurilor matricei Walsh poate fi obținută pornind de la ordonarea matricei Hadamard aplicând mai întâi permutarea biților inversați și apoi permutarea codului Gray .

Utilizare în tehnologia CDMA

Teoretic

În tehnologia CDMA ( Code Division Multiple Access ) care stă la baza unor tehnologii mai cunoscute precum UMTS , matricile Walsh sunt utilizate datorită proprietăților lor particulare. Scopul este de a identifica în mod unic când un terminal inițiază o comunicare, pentru a face acest lucru există două opțiuni:

împărțiți banda disponibilă în frecvență și timp pentru a împărți semnalele fiecărui terminal și a le putea recunoaște fără conversii speciale (simplificând, luați datele trimise în frecvența indicată și în intervalul de timp ales) și aceasta este ideea pe pe care se bazează AMPS , GSM și protocoale similare.
lăsând pe toată lumea să transmită în același timp folosind o codificare diferită (idee cunoscută uneori în literatură cu metafora „partidului internațional”).

A doua idee, deși contraintuitivă, este cea pe care se bazează CDMA și derivatele. Singura măsură de precauție necesară pentru ca totul să funcționeze este să luăm coduri ortogonale unele cu altele. În acest fel, imaginând comunicațiile ca un spațiu multidimensional în care fiecare cod are propria axă, făcând produsul punct pe toate axele disponibile, dacă punctul găsit pe axă corespunde originii, nu a existat comunicare, viceversa c 'a fost comunicarea iar produsul punct indică exact ce cuvânt a fost folosit.

Un punct generic P (x, y, z)

Să simplificăm ideea cu un exemplu tridimensional în care există comunicări cu codul „x”, „y” și „z”.

Dacă persoana cu codul x vorbește, punctul rezultat se deplasează de la originea O (0,0,0) la punctul (de exemplu) R (1,0,0) în care 1 indică faptul că a trimis primul cuvânt.
Dacă vorbește și persoana cu codul y, punctul se mișcă din nou, dar de data aceasta de-a lungul axei y. Punctul rezultat este apoi Q (1,5,0) unde 5 indică faptul că a fost trimis al cincilea cuvânt de cod y.
Dacă atunci a treia persoană cu codul z este tăcută, punctul nu se mișcă, astfel încât punctul final rezultat este: Q (1,5,0) care reprezintă un anumit punct din spațiul care a fost definit. Primind punctul Q (1,5,0) facem apoi produsul scalar în raport cu axa x, văzând astfel că numărul rezultat este 1, prin urmare cuvântul trimis de persoana cu codul x este 1, deci facem produs scalar în ceea ce privește y și vedem că cuvântul este al cincilea, în cele din urmă realizăm produsul punct în raport cu z și observăm că punctul pe care îl găsim este originea, prin urmare a treia persoană nu a transmis.

Dacă în loc de 3 dispozitive avem „n”, creșteți doar numărul de axe care trec de la un spațiu tridimensional la un spațiu „n-dimensional”.

Trecându-se, așadar, de la această reprezentare „ spațială ” a ideii propuse la utilizarea practică efectivă, s-a decis utilizarea matricelor Walsh. De fapt, a fost necesar să se creeze limbaje ortogonale între ele în așa fel încât toate cuvintele lor ale unui cod să fie amplasate pe axa acestuia, dar nu în cea a celorlalte coduri, pentru a nu interfera cu comunicarea unui alt dispozitiv.

Matricile Walsh au tocmai proprietatea fundamentală că fiecare rând al matricei reprezintă un limbaj care este ortogonal în raport cu limbile celorlalte 0 la 0 0 1 1 de exemplu) este încă parte a limbajului. În matricile Walsh, cifra -1 este utilizată în locul 0 pentru a distinge mesajul invers de unul. Este util din motive de calcul, dar din punct de vedere al computerului ele reprezintă aceleași informații (adică mesajul opus celui 1).

Același subiect în detaliu: matricea Hadamard § Construcția Sylvester .

Un alt avantaj foarte util al matricelor Walsh este că sunt deosebit de ușor de „mărit” dacă dispozitivele noastre cresc ca puteri de două. În paragraful anterior s-a văzut de fapt cum matricea H ₁ are doar 1 în interior, în timp ce matricea H ₂ sunt toate 1, cu excepția ultimei care este -1. Inductiv, este suficient să luați matricea ordinii imediat inferioare, să o puneți în primele 2 câmpuri și în al treilea așa cum este și să o inversați în al patrulea. De asemenea, în paragraful anterior vedem generația „evidentă” a matricei H ₄ care este generată de 3 matrice H ₂ „normale” plus a patra inversată (iar formula pentru generarea oricăror matrice mari Walsh este prezentă).

Principala problemă cu utilizarea acestui tip de matrice este că acestea cresc ca puteri a două. Dacă, pe de altă parte, avem doar 9 dispozitive (deci nu o putere de două), problema devine mai complicată. De fapt, cu acest sistem, singura modalitate este de a utiliza 16 coduri, de a atribui 9 și de a lăsa celelalte 7 coduri să rămână neutilizate (ceea ce corespunde cu 7 dispozitive care nu comunică efectiv). Oricât funcționează acest sistem, nu este ieftin din punct de vedere al calculului, deoarece de multe ori dispozitivele implicate nu sunt câteva mână, dar sunt mai multe și, de exemplu, diferența dintre 256 și 512 nu este mică.

Studiile privind acest tip de matrice au condus la următoarele rezultate:

1867 : Sylvester reușește să descopere și să demonstreze ceea ce tocmai a fost explicat, și anume realizarea matricilor care cresc ca puteri de 2.
1893 : Hadamard descoperă matrici cu limbaje ortogonale cu 12 și 20 de linii.
1933 : Paley descoperă o metodă pentru a crea tablouri care au un număr de rânduri egal cu p + 1 unde p este un număr prim.
1962 : folosind computerul, este posibil să se găsească și să se demonstreze corectitudinea tuturor matricilor cu rânduri până la un număr maxim de 428.
2004 : se depășește limita actuală de 668 de linii (după bunul plac, matricile cu puteri de 2 sau cu p + 1 linii sunt în mod evident încă generabile dincolo de acest număr).

Uz practic

Întrebarea la acest moment este: cum utilizați acest tip de matrice în protocolul CDMA?

În primul rând, amintiți-vă că fiecare linie are proprietatea fundamentală că inversul său este încă un cuvânt al limbii. Prin urmare, pentru fiecare cod avem 3 opțiuni: transmite codul dat de matricea de referință, transmite inversul sau nu transmite.

Explicăm utilizarea practică printr-un exemplu de aplicație, folosind din nou câteva dispozitive. De această dată, pentru simplitate, vom folosi 4, deci vom folosi matricea văzută mai sus, și anume următoarele:

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

{\ displaystyle H (4) = {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 și 1 \\\ end {bmatrix}}}

{\ displaystyle H (4) = {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 și 1 \\\ end {bmatrix}}}

4 coduri vor fi apoi disponibile:

Codul A care are cuvintele: 1 1 1 1 și -1 -1 -1 -1 (inversul său)
Codul B care are cuvintele: 1 -1 1 -1 și -1 1 -1 1
Codul C care are cuvintele: 1 1 -1 -1 și -1 -1 1 1
Codul D care are cuvintele: 1 -1 -1 1 și -1 1 1 -1

Deci, să presupunem, de exemplu:

că primul dispozitiv transmite primul dintre cele două cuvinte pe care le are la dispoziție (1,1,1,1) folosind codul A care i-a fost atribuit,
că al doilea dispozitiv transmite al doilea cuvânt pe care îl dispune (-1,1, -1,1) cu codul B.
că cel de-al treilea dispozitiv nu are nimic de transmis (prin urmare este tăcut).
că al patrulea dispozitiv transmite primul cuvânt pe care îl dispune (1, -1, -1,1) cu codul D.

Cuvintele transmise sunt apoi adăugate împreună (deci doar cele ale primului, celui de-al doilea și al patrulea dispozitiv, deoarece al treilea nu a transmis) pur și simplu punându-le una peste alta și adăugând prin coloană, prin urmare:

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

 ↓ ↓ ↓ ↓
 1 1 -1 3

Prin urmare, rezultatul, care va fi transmis, este: 1, 1, -1, 3. La prima vedere pare imposibil să se urmărească mesajul transmis din acest număr. În schimb, având în vedere că furnizorul știe câte dispozitive sunt conectate la rețea și ce cod folosesc pentru a comunica, este necesar doar ca unitatea de control să verifice dacă dispozitivele pe care le gestionează au transmis ceva sau nu de fiecare dată când ajunge un semnal .

Unitatea de control întreabă dacă primul dispozitiv a trimis un semnal. Pentru a verifica, el înmulțește pur și simplu valoarea rezultată (1,1, -1,3) cu un cuvânt al limbii primului dispozitiv, deci de exemplu (1,1,1,1) (același tip de calcule ar putea se face cu cuvântul invers, procedura este analogă). Și aici multiplicarea se face pe coloane:

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

Odată găsite aceste valori, adăugați-le împreună: 1 + 1-1 + 3 = 4.
Aceasta înseamnă că există un cuvânt trimis de prima persoană și că acesta este primul dintre cele două cuvinte pe care le-ar putea transmite. Prin urmare, primul dispozitiv transmis (1,1,1,1).

Dacă, pe de altă parte, valoarea găsită ar fi fost negativă, cuvântul transmis ar fi fost invers, prin urmare (-1, -1, -1, -1). Dacă valoarea ar fi fost 0, atunci dispozitivul nu ar fi transmis.

Să verificăm că acesta este cu adevărat cazul: să încercăm să vedem dacă putem deduce ce alte două dispozitive au transmis și ele, al doilea (care a transmis cuvântul invers) și al treilea care nu a transmis nimic.

În al doilea rând: (1,1, -1,3) * (1, -1,1, -1) = 1 -1 -1 -3 = -4. Valoarea este negativă, de fapt cuvântul transmis nu a fost primul, ci al doilea, adică inversul.
Al treilea: (1,1, -1,3) * (1,1, -1, -1) = 1 + 1 + 1 -3 = 0. Valoarea este 0, de fapt al treilea dispozitiv nu a transmis.

Acest sistem funcționează foarte bine, deoarece nu necesită calcule complexe și din moment ce multiplicarea și adunarea sunt operațiile de bază ale oricărui calculator, deci sunt cele implementate în cel mai rapid mod posibil. Acest sistem este mult superior celor precedente din două motive fundamentale:

spectrul nu este împărțit în frecvență, așa că este utilizat complet.
atunci când o persoană nu difuzează nu ocupă canalul și din moment ce 35/40% din timpul de dialog constau în pauze, acest lucru a făcut rețeaua foarte grea în standardele anterioare. Frecvența și timpul au fost, de fapt, încă rezervate, chiar dacă nu au fost utilizate, în timp ce acum acest lucru nu provoacă nicio risipă de bandă care poate fi utilizată la maximum de fiecare dispozitiv.

Singura măsură de precauție care trebuie urmată pentru ca sistemul să funcționeze corect este calibrarea puterii semnalului dispozitivului pe baza distanței de la unitatea de control. Dacă distanța este mare, puterea va fi mai mare și invers. În acest fel, unitatea de control primește semnalele toate cu aceeași putere și semnalele sunt însumate corect în modul văzut anterior, altfel cele mai apropiate semnale ar fi avut o influență mai mare decât celelalte în rezultatul final. Unitatea de control, prin urmare, cu semnalul său de putere fix de referință, este singura stație care poate decripta mesajele, deoarece semnalul dispozitivelor este calibrat pe baza distanței de la aceasta și de la nimeni altcineva.

Bibliografie

C. Yuen (1972): Observații privind ordonarea funcțiilor Walsh , Tranzacții IEEE pe computere, C-21: 1452.
Lecția de predare a rețelelor și securității cursului de licență în Informatică dedicat explicației standardului CDMA desfășurat la Padova în anul universitar 2010/2011 de profesorul Massimo Marchiori .

Elemente conexe

Wavelet Haar

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere matrice Walsh

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică