Transformada rápida de Walsh-Hadamard

En matemáticas computacionales, la transformada rápida de Walsh-Hadamard ordenada por Hadamard ( FWHT _h ) es un algoritmo eficiente para calcular la transformada de Walsh-Hadamard (WHT). Una implementación ingenua del WHT de orden tendría una complejidad computacional de O( ) . El FWHT _h requiere solo sumas o restas.${\displaystyle n=2^{m}}$${\displaystyle n^{2}}$${\displaystyle n\log n}$

El FWHT _h es un algoritmo divide y vencerás que descompone recursivamente un WHT de tamaño en dos WHT más pequeños de tamaño . ^[1] Esta implementación sigue la definición recursiva de la matriz de Hadamard :${\displaystyle n}$${\displaystyle n/2}$${\displaystyle 2^{m}\times 2^{m}}$ ${\displaystyle H_{m}}$

Los factores de normalización para cada etapa pueden agruparse o incluso omitirse.${\displaystyle 1/{\sqrt {2}}}$

La Secuencia de ordenada , también conocido como Walsh ordenada, rápido Walsh-Hadamard transformar, FWHT _w , se obtiene calculando la FWHT _h como anteriormente, y luego la reordenación de las salidas.

Una implementación simple, rápida y no recursiva de la transformada de Walsh-Hadamard se deriva de la descomposición de la matriz de transformada de Hadamard como , donde A es la m -ésima raíz de . ^[2]${\displaystyle H_{m}=A^{m}}$${\displaystyle H_{m}}$

Este artículo relacionado con algoritmos o estructuras de datos es un trozo . Puedes ayudar a Wikipedia expandiéndola .

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

Ejemplo para el vector de entrada (1, 0, 1, 0, 0, 1, 1, 0)