Transformarea lui Hadamard

Transformata Hadamard (cunoscut și sub numele de „Walsh-Hadamard transforma“) este un exemplu al unei clase generalizată a unei transformări Fourier . Este numit după matematicianul francez Jacques Hadamard și efectuează o operație liniară și involutivă cu o matrice ortogonală și simetrică pe numere reale de $2 m$ (sau complexe , deși matricile utilizate au coeficienți reali). Aceste matrice sunt matrici Hadamard .

Transformata Hadamard poate fi văzută derivată dintr-o transformată Fourier discretă și se dovedește a fi de fapt echivalentul unei transformate Fourier discrete multidimensionale cu o dimensiune de $2 \times 2 \times ... \times 2 \times 2$ . Descompune un vector de intrare arbitrar într-o suprapunere a funcțiilor Walsh .

Definiție formală

Transformata Hadamard $H m$ utilizează o matrice de $2 m \times 2 m$ (o matrice Hadamard ) înmulțită cu un factor de normalizare și transformă 2 m numere reale $x n$ în 2 m numere reale $X k$ . Transformarea poate fi definită în două moduri: recursiv sau utilizând o reprezentare binară a indicilor n și k .

Definiție recursivă

Recursiv, definim o primă transformare $1 \times 1$ printr-o matrice $H 0$ care este matricea de identitate cu un singur element (1). Apoi definim $H m$ pentru $m > 0$ datorită următoarei relații:

{\ displaystyle H_ {m} = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} H_ {m-1} & H_ {m-1} \\ H_ {m-1} și - H_ {m-1} \ end {pmatrix}},}

unde $1 / \sqrt 2$ este un factor de normalizare care uneori este omis. Astfel, cu excepția normalizării, coeficienții matricei sunt egali cu 1 sau -1.

Definiție directă

Într-un mod echivalent, putem defini elementul $( k , n )$ al unei matrice Hadamard datorită și , unde $k$ $j$ și $n$ $j$ sunt bitul $j$ (0 sau 1) respectiv $k$ și $n$ . În acest caz, obținem ${\ displaystyle k = k_ {m-1} 2 ^ {m-1} + k_ {m-2} 2 ^ {m-2} + \ cdots + k_ {1} 2 + k_ {0}}$ ${\ displaystyle n = n_ {m-1} 2 ^ {m-1} + n_ {m-2} 2 ^ {m-2} + \ cdots + n_ {1} 2 + n_ {0}}$

{\ displaystyle \ left (H_ {m} \ right) _ {k, n} = {\ frac {1} {2 ^ {m / 2}}} (- 1) ^ {\ sum _ {j} k_ { j} n_ {j}}}

Interpretare

Acesta este un $2 \times 2 \times ... \times 2 \times 2$ transformata Fourier discretă normalizate să fie unitar, luând în considerare intrările și ieșirile ca matrice multidimensionale indexate de $n j$ și $k j$ .

Exemple

Primele matrice Hadamard sunt date de:

{\ displaystyle ~ H_ {0} = 1}

{\ displaystyle H_ {1} = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} {\ begin {array} {rr} 1 & 1 \\ 1 & -1 \ end {array }} \ end {pmatrix}}}

{\ displaystyle H_ {2} = {\ frac {1} {2}} {\ begin {pmatrix} {\ begin {array} {rrrr} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & - 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \ end {array}} \ end {pmatrix}}}

{\ displaystyle H_ {3} = {\ frac {1} {2 ^ {3/2}}} {\ begin {pmatrix} {\ begin {array} {rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & - 1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & - 1 \ end {array}} \ end {pmatrix}}}

Rândurile unei matrice Hadamard formează funcții Walsh .

Aplicații

În tratamentul calculului cuantic ,transformarea Hadamard, denumită mai des „ poarta Hadamard ” în acest context, este o rotație a unui qubit . Permite transformarea stărilor și a qubitului în două stări suprapuse cu greutate egală: și . În general, fazele sunt alese astfel încât: ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

{\ displaystyle {\ frac {| 0 \ rangle + | 1 \ rangle} {\ sqrt {2}}} \ langle 0 | + {\ frac {| 0 \ rangle - | 1 \ rangle} {\ sqrt {2} }} \ langle 1 |}

în notația Dirac . Aceasta corespunde matricei de transformare:

{\ displaystyle H_ {1} = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} 1 & 1 \\ 1 & -1 \ end {pmatrix}}}

în bază , . ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

Un număr mare de algoritmi cuantici utilizează transformarea Hadamard ca prim pas, deoarece transformă n qubiți inițializați într-o suprapunere a tuturor celor 2 n stări ortogonale exprimate în bază , cu pondere egală. ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 1 \ rangle}$

De exemplu, algoritmul lui Shor folosește o astfel de transformare.

Alte aplicații

Transformarea este utilizată în criptografie, vorbim apoi despre pseudo-transformarea lui Hadamard . De asemenea, este utilizat pentru a genera numere aleatorii dintr-o distribuție gaussiană. Este, de asemenea, utilizat în compresia datelor, cum ar fi algoritmul H.264 și pentru operațiuni de procesare a semnalului.

Note și referințe