Transformada rápida de Fourier

la transformada rápida de Fourier (FFT, del inglés Fast Fourier Transform). La FFT constituye uno de los mayores desarrollos en la tecnología del tratamiento de la imagen (en general, de cualquier tipo de señal). Las diversas aplicaciones de la FFT surgen de sus raíces: la transformada discreta de Fourier y de ahí, la transformada de Fourier. La evolución de la informática, particularmente la del ordenador personal, ha hecho de la FFT una herramienta de análisis manejable y potente. Durante el estudio del algoritmo FFT, podremos apreciar su enorme potencia. Además, haremos una comparación entre el número de operaciones que supone un cálculo directo de la DFT y el que supone el cálculo de la DFT mediante el algoritmo FFT. Primero veremos a fondo la FFT unidimensional. Después, la FFT bidimensional se comprenderá fácilmente. Sean x0, ...., xn-1 números complejos. La transformada discreta de Fourier (DFT, por sus siglas en inglés) se define como

La evaluación directa de esa fórmula requiere O(n²) operaciones aritméticas. Mediante un algoritmo FFT se puede obtener el mismo resultado con sólo O(n log n) operaciones. En general, dichos algoritmos dependen de la factorización de n pero, al contrario de lo que frecuentemente se cree, existen FFTs para cualquier n, incluso con n primo. La idea que permite esta optimización es la descomposición de la transformada a tratar en otras más simples y éstas a su vez hasta llegar a transformadas de 2 elementos donde k puede tomar los valores 0 y 1. Una vez resueltas las transformadas más simples hay que agruparlas en otras de nivel superior que deben resolverse de nuevo y así sucesivamente hasta llegar al nivel más alto. Al final de este proceso, los resultados obtenidos deben reordenarse. Dado que la transformada discreta de Fourier inversa es análoga a la transformada discreta de Fourier, con distinto signo en el exponente y un factor 1/n, cualquier algoritmo FFT puede ser fácilmente adaptado para el cálculo de la transformada inversa.