miniatura|358x358px|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 FWHTh) és un algorisme eficient per calcular la transformada de Walsh-Hadamard (WHT). Una implementació ingènua del WHT de l'ordre tindria una complexitat computacional de O(). El FWHT h només requereix sumes o restes.
El FWHT h és un algorisme de dividir i conquerir que trenca recursivament un WHT de mida en dos WHT més petits de mida . Aquesta implementació segueix la definició recursiva de la matriu de Hadamard :
El 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, FWHTw, 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 , on A és m -essa arrel de .Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer) miniatura|308x308px|Transformada Fast Walsh–Hadamard dela funció lògica 1010 0110. Exemple de codi Python: miniatura|311x311px|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
Referències
Categoria:Processament digital del senyal