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.

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 :

Los factores de normalización para cada etapa pueden agruparse o incluso omitirse.

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]

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)