Transformada ràpida de Walsh-Hadamard

La transformada ràpida de Walsh-Hadamard aplicada a un vector de longitud 8.

En matemàtiques computacionals, la transformada ràpida de Walsh-Hadamard ordenada de Hadamard (amb acrònim anglès FWHT_h) és un algorisme eficient per calcular la transformada de Walsh-Hadamard (WHT). Una implementació ingènua del WHT de l'ordre $n=2^m$ tindria una complexitat computacional de O($n^2$). El FWHT _h només requereix $n\log n$ sumes o restes.

El FWHT _h és un algorisme de dividir i conquerir que trenca recursivament un WHT de mida $n$ en dos WHT més petits de mida $n/2$. Aquesta implementació segueix la definició recursiva de la $2^m\times 2^m$ matriu de Hadamard $H_m$:

$H_m=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{H}_{m-1}& H_{m-1}\\ H_{m-1}& -H_{m-1}\end{array}\right).$

El $1/\sqrt{2}$ els factors de normalització de cada etapa es poden agrupar o fins i tot ometre.

La transformació ràpida de Walsh-Hadamard ordenada per seqüència, també coneguda com a transformada ràpida de Walsh-Hadamard, FWHT_w, s'obté calculant la FWHT _h com a anterior, i després reordenant les sortides.

Una implementació senzilla i ràpida no recursiva de la transformada de Walsh-Hadamard es desprèn de la descomposició de la matriu de transformada de Hadamard com $H_m=A^m$, on A és m -essa arrel de $H_m$.

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

Exemple de codi Python:

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

def fwht(a) -> None:
 '''In-place Fast Walsh–Hadamard Transform of array a.'''
 h = 1
 while h < len(a):
 # perform FWHT
 for i in range(0, len(a), h * 2):
 for j in range(i, i + h):
 x = a[j]
 y = a[j + h]
 a[j] = x + y
 a[j + h] = x - y
 # normalize and increment
 a /= 2
 h *= 2