Transformada rápida de Fourier
La transformada rápida de Fourier, conocida por la abreviatura FFT (del inglés Fast Fourier Transform) es un algoritmo eficiente que permite calcular la transformada de Fourier discreta (DFT) y su inversa.
Cuando se habla del tratamiento digital de señales, el algoritmo FFT impone algunas limitaciones en la señal y en el espectro resultante ya que la señal muestreada y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos.
La transformada discreta de Fourier (DFT, por sus siglas en inglés) de esta señal se define[1] como: en la cual
La evaluación directa de esa fórmula requiere
operaciones aritméticas, pero con un algoritmo FFT se puede obtener el mismo resultado con solo
[2] 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 discreta de Fourier (conocida por su sigla inglesa, IDFT).
Por lo general, tenemos que: donde el símbolo de asterisco (*) denota la conjugada compleja de la expresión que le antecede.
El algoritmo de la transformada de Fourier Rápida (FFT), fue popularizado por los matemáticos estadounidenses James William Cooley y John Wilder Tukey en 1965.
Efectuar la multiplicación usual de matrices directa requeriría
Por lo tanto, puede escribirse de la siguiente manera: Debido a que
es un entero, es posible factorizar la matriz en el producto de dos matrices: Los elementos
han cambiado de lugar en el vector que se encuentra del lado izquierdo.
y el producto ya se ha obtenido en el cálculo del primer elemento y puede, en consecuencia, solo almacenarse hasta que se necesite y luego restarse en vez de sumarse.
Hasta ahora se tienen dos multiplicaciones y cuatro sumas.
Apelando a condiciones de simetrías similares en la segunda multiplicación de matrices, se encuentra que se requieren dos multiplicaciones y cuatro sumas más.
Así, en total, se necesitan cuatro multiplicaciones y ocho adiciones.
Puesto que, computacionalmente, las multiplicaciones requieren por lo general mucho más tiempo de cómputo que las adiciones, el algoritmo de FFT para cuatro puntos es alrededor de cuatro veces más rápido que la FDT directa.
Es el algoritmo más famoso para el cálculo de una FFT, diseñado por Cooley y Tukey en 1965.
Tomando como entrada una señal discreta x[n] con N muestras, se basa en dividir la señal de entrada en otras dos señales de N/2 muestras (por un lado los coeficientes pares y por otro los impares), y se envían cada una de estas subseñales a una FFT de tamaño N/2 puntos.
, donde k es la posición del vector salida, y se suma a las muestras pares.
