Transformada rápida de Fourier
Una transformada rápida de Fourier ( FFT ) es un algoritmo que calcula la transformada discreta de Fourier (DFT) de una secuencia, o su inversa (IDFT). El análisis de Fourier convierte una señal de su dominio original (a menudo tiempo o espacio) a una representación en el dominio de la frecuencia y viceversa. La DFT se obtiene descomponiendo una secuencia de valores en componentes de diferentes frecuencias. [1] Esta operación es útil en muchos campos, pero calcularla directamente a partir de la definición suele ser demasiado lento para ser práctico. Una FFT calcula rápidamente tales transformaciones factorizando la matriz DFTen un producto de factores escasos (en su mayoría cero). [2] Como resultado, se las arregla para reducir la complejidad de calcular la DFT desde , que surge si uno simplemente aplica la definición de DFT, a , donde está el tamaño de los datos. La diferencia de velocidad puede ser enorme, especialmente para conjuntos de datos extensos donde N puede ser de miles o millones. En presencia de error de redondeo , muchos algoritmos de FFT son mucho más precisos que evaluar la definición de DFT directa o indirectamente. Hay muchos algoritmos FFT diferentes basados en una amplia gama de teorías publicadas, desde la aritmética simple de números complejos hasta la teoría de grupos yteoría de números .
Las transformadas rápidas de Fourier se utilizan ampliamente para aplicaciones en ingeniería, música, ciencias y matemáticas. Las ideas básicas se popularizaron en 1965, pero algunos algoritmos se habían derivado ya en 1805. [1] En 1994, Gilbert Strang describió la FFT como "el algoritmo numérico más importante de nuestra vida", [3] [4] y fue incluido en los 10 mejores algoritmos del siglo XX por la revista IEEE Computing in Science & Engineering . [5]
Los algoritmos de FFT más conocidos dependen de la factorización de N , pero hay FFT con complejidad O ( N log N ) para todo N , incluso para N primo . Muchos algoritmos FFT dependen solo del hecho de que es una raíz primitiva N - ésima de la unidad y, por lo tanto, se pueden aplicar a transformaciones análogas sobre cualquier campo finito , como las transformadas teóricas de números . Dado que la DFT inversa es la misma que la DFT, pero con el signo opuesto en el exponente y un factor 1 / N , cualquier algoritmo de FFT puede adaptarse fácilmente.
El desarrollo de algoritmos rápidos para DFT se remonta al trabajo inédito de Carl Friedrich Gauss en 1805 cuando lo necesitaba para interpolar la órbita de los asteroides Pallas y Juno a partir de observaciones de muestra. [6] [7] Su método fue muy similar al publicado en 1965 por James Cooley y John Tukey , a quienes generalmente se les atribuye la invención del algoritmo FFT genérico moderno. Si bien el trabajo de Gauss fue anterior incluso a los resultados de Joseph Fourier en 1822, no analizó el tiempo de cálculo y finalmente utilizó otros métodos para lograr su objetivo.
