Transformación 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 de la WHT de orden $n=2^{m}$ tendría una complejidad computacional de O( $n^{2}$ ) . El FWHT _h solo requiere $n\log n$ sumas o restas.

El FWHT _h es un algoritmo de divide y vencerás que descompone recursivamente un WHT de tamaño $n$ en dos WHT más pequeños de tamaño $n/2$ . ^{[ 1 ]} Esta implementación sigue la definición recursiva de la $2^{m}\times 2^{m}$ Matriz 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}}$ Los factores de normalización para cada etapa pueden agruparse o incluso omitirse.

La transformada de Walsh-Hadamard rápida, FWHT _w , ordenada en secuencia , también conocida como ordenada por Walsh, se obtiene calculando la FWHT _h como se indicó anteriormente y luego reorganizando las salidas.

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

Código de ejemplo en Python

import math def fwht ( a ) -> None : """Transformación rápida de Walsh-Hadamard in situ del array a.""" assert math . log2 ( len ( a )) . is_integer (), "la longitud de a es una potencia de 2" h = 1 while h < len ( a ): # realizar 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 # normalizar e incrementar a /= math . sqrt ( 2 ) h *= 2

Véase también

Referencias

↑ Fino, BJ; Algazi, VR (1976). "Tratamiento matricial unificado de la transformada rápida de Walsh-Hadamard". IEEE Transactions on Computers . 25 (11): 1142– 1146. doi : 10.1109/TC.1976.1674569 . S2CID 13252360 .
↑ Yarlagadda y Hershey, "Análisis y síntesis de la matriz de Hadamard", 1997 (Springer)

Enlaces externos

Charles Constantine Gumas, Con un siglo de antigüedad, la rápida transformada de Hadamard demuestra su utilidad en las comunicaciones digitales.

[1] Fino, BJ; Algazi, VR (1976). "Tratamiento matricial unificado de la transformada rápida de Walsh-Hadamard". IEEE Transactions on Computers . 25 (11): 1142– 1146. doi : 10.1109/TC.1976.1674569 . S2CID 13252360 .

[2] Yarlagadda y Hershey, "Análisis y síntesis de la matriz de Hadamard", 1997 (Springer)

[ 1 ]

[ 2 ]