Página principal › Índice multilingüe del archivo › Fourier rápido transforma

 Top 10 de los artículos YouTube Gmail Goole GayRomeo Números chinos Números romanos Orkut Costco Sistema porta hepático El mundo Factbook

News:

Fourier rápido transforma

A Fourier rápido transforma (FFT) es un eficiente algoritmo para computar Fourier discreto transforma (DFT) y su lo contrario. FFTs es de gran importancia a una variedad amplia de usos, de proceso de la señal numérica y el solucionar ecuaciones diferenciales parciales a los algoritmos para aprisa multiplicación de números enteros grandes. Este artículo describe los algoritmos, de los cuales hay muchos; vea Fourier discreto transforma para las características y los usos del transformar.

Dejado x₀, ...., x_N-1 sea números complejos. El DFT es definido por el fórmula

La evaluación de estas sumas tomaría directamente O (N ²) operaciones aritméticas. Un FFT es un algoritmo para computar el mismo resultado en solamente O (N registro N) operaciones. Tales algoritmos dependen generalmente de facturización de N, pero (contrario a la idea falsa popular) hay FFTs con O (N registro N) complejidad para todos N, iguale para prima N.

Muchos algoritmos de FFT dependen solamente del hecho eso es Nth raíz primitiva de la unidad, y puede ser aplicado así a análogo transforma sobre cualesquiera campo finito, por ejemplo número-teórico transforma.

Puesto que el DFT inverso es igual que el DFT, pero con la muestra opuesta en el exponente y un 1N el factor, cualquier algoritmo de FFT se puede adaptar fácilmente para él también.

Contenido 1 El algoritmo de Cooley-Tukey 2 Otros algoritmos de FFT 3 Los algoritmos de FFT se especializaron para los datos verdaderos y/o simétricos 4 Límites en cuentas de la complejidad y de la operación 5 Exactitud y aproximaciones 6 Algoritmos multidimensionales de FFT 7 Otras generalizaciones 8 Vea también 9 Referencias 10 Acoplamientos externos

El algoritmo de Cooley-Tukey

Artículo principal: Algoritmo de Cooley-Tukey FFT

En gran medida el FFT más común es Cooley-Tukey algoritmo. Ésta es a divida y conquiste el algoritmo eso recurrentemente analiza un DFT de cualesquiera compuesto tamaño N = N₁N₂ en muchos un DFTs más pequeño de tamaños N₁ y N₂, junto con O (N) multiplicaciones por el complejo raíces de la unidad, llamado tradicionalmente factores de la vuelta ligera (después de Gentleman y de Sande, 1966).

Este método (y la idea general de un FFT) fueron popularizados por una publicación de J. W. Cooley y J. W. Tukey en 1965, solamente fue descubierto más adelante que esos dos autores habían reinventado independientemente un algoritmo sabido a Gauss de Carl Friedrich alrededor 1805 (y vuelto a descubrir posteriormente varias veces en formas limitadas).

El uso más bien conocido del algoritmo de Cooley-Tukey es dividir el transformar en dos pedazos del tamaño N / 2 en cada paso, y por lo tanto se limita a energía-de-dos sizes, pero cualquier facturización puede ser utilizada en general (como era sabido al gauss y a Cooley/Tukey). Éstos se llaman radix-2 y mixed-radix casos, respectivamente (y otras variantes tales como partir-raíz FFT tenga sus propios nombres también). Aunque la idea básica es recurrente, la mayoría de las puestas en práctica tradicionales cambian el algoritmo para evitar la repetición explícita. También, porque el algoritmo de Cooley-Tukey rompe el DFT en un DFTs más pequeño, puede ser combinado arbitrariamente con cualquier otro algoritmo para el DFT, tal como ésos descritos más abajo.

Otros algoritmos de FFT

Artículos principales: Algoritmo del factor primario FFT, Algoritmo de FFT de Bruun, Algoritmo de FFT de Rader, y Algoritmo de FFT de Bluestein

Hay otros algoritmos de FFT distintos de Cooley-Tukey. Para N = N₁N₂ con coprimero N₁ y N₂, uno puede utilizar Factor primario Algoritmo (de Bueno-Thomas) (PFA), basado en Teorema chino del resto, para descomponer en factores el DFT semejantemente a Cooley-Tukey pero sin los factores de la vuelta ligera. El algoritmo de Rader-Brenner (1976) es a Cooley-Tukey-como la facturización pero con los factores puramente imaginarios de la vuelta ligera, reduciendo multiplicaciones en el coste de adiciones crecientes y de estabilidad numérica reducida; fue reemplazado más adelante por partir-raíz variante de Cooley-Tukey (que alcanza la misma cuenta de la multiplicación pero con pocas adiciones y sin sacrificar exactitud). Los algoritmos que descomponen en factores recurrentemente el DFT en operaciones más pequeñas con excepción de DFTs incluyen los algoritmos de Bruun y de QFT. (Los algoritmos de Rader-Brenner y de QFT fueron propuestos para energía-de-dos sizes, pero es posible que podrían ser adaptados al compuesto general n. El algoritmo de Bruun se aplica incluso a los tamaños compuestos arbitrarios.) Algoritmo de Bruun, particularmente, se basa en interpretar el FFT como facturización recurrente del polinómico z^N − 1, aquí en los polinomios del verdadero-coeficiente de la forma z^M − 1 y z^2M + az^M + 1.

Otro punto de vista polinómico es explotado por Winograd algoritmo, que descompone en factores z^N − 1 en polinomios cyclotomic- éstos tienen a menudo coeficientes de 1, de 0, o de −1, y por lo tanto requieren pocas (si cualquier) multiplicaciones, así que Winograd se puede utilizar para obtener la mínimo-multiplicación FFTs y es de uso frecuente encontrar los algoritmos eficientes para los factores pequeños. De hecho, Winograd demostró que el DFT se puede computar con solamente O(N) multiplicaciones irracionales, conduciendo a un límite más bajo realizable probado en el número de las multiplicaciones para energía-de-dos sizes; desafortunadamente, esto viene en el coste de muchas más adiciones, una compensación no más favorable en moderno procesadores con multiplicadores del hardware. Particularmente, Winograd también hace uso el PFA así como un algoritmo de Rader para FFTs de prima tamaños.

Algoritmo de Rader, explotando la existencia de a generador para el multiplicative grupo prima del modulo N, expresa un DFT del tamaño primero n como cíclico circunvolución del tamaño (del compuesto) N − 1, que se puede entonces computar por un par de FFTs ordinario vía teorema de la circunvolución (aunque Winograd utiliza otros métodos de la circunvolución). Otro primero-tamaño FFT es debido al L. I. Bluestein, y a veces se llama gojea-z el algoritmo; también re-expresa un DFT como circunvolución, pero este vez del iguales tamaño (que se puede cero-rellenar a a energía de dos y evaluado por radix-2 Cooley-Tukey FFTs, por ejemplo), vía la identidad nk = − (k − n)² / 2 + n² / 2 + k² / 2.

Los algoritmos de FFT se especializaron para los datos verdaderos y/o simétricos

En muchos usos, los datos de entrada para el DFT son puramente verdaderos, en este caso las salidas satisfacen la simetría

y los algoritmos eficientes de FFT se han diseñado para esta situación (véase e.g. Sorensen, 1987). Un acercamiento consiste en el tomar de un algoritmo del ordinario (e.g. Cooley-Tukey) y quitando las partes redundantes del cómputo, ahorrando áspero un factor de dos a tiempo y de la memoria. Alternativomente, es posible expresar uniforme- verdadero-entrada DFT de la longitud como DFT complejo de la mitad de la longitud (que piezas verdaderas e imaginarias son los elementos uniformes/impares de los datos verdaderos originales), seguido por O (N) operaciones del post-processing.

Fue creído una vez que la verdadero-entrada DFTs se podría computar más eficientemente por medio de Hartley discreto transforma (DHT), solamente él fue discutido posteriormente que un algoritmo especializado de la verdadero-entrada DFT (FFT) puede ser encontrado típicamente que requiere pocas operaciones que el algoritmo correspondiente de DHT (FHT) para el mismo número de entradas. El algoritmo de Bruun (arriba) es otro método que fue propuesto inicialmente para aprovecharse de entradas verdaderas, solamente él no ha probado popular.

Hay especializaciones más futuras de FFT para los casos de los datos verdaderos que tienen iguale/impar la simetría, en este caso una puede ganar otro factor de (áspero) dos a tiempo y memoria y el DFT se convierte en el coseno/el seno discretos transforma (DCT/DST). En vez directamente de modificar un algoritmo de FFT para estos casos, DCTs/DSTs se puede también computar vía FFTs de los datos verdaderos combinados con O (N) pre/proceso del poste.

Límites en cuentas de la complejidad y de la operación

Una cuestión fundamental del interés teórico de muchos años es probar límites más bajos en complejidad y las cuentas exactas de la operación de Fourier rápido transforman, y sigue habiendo muchos problemas abiertos. No es uniforme riguroso probado si DFTs requiere verdad Ω (NlogN) (es decir, orden NlogN o mayores) operaciones, igualan para el caso simple de energía de dos tamaños, aunque no se sabe ningunos algoritmos con una complejidad más baja. Particularmente, la cuenta de operaciones aritméticas es generalmente el foco de tales preguntas, aunque el funcionamiento real en las computadoras del moderno-día es determinado por muchos otros factores por ejemplo escondrijo o Tubería de la CPU optimización.

Siguiente iniciando el trabajo cerca Winograd (1978), un apretado Θ (N) un límite más bajo es sabido para número de las multiplicaciones verdaderas requeridas por un FFT. Puede ser demostrado que solamente las multiplicaciones verdaderas irracionales se requieren para computar un DFT de energía-de-dos length N = 2^m. Por otra parte, se saben los algoritmos explícitos que alcanzan esta cuenta (Heideman y Burrus, 1986; Duhamel, 1990). Desafortunadamente, estos algoritmos requieren demasiadas adiciones ser prácticas, por lo menos en las computadoras modernas con multiplicadores del hardware.

Un límite más bajo apretado es no sabido en el número de adiciones requeridas, aunque límites más bajos se han probado bajo algunas asunciones restrictivas en los algoritmos. En 1973, Morgenstern probó Ω (NlogN) un límite más bajo en la cuenta de la adición para los algoritmos donde las constantes multiplicative han limitado las magnitudes (que es verdad para la mayoría pero no todos los algoritmos de FFT). Pan (1986) probó Ω (NlogN) un límite más bajo si se asume que un límite en una medida del “asynchronicity” del algoritmo de FFT, pero la generalidad de esta asunción es confusos. Para el caso de energía-de-dos N, Papadimitriou (1979) discutió que el número Nregistro₂N de las adiciones del complejo-número alcanzadas por los algoritmos de Cooley-Tukey está óptimo bajo ciertas asunciones en gráfico del algoritmo (sus asunciones implican, entre otras cosas, que no se explota ningunas identidades aditivas en las raíces de la unidad). (Esta discusión implicaría eso por lo menos 2Nregistro₂N se requieren las adiciones verdaderas, aunque esto no es un límite apretado porque las adiciones adicionales se requieren como parte de multiplicaciones del complejo-número.) hasta el momento, ningún algoritmo publicado de FFT ha alcanzado menos que Nregistro₂N adiciones del complejo-número (o su equivalente) para energía-de-dos N.

Un tercer problema es reducir al mínimo total número de multiplicaciones y de adiciones verdaderas, a veces llamado la “complejidad aritmética” (aunque en este contexto es la cuenta exacta y no la complejidad asintótica se está considerando que). Una vez más no se ha probado ningún límite más bajo apretado. Desde 1968, sin embargo, la cuenta lo más bajo posible publicada para energía-de-dos N fue alcanzado de largo por algoritmo de la partir-raíz FFT, que requiere 4Nregistro₂N − 6N + 8 multiplicaciones y adiciones verdaderas para N > 1. Esto fue reducida recientemente a (Johnson y Frigo, 2007; Lundy y Van Buskirk, 2007).

La mayor parte de las tentativas de bajar o de probar la complejidad de los algoritmos de FFT se han centrado en el caso ordinario de los complejo-datos, porque es el más simple. Sin embargo, los complejo-datos FFTs se relacionan tan de cerca con los algoritmos para los problemas relacionados tales como verdadero-datos FFTs, el coseno discreto transforma, Hartley discreto transforma, y así sucesivamente, que cualquier mejora en uno de éstos conduciría inmediatamente a las mejoras en los otros (Duhamel y Vetterli, 1990).

Exactitud y aproximaciones

Todos los algoritmos de FFT discutidos hasta ahora computan el DFT exactamente (en aritmética exacta, es decir. el descuidar floating-point errores). Se han propuesto algunos algoritmos de “FFT”, sin embargo, que computan el DFT aproximadamente, con un error que se puede hacer arbitrariamente pequeño a expensas de cómputos crecientes. Tales algoritmos negocian el error de la aproximación para la velocidad creciente u otras características. Por ejemplo, un algoritmo aproximado de FFT de Edelman y otros. (1999) alcanza requisitos más bajos de la comunicación para el computar paralelo con la ayuda de a método de varios polos rápido. A cabrilla- FFT aproximado basado por 1996) entradas escasas de las tomas de Guo y de Burrus (/salidas (localización del tiempo/de la frecuencia) en consideración más eficientemente que posible con un FFT exacto. Otro algoritmo para el cómputo aproximado de un subconjunto de las salidas de DFT es debido a Shentov y otros. (1995). Solamente los trabajos del algoritmo de Edelman igualmente bien para los datos escasos y no-escasos, sin embargo, puesto que se basa en la compresibilidad (deficiencia espesa) de la matriz sí mismo de Fourier más bien que la compresibilidad (sparsity) de los datos.

Incluso los algoritmos “exactos” de FFT tienen errores cuando se utiliza la aritmética floating-point de la finito-precisión, pero estos errores son típicamente absolutamente pequeños; la mayoría de los algoritmos de FFT, e.g. Cooley-Tukey, tiene características numéricas excelentes. El límite superior en error relativo para Cooley-Tukey el algoritmo es O (registro del ε N), comparado a O (ε N^3/2) para el fórmula del naïve DFT (Gentleman y Sande, 1966), donde está la precisión el ε relativa floating-point de la máquina. De hecho, media cuadrada de la raíz los errores (rms) son mucho mejor que estos límites superiores, siendo solamente O (√log del ε N) para Cooley-Tukey y O (√ del εN) para el naïve DFT (Schatzman, 1996). Estos resultados, sin embargo, son muy sensibles a la exactitud de los factores de la vuelta ligera usados en el FFT (es decir. función trigonométrica los valores), y no es inusuales para que las puestas en práctica incautas de FFT tengan exactitud mucho peor, e.g. si utilizan inexacto repetición trigonometric fórmulas. Algún FFTs con excepción de Cooley-Tukey, tal como el algoritmo de Rader-Brenner, es intrínseco menos estable.

En aritmética de punto fijo, los errores de la finito-precisión acumulados por algoritmos de FFT son peores, con los errores del rms creciendo como O (√N) para el algoritmo de Cooley-Tukey (Welch, 1969). Por otra parte, incluso la realización de esta exactitud requiere la atención cuidadosa al escalamiento para reducir al mínimo la pérdida de precisión, y los algoritmos de punto fijo de FFT implican el rescaling en cada etapa intermedia de descomposiciones como Cooley-Tukey.

Para verificar la corrección de una puesta en práctica de FFT, las garantías rigurosas se pueden obtener en O (N registro N) el tiempo por un procedimiento simple que comprueba las linearidades, impulso-respuesta, y tiempo-cambia de puesto las características del transformar en las entradas al azar (Ergün, 1995).

Algoritmos multidimensionales de FFT

Según lo definido en DFT multidimensional artículo, el DFT multidimensional

transforma un arsenal con a d- dimensional vector de índices por un sistema de d adiciones jerarquizadas (encima para cada uno j), donde la división , definido como , es elemento-sabio realizada. Equivalente, es simplemente la composición de una secuencia de d sistemas de DFTs unidimensional, realizados a lo largo de una dimensión a la vez (en cualquier orden).

Este punto de vista compositivo proporciona inmediatamente el algoritmo multidimensional más simple y más común de DFT, conocido como fila-columna algoritmo (después del caso de dos dimensiones, abajo). Es decir, uno realiza simplemente una secuencia de d FFTs unidimensional (por un de los sobre algoritmos): primero usted transforma a lo largo de n₁ dimensión, entonces a lo largo del n₂ dimensión, y así sucesivamente (o realmente, el cualquier ordenar trabajará). Este método se demuestra fácilmente para tener el generalmente O(NregistroN) complejidad, donde es el número total de los puntos de referencias transformados. Particularmente, hay N / N₁ transforma de tamaño N₁, el etcetera, así que la complejidad de la secuencia de FFTs es:

En dos dimensiones, puede ser visto como matriz, y este algoritmo corresponde primero a realizar el FFT de todas las filas y entonces de todas las columnas (o viceversa), por lo tanto del nombre.

En más de dos dimensiones, es a menudo ventajoso para escondrijo lugar para agrupar las dimensiones recurrentemente. Por ejemplo, un FFT tridimensional pudo primero realizar FFTs de dos dimensiones de cada “rebanada planar” para cada uno fijada n₁, y entonces realice el FFTs unidimensional a lo largo del n₁ dirección. Más generalmente, asintótico óptimo escondrijo-olvidadizo el algoritmo consiste en recurrentemente el dividir de las dimensiones en dos grupos y eso se transforma recurrentemente (redondeando si d no es uniforme) (véase a Frigo y a Johnson, 2005). No obstante, ésta sigue siendo una variación directa del algoritmo de la fila-columna que requiere en última instancia solamente un algoritmo unidimensional de FFT como el caso bajo, y todavía tiene O(NregistroN) complejidad. Otra variación es realizar la matriz transposiciones entre transformar dimensiones subsecuentes, de modo que transforme funcione encendido los datos contiguos; esto es especialmente importante para hacia fuera-de-corazón y memoria distribuida situaciones donde están extremadamente desperdiciadores de tiempo los datos no-contiguos que tienen acceso.

Hay otros algoritmos multidimensionales de FFT que son distintos del algoritmo de la fila-columna, aunque todos tienen O(NregistroN) complejidad. Quizás la no-fila-columna más simple FFT es el algoritmo de la vector-raíz FFT, que es una generalización del algoritmo ordinario de Cooley-Tukey donde uno divide las dimensiones del transformar por un vector de raíces en cada paso. (Esto puede también tener ventajas del escondrijo.) el caso más simple de la vector-raíz es donde están igual todas las raíces (e.g. vector-radix-2 se divide todos de las dimensiones por dos), sino de ésta no es necesario. Vector la raíz con solamente una sola raíz de la no-unidad a la vez, es decir. , está esencialmente un algoritmo de la fila-columna. Otro, complicado, los métodos incluye polinomio transforma los algoritmos debido a Nussbaumer (1977), que ven el transformar en términos de circunvoluciones y productos polinómicos. Vea a Duhamel y a Vetterli (1990) para más información y referencias.

Otras generalizaciones

O(N^5/2 registro N) generalización a armónicos esféricos en la esfera S² con N² los nodos fueron descritos por Mohlenkamp (1999), junto con un algoritmo conjeturado (pero no probado) para tener O(N² registro² N) complejidad; Mohlenkamp también proporciona una puesta en práctica en biblioteca del libftsh. Un algoritmo esférico-armónico con O(N² registro N) la complejidad es descrita por Rokhlin y Tygert (2006).

Los varios grupos también han publicado los algoritmos de “FFT” para non-equispaced datos, según lo repasado en Potts y otros. (2001). Tales algoritmos no computan terminantemente el DFT (para el cual se define solamente equispaced datos), solamente una algo cierta aproximación de eso (a non-equispaced Fourier discreto transforma, o NDFT, que sí mismo se computa a menudo solamente aproximadamente).

Vea también

• Algoritmo de Cooley-Tukey FFT
• algoritmo de la Partir-raíz FFT
• Algoritmo del factor primario FFT
• Algoritmo de FFT de Bruun
• Algoritmo de FFT de Rader
• Algoritmo de FFT de Bluestein
• Diagrama de la mariposa - un diagrama describía FFTs.
• Traslapar-agregue - un método eficiente de la circunvolución usando FFT para las señales largas
• Música espectral (implica el uso del análisis de FFT a la composición musical)
• Analizadores de espectro - Dispositivos que realizan un FFT
• FFTW El “Fourier más rápido transforma en el oeste” - la biblioteca de “C” para el Fourier discreto transforma (DFT) en unas o más dimensiones.

Referencias

• N. Brenner y C. Rader, 1976, Un nuevo principio para la transformación rápida de Fourier, Acústica de IEEE, discurso y proceso de señal 24: 264-266.
• Cooley, James W., y Juan W. Tukey, 1965, “un algoritmo para el cálculo de la máquina de la serie de Fourier Compleja,” Matemáticas. Comput. 19: 297–301.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein, 2001. Introducción a los algoritmos, 2do. ed. Prensa y McGraw-Colina del MIT. ISBN 0-262-03293-7. Especialmente capítulo 30, “polinomios y los FFT.”
• Pierre Duhamel, 1990, Algoritmos que satisfacen los límites más bajos en la complejidad multiplicative de la longitud2ⁿ DFTs y su conexión con algoritmos prácticos , Transporte de IEEE. Acoust. Discurso. Sig. Proc. 38: 1504-151.
• ------- y M. Vetterli, 1990, Fourier rápido transforma: una revisión preceptoral y un estado plus ultra , Proceso de señal 19: 259–299.
• A. Edelman, P. McCorquodale, y S. Toledo, 1999, ¿El Fourier rápido futuro transforma? , TAILANDIA J. Sci. El computar 20: 1094-1114.
• Funda Ergün, 1995, Funciones lineares multivariate de prueba: Superación del embotellamiento del generador , Proc. 27mo Simposio de ACM sobre la teoría de computar: 407–416.
• M. Frigo y S. G. Johnson, 2005, “El diseño y la puesta en práctica de FFTW3," Procedimientos del IEEE 93: 216–231.
• Gauss de Carl Friedrich, 1866. “Nachlass: Tractata de la Nova del methodo de los interpolationis de Theoria, “ Werke venda 3, 265-327. Göttingen: Der Wissenschaften del Gesellschaft de Königliche.
• W. M. Caballero y G. Sande, 1966, “Fourier rápido transformar-para la diversión y el beneficio,” Proc. AFIPS 29: 563–578.
• H. Guo y C. S. Burrus, 1996, Fourier aproximado rápido transforma vía cabrillas transforma , Proc. SPIE Intl. Soc. OPT. Inglés. 2825: 250–259.
• ------- y G. A. Sitton, 1994, El Fourier discreto rápido transforma , Proc. IEEE Conf. Acoust. Discurso y Sig. Proceso (ICASSP) 3: 445–448.
• Michael T. Heideman y C. Sidney Burrus, 1986, En el número de las multiplicaciones necesarias para computar una longitud2ⁿ DFT, Transporte de IEEE. Acoust. Discurso. Sig. Proc. 34: 91-95.
• -------- y D. H. Johnson, 1984, El gauss y la historia del Fourier rápido transforman, Compartimiento de IEEE ASSP 1: 14–21.
• S. G. Johnson y M. Frigo, 2007. "Una partir-raíz modificada FFT con pocas operaciones aritméticas," Transporte de IEEE. Proceso de señal 55 (1): 111–119.
• T. Lundy y J. Van Buskirk, 2007. “Un nuevo acercamiento de la matriz a FFTs verdadero y circunvoluciones de la longitud 2^k," El computar 80 (1): 23-45.
• Jacques Morgenstern, 1973, La nota sobre un límite más bajo de la complejidad linear del Fourier rápido transforma , J. ACM 20: 305-306.
• M. J. Mohlenkamp, 1999, “un rápido transforma para los armónicos esféricos”, J. Fourier anal. Appl. 5, 159-184. (preprint)
• H. J. Nussbaumer, 1977, Digital que se filtra con polinomio transforma , Electrónica Lett. 13: 386-387.
• V. Pan, 1986, La compensación entre la complejidad aditiva y el asyncronicity de algoritmos lineares y bilinearios , Información Proc. Lett. 22: 11-14.
• Christos H. Papadimitriou, 1979, El Optimality del Fourier rápido transforma , J. ACM 26: 95-102.
• D. Potts, G. Steidl, y M. Tasche, 2001. "Fourier rápido transforma para nonequispaced datos: Una clase particular“, en: J.J. Benedetto y P. Ferreira (Eds.), Teoría moderna del muestreo: Matemáticas y usos (Birkhauser).
• Vladimir Rokhlin y marca Tygert, 2006, “Algoritmos rápidos para las extensiones armónicas esféricas," TAILANDIA J. Sci. El computar 27 (6): 1903-1928.
• James C. Schatzman, 1996, La exactitud del Fourier discreto transforma y el Fourier rápido transforma, TAILANDIA J. Sci. Comput. 17: 1150-1166.
• O. V. Shentov, S. K. Mitra, U. Heute, y A. N. Hossen, 1995, Subband DFT. I. Definición, interpretaciones y extensiones , Proceso de señal 41: 261–277.
• H. V. Sorensen, D. L. Jones, M. T. Heideman, y C. S. Burrus, 1987, Fourier rápido Real-valued transforma algoritmos, Transporte de IEEE. Acoust. Sig del discurso. Proceso ASSP-35: 849–863. Vea también Las correcciones “Fourier rápido Real-valued transforman algoritmos”
• Peter D. Welch, 1969, Un Fourier rápido de punto fijo transforma análisis del error, Transporte de IEEE. Electroacoustics audio 17: 151–157.
• S. Winograd, 1978, En computar el Fourier discreto transforme, Matemáticas. Cómputo 32: 175-199.

Acoplamientos externos

• Acoplamientos al código y a la información de FFT en línea.
• Documentación, acoplamientos, libro, y código en línea.
• Software de uso paralelo en las computadoras del alto rendimiento. Rutinas seriales y paralelas de FFT.
• Sri Welaratna, “30 años de analizadores de FFT", Sonido y vibración (Enero de 1997, trigésima edición del aniversario). Una revisión histórica de los dispositivos del hardware FFT.