COOLEY-TUKEY

ALGORITMO FFT COOLEY-TUKEY

El algoritmo de Cooley-Tukey, el nombre de J.W. Cooley y John Tukey, es el rápido algoritmo de transformada de Fourier más común. Se re-expresa la transformada discreta de Fourier de un tamaño arbitrario compuesto N = n1n2 en términos de DFT más pequeñas de tamaños N1 y N2, de forma recursiva, con el fin de reducir el tiempo de cálculo a O para altamente compuesto N. Debido a la importancia del algoritmo, variantes específicas y estilos de ejecución han dado a conocer por sus propios nombres, como se describe a continuación.

Debido a que el algoritmo de Cooley-Tukey rompe 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 de se puede utilizar para manejar grandes factores primos que no pueden ser descompuestos por Cooley-Tukey, o el algoritmo de máxima audiencia factor puede ser aprovechada para una mayor eficiencia en la separación de los factores primos.

Ver también la transformada rápida de Fourier para obtener información sobre otros algoritmos FFT, especializaciones para los datos reales y/o simétrica, y la precisión en la cara de punto flotante de precisión finita.

HISTORIA

Este algoritmo, incluyendo su aplicación recursiva, fue inventado alrededor de 1805 por Carl Friedrich Gauss, que lo utilizó para interpolar las trayectorias de los asteroides Pallas y Juno, pero su trabajo no fue ampliamente reconocido. Gauss no analizó el tiempo de cálculo asintótica, sin embargo. Diversas formas limitadas también fueron descubiertas varias veces a lo largo de los siglos 19 y 20. FFT se hizo popular después de que James Cooley de IBM y John Tukey de Princeton publicó un artículo en 1965 reinventando el algoritmo y la descripción de cómo llevar a cabo convenientemente en un ordenador.

Tukey al parecer se le ocurrió la idea durante una reunión de un comité asesor presidencial de EE.UU. discutir maneras de detectar ensayos de armas nucleares en la Unión Soviética. Otro de los participantes en esa reunión, Richard Garwin de IBM, reconoció el potencial del método Tukey y poner en contacto con Cooley, quien implementó un problema diferente: el análisis de los datos cristalográficos 3d. Cooley y Tukey posteriormente publicaron su documento conjunto, y la adopción a gran siguieron rápidamente.

El hecho de que Gauss había descrito el mismo algoritmo no se realizó sino hasta varios años después de papel Cooley y Tukey 1965. Su artículo citado como inspiración única obra de IJ buena en lo que ahora se llama el algoritmo FFT primer factor; algoritmo aunque de buen principio se pensó equivocadamente que es equivalente al algoritmo de Cooley-Tukey, se dio cuenta rápidamente de que PFA es un algoritmo muy diferente .

FACTORIZACIONES GENERALES

Más en general, los algoritmos de Cooley-Tukey recursiva re-expresan una DFT de un tamaño compuesto N = n1n2 como:

Realizar DFTs N1 N2 tamaño.

Multiplique por las raíces complejas de la unidad llamados factores de rotación.

Realizar DFTs N2 de tamaño N1.

Por lo general, ya sea N1 o N2 es un pequeño factor, llamado el radix. Si N1 es la raíz, que se llama un algoritmo de decimación en el tiempo, mientras que si N2 es la raíz, es decimación en frecuencia. La versión anterior fue presentado un algoritmo radix-2 DIT, en la expresión final, la fase de multiplicación de la transformación extraña es el factor twiddle y el +/- combinación de las transformaciones pares e impares es una talla 2 DFT.

Hay muchas otras variaciones en el algoritmo de Cooley-Tukey. Mezclado-radix implementaciones de identificadores tamaños compuestos con una variedad de factores, además de a dos, por lo general empleando el algoritmo de O para los casos base primos de la recursión. Dividir radix se funde radices 2 y 4, explotando el hecho de que la primera transformada de base 2 no requiere ningún factor de vuelta ligera, con el fin de lograr lo que fue durante mucho tiempo el recuento de operación aritmética conocido bajo para poder de dos tamaños, aunque las variaciones recientes lograr un recuento aún más baja . Otra manera de mirar el algoritmo de Cooley-Tukey es que se re-expresa un tamaño N DFT unidimensional como por N1 N2 DFT de dos dimensiones, donde se transpone la matriz de salida. El resultado neto de todas estas transposiciones, para un algoritmo de radix-2, corresponde a una inversión de bit de la entrada o salida de índices. Si, en lugar de utilizar una pequeña radix, uno emplea una base de más o menos vN y de entrada/salida de transposiciones matriz explícita, se llama un algoritmo de cuatro pasos, propuesto inicialmente para mejorar la localidad de memoria, por ejemplo, para la optimización de caché o fuera de servicio de núcleo, y más tarde se demostró que un algoritmo de caché-ajeno óptima.

El Cooley-Tukey factorización en general vuelve a escribir el índices k y n como y, respectivamente, donde los índices de ka y na van desde 0 .. Na-1. Es decir, que volvió a los índices de entrada y salida como N1 N2 por matrices bidimensionales en orden de columna-principal y de las filas, respectivamente, la diferencia entre estas indexaciones es una transposición, como se mencionó anteriormente. Cuando re-indexación se sustituye en la fórmula DFT para nk, el término cruzada desaparece, y los términos restantes dan

donde cada suma interna es una DFT de N2 tamaño, cada suma exterior es una DFT de tamaño N1, y el término entre corchetes es el factor de vuelta ligera.

Un radix arbitraria r se puede emplear, como se ha demostrado por tanto Cooley y Tukey, así como de Gauss. Cooley y Tukey asumieron inicialmente que la raíz de la mariposa requiere O el trabajo y por lo tanto, calcula la complejidad de una raíz r que O = O, desde el cálculo de los valores de r/log2r para valores enteros de r 2-12 la óptima base se encuentra a ser 3. Este análisis era errónea, sin embargo: la radix-mariposa es también una DFT y se puede realizar a través de un algoritmo de FFT en las operaciones de O, por lo tanto, la raíz r cancela realmente en la complejidad O, y la r óptima se determina por consideraciones más complicados. En la práctica, bastante grande r son importantes con el fin de explotar eficazmente por ejemplo, el gran número de registros del procesador en los procesadores modernos, e incluso una ilimitada radix r = vN también logra complejidad O y tiene ventajas teóricas y prácticas para grandes N como se mencionó anteriormente.