Transformada ràpida de Walsh-Hadamard

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.

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

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}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.$

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