Algoritmo Cooley-Tukey FFT
El algoritmo Cooley-Tukey , llamado así por JW Cooley y John Tukey , es el algoritmo de transformada rápida de Fourier (FFT) más común . Vuelve a expresar la transformada discreta de Fourier (DFT) de un tamaño compuesto arbitrario en términos de N 1 DFT más pequeñas de tamaños N 2 , recursivamente , para reducir el tiempo de cálculo a O ( N log N ) para N altamente compuestos ( números suaves). Debido a la importancia del algoritmo, las variantes específicas y los estilos de implementación se conocen por sus propios nombres, como se describe a continuación.
Debido a que el algoritmo Cooley-Tukey divide la DFT en DFT más pequeñas, se puede combinar arbitrariamente con cualquier otro algoritmo para la DFT. Por ejemplo, el algoritmo de Rader o Bluestein se puede usar para manejar factores primos grandes que no se pueden descomponer por Cooley-Tukey, o el algoritmo de factor primo se puede explotar para una mayor eficiencia en la separación de factores primos relativamente .
El algoritmo, junto con su aplicación recursiva, fue inventado por Carl Friedrich Gauss . Cooley y Tukey lo redescubrieron y popularizaron de forma independiente 160 años después.
Este algoritmo, incluida su aplicación recursiva, fue inventado alrededor de 1805 por Carl Friedrich Gauss , quien lo usó para interpolar las trayectorias de los asteroides Palas y Juno , pero su trabajo no fue ampliamente reconocido (siendo publicado solo póstumamente y en neolatín ). [1] [2] Sin embargo, Gauss no analizó el tiempo computacional asintótico. También se redescubrieron varias formas limitadas varias veces a lo largo del siglo XIX y principios del XX. [2] Las FFT se hicieron populares después de que James Cooley de IBM y John Tukey de Princetonpublicó un artículo en 1965 reinventando el algoritmo y describiendo cómo realizarlo convenientemente en una computadora. [3]
Según los informes, a Tukey se le ocurrió la idea durante una reunión del Comité Asesor Científico del presidente Kennedy que discutía formas de detectar pruebas de armas nucleares en la Unión Soviética mediante el empleo de sismómetros ubicados fuera del país. Estos sensores generarían series temporales sismológicas. Sin embargo, el análisis de estos datos requeriría algoritmos rápidos para calcular DFT debido a la cantidad de sensores y la duración del tiempo. Esta tarea fue fundamental para la ratificación de la propuesta de prohibición de los ensayos nucleares, de modo que se pudiera detectar cualquier violación sin necesidad de visitar las instalaciones soviéticas. [4] [5] Otro participante en esa reunión, Richard Garwinde IBM, reconoció el potencial del método y puso a Tukey en contacto con Cooley, pero asegurándose de que Cooley no supiera el propósito original. En cambio, se le dijo a Cooley que esto era necesario para determinar las periodicidades de las orientaciones de espín en un cristal tridimensional de helio-3 . Cooley y Tukey publicaron posteriormente su artículo conjunto, y la adopción generalizada siguió rápidamente debido al desarrollo simultáneo de convertidores de analógico a digital capaces de muestrear a velocidades de hasta 300 kHz.
El hecho de que Gauss había descrito el mismo algoritmo (aunque sin analizar su costo asintótico) no se dio cuenta hasta varios años después del artículo de 1965 de Cooley y Tukey. [2] Su artículo citó como inspiración solo el trabajo de IJ Good sobre lo que ahora se llama el algoritmo FFT de factor primo (PFA); [3] aunque inicialmente se pensó que el algoritmo de Good era equivalente al algoritmo de Cooley-Tukey, rápidamente se dio cuenta de que PFA es un algoritmo bastante diferente (funciona solo para tamaños que tienen factores primos relativamente y se basa en el Teorema chino del resto , a diferencia del soporte para cualquier tamaño compuesto en Cooley–Tukey). [6]
