La transformada rápida de Fourier

Un algoritmo que calcule la transformada de Fourier  unidimensional tiene de complejidad O(N²). Existe un algoritmo "rápido" que calcula dicha transformada en O(N log N) operaciones (donde N=2^k) similar al de la transformada rápida de Walsh.

Para conseguir tal reducción, hemos de darnos cuenta que si escribimos N=2M entonces

para u=0,1,2,...,M-1, donde

y

Además, se cumple que 

siendo  u=0,1,2,..., M-1.

Por tanto, para conocer la transformada de Fourier F(u) para todo u, sólo tenemos que calcular F_p(u)  y F_i(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 F_p(u) y de F_i(u) para u=0,1,2,...,N/4-1, y así sucesivamente.

Para practicar:

• https://www.dai.ed.ac.uk/HIPR2/

• https://www.ee.siue.edu/~cvip/CVIPtools_demos/mainframe.shtml

• https://rsbweb.nih.gov/ij/