Transformada ràpida de Walsh-Hadamard

és un algorisme eficient per calcular la transformada de Walsh-Hadamard.

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.

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 en dos WHT més petits de mida .[1] Aquesta implementació segueix la definició recursiva de la matriu de Hadamard : [2]

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.[3]

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 .[4]

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

Referències

modifica
  1. Fino, B. J.; Algazi, V. R. IEEE Transactions on Computers, 25, 11, 1976, pàg. 1142–1146. DOI: 10.1109/TC.1976.1674569.
  2. «Fast Walsh-Hadamard transform - MATLAB fwht» (en anglès). https://www.mathworks.com.+[Consulta: 18 novembre 2022].
  3. «Fast Walsh Hadamard Transforms and it's inner workings» (en anglès). https://codeforces.com.+[Consulta: 18 novembre 2022].
  4. Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer)