Transformada de Hadamard

Espectre de Walsh de la funció booleana 3-ària 1010 0110. La cadena binària es multiplica amb una matriu de Walsh d'ordre 8. Els quadrats vermells del fons són informació addicional i mostren el producte de la cadena binària amb una matriu de Walsh binària.

Transformada Fast Walsh–Hadamard dela funció lògica 1010 0110.

La transformada de Hadamard (també coneguda com a transformada de Walsh–Hadamard, transformada de Hadamard–Rademacher–Walsh, transformada de Walsh o transformada de Walsh–Fourier) és un exemple d'una classe generalitzada de transformades de Fourier. Realitza una operació lineal ortogonal, simètrica, involutiva i sobre nombres reals de 2^m (o nombres complexos o hipercomplexos, encara que les matrius de Hadamard són purament reals).

Es pot considerar que la transformada de Hadamard s'ha construït a partir de transformades discretes de Fourier (DFT) de mida 2 i, de fet, és equivalent a una DFT multidimensional de mida 2 × 2 × ⋯ × 2 × 2. Descomposa un vector d'entrada arbitrari en una superposició de funcions de Walsh.

La transformació rep el nom del matemàtic francès Jacques Hadamard (francès: [adamaʁ]), el matemàtic alemany-americà Hans Rademacher, i el matemàtic nord-americà Joseph L. Walsh.

La funció original pot ésser expressada mitjançant el seu espectre de Walch com un polinomi aritmètic.

La transformada de Hadamard H_m és de 2^m × Matriu de 2^m, la matriu de Hadamard (escalada per un factor de normalització), que transforma 2^m nombres reals x_n en 2^m nombres reals X_k. La transformada de Hadamard es pot definir de dues maneres: recursivament o utilitzant la representació binària (base -2) dels índexs n i k.

Recursivament, definim l'1 × 1 Hadamard transforma H₀ per la identitat H₀=1, i després defineix H_m per a m>0 per:

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

on l'1/√2 és una normalització que de vegades s'omet.

Per a m>1, també podem definir H_m per:

$$H_{m}=H_{1}\otimes H_{m-1}$$

on $\otimes$ representa el producte Kronecker. Així, a part d'aquest factor de normalització, les matrius de Hadamard estan formades completament per 1 i -1.

En el domini clàssic, es pot calcular la transformada de Hadamard $n\log n$ operacions ($n=2^{m}$), utilitzant l'algorisme de transformació ràpida de Hadamard.

La transformada de Hadamard s'utilitza àmpliament en la computació quàntica. El 2 × 2 transformacions de Hadamard $H_{1}$ és la porta de lògica quàntica coneguda com la porta Hadamard, i l'aplicació d'una porta Hadamard a cada qubit d'un registre n-qubit en paral·lel és equivalent a la transformada Hadamard $H_{n}$.

La transformada Hadamard també s'utilitza en el xifratge de dades, així com molts algorismes de processament de senyal i compressió de dades, com ara JPEG XR i MPEG-4 AVC. En aplicacions de compressió de vídeo, normalment s'utilitza en forma de suma de diferències absolutes transformades. També és una part crucial d'un nombre important d'algorismes en informàtica quàntica. La transformada de Hadamard també s'aplica en tècniques experimentals com la RMN, l'espectrometria de masses i la cristal·lografia. També s'utilitza en algunes versions de hashing sensible a la localitat, per obtenir rotacions de matrius pseudoaleatòries.