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 la orden.tendría una complejidad computacional de O () . El FWHT h solo requiere sumas o restas.
El FWHT h es un algoritmo de divide y vencerás que descompone de forma recursiva un WHT de tamaño en dos WHT más pequeños de tamaño . [1] Esta implementación sigue la definición recursiva del Matriz de Hadamard :
La los factores de normalización para cada etapa pueden agruparse o incluso omitirse.
La secuencia ordenada , también conocida como transformada rápida de Walsh-Hadamard ordenada de Walsh, FWHT w , se obtiene calculando la FWHT h como se indicó anteriormente, y luego reordenando las salidas.
Una implementación no recursiva rápida simple de la transformada de Walsh-Hadamard se sigue de la descomposición de la matriz de la transformada de Hadamard como , donde A es m-ésima raíz de . [2]
Código de ejemplo de Python
def fwht ( a ) -> Ninguno : "" "Transformada rápida de Walsh-Hadamard en el lugar de la matriz a." "" h = 1 while h < len ( a ): para i en el rango ( 0 , len ( a ), h * 2 ): para j en el rango ( i , i + h ): x = a [ j ] y = a [ j + h ] a [ j ] = x + y a [ j + h ] = x - y h * = 2
Ver también
Referencias
- ^ Fino, BJ; Algazi, VR (1976). "Tratamiento de matriz unificada de la transformación rápida de Walsh-Hadamard". Transacciones IEEE en computadoras . 25 (11): 1142-1146. doi : 10.1109 / TC.1976.1674569 .
- ^ Yarlagadda y Hershey, "Análisis y síntesis de la matriz de Hadamard", 1997 (Springer)
enlaces externos
- Charles Constantine Gumas, centenario, la rápida transformación de Hadamard resulta útil en las comunicaciones digitales