Algoritmo de Cooley y 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 .
El caso radix-2 DIT
Un radix-2 de diezmado en tiempo FFT es la forma más simple y más común del algoritmo de Cooley-Tukey, aunque las implementaciones de Cooley-Tukey altamente optimizados suelen utilizar otras formas del algoritmo como se describe a continuación. Radix-2 DIT se divide una DFT de tamaño N en dos DFT intercalados de tamaño N/2 en cada etapa recursiva.
La transformada discreta de Fourier se define por la fórmula:
donde es un número entero de al.
Radix-2 DIT primero calcula la DFT de las entradas incluso indexados y de las entradas indexados impares, y luego combina estos dos resultados para producir la DFT de toda la secuencia. Esta idea, entonces se puede realizar de forma recursiva para reducir el tiempo de ejecución global a O. Esta forma simplificada supone que N es una potencia de dos, ya que el número de puntos de muestra N por lo general puede ser elegido libremente por la aplicación, esto a menudo no es una restricción importante .
El algoritmo Radix-2 DIT reorganiza la DFT de la función en dos partes: una suma sobre los índices de número par y una suma en los índices impares:
Uno puede factorizar un multiplicador común a partir de la segunda suma, como se muestra en la siguiente ecuación. A continuación, es claro que las dos sumas son la DFT de la parte par-indexado y la DFT de la parte impar-indexada de la función. Denotan la DFT de las entradas Aún indexados y por la DFT de las entradas Odd indexados por y obtenemos:
Sin embargo, estos DFTs más pequeños tienen una longitud de N/2, por lo que sólo necesita calcular N/2 salidas: gracias a las propiedades de la periodicidad de la DFT, las salidas para ![]()
Pseudocódigo
En pseudocódigo, el proceso anterior se puede escribir:
X0, ..., N-1? ditfft2: DFT de: si N = 1 entonces X0? x0 size-1 trivial DFT caso base más X0, ..., N/2-1? ditfft2 DFT de XN/2, ..., N-1? ditfft2 DFT por k = 0 a N/2-1 combinan DFT de dos mitades en plena DFT: t? Xk Xk? t + exp Xk + N/2 Xk + N/2? t - exp Xk + N/2 endfor endif
Aquí, ditfft2, calcula X = DFT fuera de lugar por un FFT radix-2 DIT, donde N es una potencia entera de 2 y s = 1 es el paso de la matriz de entrada x. x + s denota la matriz a partir de xs.
Implementaciones FFT alto rendimiento hacen muchas modificaciones a la aplicación de un algoritmo de tal comparación con este sencillo pseudocódigo. Por ejemplo, se puede utilizar un caso base mayor que N = 1 para amortizar los gastos generales de la recursión, los factores de rotación pueden calcularse previamente, y radices más grandes se utilizan a menudo por razones de caché; estas y otras optimizaciones juntos pueden mejorar el rendimiento en un orden de magnitud o más. Varias de estas ideas se describen en más detalle a continuación.
Factorizaciones Generales
Más en general, los algoritmos de Cooley-Tukey recursiva re-expresan una DFT de un tamaño compuesto N = n1n2 como:
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.
Reordenación de los datos, inversión de poco, y en el lugar algoritmos
Aunque el resumen de Cooley-Tukey factorización de la DFT, anteriormente, se aplica en alguna forma a todas las implementaciones del algoritmo, existe una diversidad mucho mayor en las técnicas para ordenar y acceder a los datos en cada etapa de la FFT. De especial interés es el problema de la elaboración de un algoritmo en el lugar que sobrescribe la entrada con sus datos de salida utilizando sólo el almacenamiento auxiliar O.
La técnica más conocida reordenación implica inversión de poco explícito en el lugar radix-2 algoritmos. Reversión es la permutación de bits, donde los datos en un índice n, escrito en binario con los dígitos b4b3b2b1b0, se transfieren al índice con los dígitos invertidos b0b1b2b3b4. Tenga en cuenta la última etapa de un algoritmo de radix-2 DIT como el presentado anteriormente, en donde la salida está escrito en el lugar sobre la entrada: y cuando se combinan con un tamaño de 2-DFT, esos dos valores son sobrescritos por las salidas. Sin embargo, los dos valores de salida deben ir en la primera y segunda mitades de la matriz de salida, correspondiente al bit más significativo b4, mientras que las dos entradas y se intercalan en los pares e impares elementos, correspondientes al bit menos significativo b0. Por lo tanto, con el fin de obtener la salida en el lugar correcto, estos dos bits deben ser intercambiados. Si se incluyen todas las etapas recursivas de un algoritmo radix-2 DIT, todos los bits deben ser cambiados y por lo tanto uno debe pre-procesar la entrada con una inversión de poco para la salida en orden. De la misma manera, si lleva a cabo todos los pasos en orden inverso, se obtiene un algoritmo radix-2 DIF con inversión de poco en el post-procesamiento. Alternativamente, algunas aplicaciones funcionan igual de bien en los datos de bits invertidos, por lo que uno puede realizar hacia adelante transformaciones, procesamiento y luego inversos transforma todo sin reversión bits para producir los resultados finales en el orden natural.
Muchos usuarios de FFT, sin embargo, prefieren salidas de orden natural, y una etapa de bits reversión separada, explícita pueden tener un impacto no despreciable en el tiempo de cálculo, a pesar de reversión poco se puede hacer en tiempo O y ha sido el objeto de mucha investigación. También, mientras que la permutación es una inversión de bits en el caso radix-2, que es más general, una inversión de dígitos arbitrario para el caso mixto-radix, y los algoritmos de permutación ser más complicado de implementar. Por otra parte, es deseable en muchas arquitecturas de hardware para volver a ordenar las etapas intermedias de la algoritmo de FFT para que operen en los elementos de datos consecutivos. Con este fin, una serie de planes de ejecución alternativos se han ideado para el algoritmo de Cooley-Tukey que no requieren inversión de bits independiente y/o que involucren permutaciones adicionales en fases intermedias.
El problema se simplifica en gran medida si está fuera de lugar: la matriz de salida es distinta de la matriz de entrada o, de manera equivalente, una matriz auxiliar de igual tamaño está disponible. El algoritmo de clasificación automática Stockham realiza todas las etapas de la FFT fuera de lugar, por lo general por escrito de ida y vuelta entre dos matrices, la transposición de un "número" de los índices con cada etapa, y ha sido especialmente popular en arquitecturas SIMD. Se han propuesto aún mayores potenciales ventajas SIMD para el algoritmo de Pease, que también reordena fuera de lugar con cada etapa, pero este método requiere poco separada/reversión dígitos y S de almacenamiento. También se puede aplicar directamente la definición de factorización Cooley-Tukey con recursión explícita y pequeñas radices, que produce-orden natural fuera de su lugar de salida sin paso permutación separado y se puede argumentar que tiene beneficios localidad-ajenos caché en sistemas con memoria jerárquica.
Una estrategia típica para en el lugar algoritmos sin almacenamiento auxiliar y sin pases de inversión de dígitos aislados ocasiona pequeñas transposiciones de la matriz en una fase intermedia, que se pueden combinar con las mariposas radix para reducir el número de pasadas sobre los datos.
No hay comentarios:
Publicar un comentario