La transformada rápida de Walsh
Observemos que la transformada de Walsh bidimensional, puede calcularse aplicando repetidamente la transformada de Walsh unidimensional:
Un algoritmo que calcule la transformada de Walsh unidimensional tiene de complejidad O(N2). Existe un algoritmo "rápido" que calcula dicha transformada en O(N log N) operaciones (donde N=2k).
Para conseguir tal reducción, hemos de darnos cuenta que si escribimos N=2M entonces
W(u)=1/2 ( Wp(u) + Wi(u) )
donde
y
Además, se cumple que
W(u+M)=1/2 ( Wp(u) - Wi(u) )
siendo u=0,1,2,..., M-1.
Por tanto, para conocer la transformada de Walsh, W(u), para todo u, sólo tenemos que calcular Wp(u) y Wi(u) para u=0,1,2,...,N/2-1. Si volvemos a aplicar el mismo razonamiento para M=2L, sólo tendremos que calcular el valor de Wp(u) y de Wi(u) para u=0,1,2,...,N/4-1, y así sucesivamente.
Por ejemplo, si N=16, debemos calcular Wp(u) y de Wi(u) para u=0,1,2,3,4,5,6,7. Observemos que Wp(u) utiliza los valores {f(0),f(2),f(4),f(6)} y Wi(u) los valores {f(1),f(3)f(5),f(7)}.
Por tanto, calcular Wp(u) es lo mismo que calcular la transformada de Wals de una función f1 de 4 valores tal que f1(0)=f(0), f1(1)=f(2), f1(2)=f(4), f1(3)=f(6). Y de forma análoga ocurre con Wi(u).
La transformada de Walsh de f1 se calcula, hallando el valor de Wp(u) y de Wi(u) para u=0,1. Pero de nuevo, Wp(u) consiste en la transformada de Walsh de una función f2 de 2 valores tal que f2(0)=f1(0)=f(0) y f2(1)=f1(2)=f(4). Y de forma análoga ocurre con Wi(u).
Este proceso puede verse también en forma matricial: la matriz W de Wals de dimensión N=2k puede descomponerse en k matrices
W=A1A2...Ak
de tal forma que Ai es una matriz sparse (con muchos ceros).
Ejercicio:
Calcular la descomposición en matrices sparse Ai de W8.
Calcular la transformada rápida de Walsh de f que toma valores f(i,j)=i+j, para i,j=0,1,2,3,4,5,6,7.
Para practicar: