transformada rápida de Fourier

La transformada rápida de Fourier ( FFT ) es un algoritmo que calcula la transformada discreta de Fourier (DFT) o su inversa (IDFT) de una secuencia . Una transformada de Fourier convierte una señal de su dominio original (generalmente el tiempo o el 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 dichas transformaciones factorizando la matriz DFT en un producto de factores dispersos (en su mayoría cero). ^{[ 2 ]} Como resultado, logra reducir la complejidad del cálculo de la DFT.${\textstyle O(n^{2})}$, que surge si simplemente se aplica la definición de DFT a${\textstyle O(n\log n)}$donde n es la longitud de la secuencia. La diferencia de velocidad puede ser enorme, especialmente para secuencias largas donde n puede ser de miles o millones.

Como la FFT es simplemente una refactorización algebraica de términos dentro de la DFT, tanto la DFT como la FFT realizan operaciones matemáticamente equivalentes e intercambiables, suponiendo que todos los términos se calculan con precisión infinita. Sin embargo, en presencia de errores de redondeo , muchos algoritmos de FFT son mucho más precisos que evaluar la definición de DFT directa o indirectamente. Existen muchos algoritmos de 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 y la teoría de números . Los algoritmos de FFT más conocidos dependen de la factorización de n , pero existen FFT con${\displaystyle O(n\log n)}$complejidad para todos los n , incluidos los valores primos . Muchos algoritmos FFT dependen únicamente del hecho de que${\textstyle e^{-2\pi i/n}}$es una raíz primitiva n- ésima de la unidad y, por lo tanto, puede aplicarse a transformaciones análogas sobre cualquier campo finito , como las transformaciones de la teoría 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 de 1/ n , cualquier algoritmo FFT puede adaptarse fácilmente para ella.

Las transformadas rápidas de Fourier se utilizan ampliamente en aplicaciones de ingeniería, música, ciencia 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 época", ^{[ 3 ] [ 4 ]} y fue incluida en los 10 mejores algoritmos del siglo XX por la revista IEEE Computing in Science & Engineering . ^{[ 5 ]}

El desarrollo de algoritmos rápidos para la DFT se vislumbró en el trabajo inédito de Carl Friedrich Gauss de 1805 sobre las órbitas de los asteroides Pallas y Juno . Gauss quería interpolar las órbitas a partir de observaciones de muestra; ^{[ 6 ] [ 7 ]} su método era muy similar al que publicarían en 1965 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 precedió incluso a los resultados de Joseph Fourier de 1822, no analizó la complejidad del método y, finalmente, utilizó otros métodos para lograr el mismo fin.

Entre 1805 y 1965, otros autores publicaron algunas versiones de la FFT. Frank Yates publicó en 1932 su versión llamada algoritmo de interacción , que proporcionaba un cálculo eficiente de las transformadas de Hadamard y Walsh . ^{[ 8 ]} El algoritmo de Yates todavía se utiliza en el campo del diseño estadístico y el análisis de experimentos. En 1942, GC Danielson y Cornelius Lanczos publicaron su versión para calcular la DFT para la cristalografía de rayos X , un campo donde el cálculo de las transformadas de Fourier presentaba un formidable cuello de botella. ^{[ 9 ] [ 10 ]} Si bien muchos métodos en el pasado se habían centrado en reducir el factor constante para${\textstyle O(n^{2})}$mediante el cálculo aprovechando las simetrías, Danielson y Lanczos se dieron cuenta de que se podía usar la periodicidad y aplicar un truco de duplicación para "duplicar [ n ] con solo un poco más del doble de trabajo", aunque al igual que Gauss no hicieron el análisis para descubrir que esto conducía a${\textstyle O(n\log n)}$escalado. ^{[ 11 ]} En 1958, IJ Good publicó un artículo que establecía el algoritmo FFT de factor primo que se aplica a transformadas de Fourier discretas de tamaño${\textstyle n=n_{1}n_{2}}$, dónde${\displaystyle n_{1}}$y${\displaystyle n_{2}}$son coprimos. ^{[ 12 ]}

James Cooley y John Tukey redescubrieron independientemente estos algoritmos anteriores ^{[ 7 ]} y publicaron una FFT más general en 1965 que es aplicable cuando n es compuesto y no necesariamente una potencia de 2, además de analizar la${\textstyle O(n\log n)}$escalamiento. ^{[ 13 ]} Tukey concibió la idea durante una reunión del Comité Asesor Científico del Presidente Kennedy , donde un tema de discusión fue la detección de pruebas nucleares de la Unión Soviética mediante la instalación de sensores para rodear el país desde el exterior. Para analizar la salida de estos sensores, se necesitaría un algoritmo FFT. En una conversación con Tukey, Richard Garwin reconoció la aplicabilidad general del algoritmo no solo a problemas de seguridad nacional, sino también a una amplia gama de problemas, incluyendo uno de interés inmediato para él: determinar las periodicidades de las orientaciones de espín en un cristal 3D de Helio-3. ^{[ 14 ]} Garwin le dio la idea de Tukey a Cooley (ambos trabajaban en los laboratorios Watson de IBM ) para su implementación. ^{[ 15 ]} Cooley y Tukey publicaron el artículo en un tiempo relativamente corto de seis meses. ^{[ 16 ]} Como Tukey no trabajaba en IBM, se dudó de la patentabilidad de la idea y el algoritmo pasó a ser de dominio público, lo que, a través de la revolución informática de la década siguiente, convirtió a la FFT en uno de los algoritmos indispensables en el procesamiento de señales digitales .

Dejar${\displaystyle x_{0},\ldots ,x_{n-1}}$sean números complejos . La DFT se define mediante la fórmula

${\displaystyle X_{k}=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi km/n}\qquad k=0,\ldots ,n-1,}$

dónde${\displaystyle e^{i2\pi /n}}$es una raíz n- ésima primitiva de 1.

Evaluar esta definición directamente requiere${\textstyle O(n^{2})}$operaciones: hay n salidas X _k , y cada salida requiere una suma de n términos. Una FFT es cualquier método para calcular los mismos resultados en${\textstyle O(n\log n)}$operaciones. Todos los algoritmos FFT conocidos requieren${\textstyle O(n\log n)}$operaciones, aunque no existe prueba conocida de que una menor complejidad sea imposible. ^{[ 17 ]}

Para ilustrar el ahorro de una FFT, considere el recuento de multiplicaciones y sumas complejas para${\textstyle n=4096}$puntos de datos. Evaluar las sumas de la DFT directamente implica${\textstyle n^{2}}$multiplicaciones complejas y${\textstyle n(n-1)}$adiciones complejas, de las cuales${\textstyle O(n)}$Se pueden ahorrar operaciones eliminando operaciones triviales como las multiplicaciones por 1, dejando aproximadamente 30 millones de operaciones. En contraste, el algoritmo Cooley-Tukey de base 2 , para n una potencia de 2, puede calcular el mismo resultado con solo${\textstyle (n/2)\log _ {2}(n)}$multiplicaciones complejas (de nuevo, ignorando las simplificaciones de multiplicaciones por 1 y similares) y${\textstyle n\log _{2}(n)}$sumas complejas, en total unas 70.000 operaciones, más de cuatrocientas veces menos que con la evaluación directa. En la práctica, el rendimiento real en las computadoras modernas suele estar dominado por factores distintos a la velocidad de las operaciones aritméticas y el análisis es un tema complicado (por ejemplo, véase Frigo y Johnson , 2005), ^{[ 18 ]} pero la mejora general de${\textstyle O(n^{2})}$a${\textstyle O(n\log n)}$restos.

En muchas aplicaciones, los datos de entrada para la DFT son puramente reales, en cuyo caso las salidas satisfacen la simetría.

${\displaystyle X_{nk}=X_{k}^{*}}$

y se han diseñado algoritmos FFT eficientes para esta situación (véase, por ejemplo, Sorensen, 1987). ^{[ 27 ] [ 28 ]} Un enfoque consiste en tomar un algoritmo ordinario (por ejemplo, Cooley-Tukey) y eliminar las partes redundantes del cálculo, ahorrando aproximadamente un factor de dos en tiempo y memoria. Alternativamente, es posible expresar una DFT de entrada real de longitud par como una DFT compleja de la mitad de la longitud (cuyas partes real e imaginaria son los elementos pares/impares de los datos reales originales), seguida de${\displaystyle O(n)}$operaciones de postprocesamiento.

Antes se creía que las DFT de entrada real podían calcularse de forma más eficiente mediante la transformada discreta de Hartley (DHT), pero posteriormente se argumentó que normalmente se puede encontrar un algoritmo de DFT de entrada real especializado (FFT) que requiere menos operaciones que el algoritmo DHT correspondiente (FHT) para el mismo número de entradas. ^{[ 27 ]} El algoritmo de Bruun (arriba) es otro método que se propuso inicialmente para aprovechar las entradas reales, pero no ha tenido éxito.

Existen especializaciones adicionales de FFT para los casos de datos reales que tienen simetría par/impar , en cuyo caso se puede ganar otro factor de aproximadamente dos en tiempo y memoria y la DFT se convierte en la (s) transformada(s) discreta(s) de coseno / seno ( DCT / DST ). En lugar de modificar directamente un algoritmo FFT para estos casos, las DCT/DST también se pueden calcular a través de FFT de datos reales combinados con${\displaystyle O(n)}$preprocesamiento y postprocesamiento.

Tal como se define en el artículo DFT multidimensional , la DFT multidimensional

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }}$

transforma una matriz x _n con un vector de índices de dimensión d${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$mediante un conjunto de d sumas anidadas (sobre${\textstyle n_{j}=0\ldots N_{j}-1}$para cada j ), donde la división${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots,n_{d}/N_{d}\right)}$se realiza elemento a elemento. De forma equivalente, es la composición de una secuencia de d conjuntos de DFT unidimensionales, realizadas a lo largo de una dimensión a la vez (en cualquier orden).

Este punto de vista compositivo proporciona inmediatamente el algoritmo DFT multidimensional más simple y común, conocido como algoritmo de filas y columnas (después del caso bidimensional, más adelante). Es decir, simplemente se realiza una secuencia de d FFT unidimensionales (mediante cualquiera de los algoritmos anteriores): primero se transforma a lo largo de la dimensión n ₁ , luego a lo largo de la dimensión n ₂ , y así sucesivamente (de hecho, cualquier orden funciona). Se demuestra fácilmente que este método tiene la siguiente estructura habitual.${\textstyle O(n\log n)}$complejidad, donde${\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}$es el número total de puntos de datos transformados. En particular, hay n / n ₁ transformaciones de tamaño n ₁ , etc., por lo que la complejidad de la secuencia de FFT es:

${\displaystyle {\begin{aligned}&{\frac {n}{n_{1}}}O(n_{1}\log n_{1})+\cdots +{\frac {n}{n_{d}}}O(n_{d}\log n_{d})\\[6pt]={}&O\left(n\left[\log n_{1}+\cdots +\log n_{d}\right]\right)=O(n\log n).\end{aligned}}}$

En dos dimensiones, el x _k puede verse como un${\displaystyle n_{1}\times n_{2}}$matriz , y este algoritmo corresponde a realizar primero la FFT de todas las filas (respectivamente, columnas), agrupando las filas (respectivamente, columnas) transformadas resultantes juntas como otra${\displaystyle n_{1}\times n_{2}}$matriz, y luego realizar la FFT en cada una de las columnas (respectivamente, filas) de esta segunda matriz, y de manera similar agrupar los resultados en la matriz de resultados final.

En más de dos dimensiones, a menudo resulta ventajoso para la localidad de caché agrupar las dimensiones recursivamente. Por ejemplo, una FFT tridimensional podría realizar primero FFT bidimensionales de cada segmento planar para cada n ₁ fijo , y luego realizar FFT unidimensionales a lo largo de la dirección n _1. De forma más general, un algoritmo asintóticamente óptimo que ignora la caché consiste en dividir recursivamente las dimensiones en dos grupos.${\textstyle (n_{1},\ldots ,n_{d/2})}$y${\textstyle (n_{d/2+1},\ldots ,n_{d})}$que se transforman recursivamente (redondeo si d no es par) (véase Frigo y Johnson, 2005). ^{[ 18 ]} Aun así, esta sigue siendo una variación directa del algoritmo de filas y columnas que en última instancia solo requiere un algoritmo FFT unidimensional como caso base, y todavía tiene${\displaystyle O(n\log n)}$complejidad. Otra variante consiste en realizar transposiciones de matrices entre transformaciones de dimensiones sucesivas, de modo que las transformaciones operen sobre datos contiguos; esto es especialmente importante para situaciones de memoria fuera de memoria principal y memoria distribuida , donde el acceso a datos no contiguos consume muchísimo tiempo.

Existen otros algoritmos FFT multidimensionales que son distintos del algoritmo de filas y columnas, aunque todos ellos tienen${\textstyle O(n\log n)}$complejidad. Quizás el algoritmo FFT no basado en filas y columnas más simple sea el algoritmo FFT de base vectorial , que es una generalización del algoritmo Cooley-Tukey ordinario donde se dividen las dimensiones de la transformada por un vector.${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$de radices en cada paso. (Esto también puede tener beneficios de caché). El caso más simple de vector-radix es cuando todas las radices son iguales (por ejemplo, vector-radix-2 divide todas las dimensiones por dos), pero esto no es necesario. Vector radix con una sola radix no unitaria a la vez, es decir${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$Esencialmente, se trata de un algoritmo de filas y columnas. Otros métodos más complejos incluyen algoritmos de transformación polinómica, propuestos por Nussbaumer (1977) ^{[ 44 ]} , que consideran la transformación en términos de convoluciones y productos polinómicos. Para más información y referencias, consulte Duhamel y Vetterli (1990) ^{[ 36 ]} .

Un${\textstyle O(n^{5/2}\log n)}$La generalización a armónicos esféricos en la esfera S ² con n ² nodos fue descrita por Mohlenkamp, ^{​​[ 45 ]} junto con un algoritmo que se conjeturó (pero no se demostró) que tiene${\textstyle O(n^{2}\log ^{2}(n))}$complejidad; Mohlenkamp también proporciona una implementación en la biblioteca libftsh. ^{[ 46 ]} Un algoritmo de armónicos esféricos con${\textstyle O(n^{2}\log n)}$La complejidad es descrita por Rokhlin y Tygert. ^{[ 47 ]}

El algoritmo de plegado rápido es análogo a la FFT, excepto que opera sobre una serie de formas de onda agrupadas en lugar de una serie de valores escalares reales o complejos. La rotación (que en la FFT es la multiplicación por un fasor complejo) es un desplazamiento circular de la forma de onda componente ^{[ 48 ]} .

Varios grupos también han publicado algoritmos FFT para datos no equiespaciados, como se revisa en Potts et al. (2001). ^{[ 49 ]} Estos algoritmos no calculan estrictamente la DFT (que solo está definida para datos equiespaciados), sino más bien alguna aproximación de la misma (una transformada discreta de Fourier no uniforme , o NDFT, que a menudo se calcula solo de forma aproximada). De manera más general, existen otros métodos de estimación espectral .

La FFT se utiliza en software de grabación digital, muestreo, síntesis aditiva y corrección de tono . ^{[ 50 ]}

La importancia de la FFT radica en que ha hecho que trabajar en el dominio de la frecuencia sea tan factible computacionalmente como trabajar en el dominio temporal o espacial. Algunas de las aplicaciones importantes de la FFT incluyen: ^{[ 16 ] [ 51 ]}

• algoritmos rápidos de multiplicación de enteros grandes y multiplicación de polinomios,
• Multiplicación eficiente de matrices por vectores para matrices de Toeplitz , circulantes y otras matrices estructuradas,
• algoritmos de filtrado (véanse los métodos de superposición-suma y superposición-guardado ),
• algoritmos rápidos para transformadas discretas de coseno o seno (por ejemplo, DCT rápida utilizada para la codificación y decodificación JPEG y MPEG / MP3 ),
• aproximación rápida de Chebyshev ,
• resolución de ecuaciones en diferencias ,
• cálculo de distribuciones isotópicas . ^{[ 52 ]}

La transformada rápida de Fourier (FFT) puede ser una mala elección para analizar señales con contenido de frecuencia no estacionario , donde las características de frecuencia cambian con el tiempo. La transformada discreta de Fourier (DFT) proporciona una estimación global de la frecuencia, asumiendo que todos los componentes de frecuencia están presentes en toda la señal, lo que dificulta la detección de características transitorias o de corta duración dentro de las señales.

Para los casos en que la información de frecuencia aparece brevemente en la señal o varía generalmente con el tiempo, pueden ser más adecuadas alternativas como la transformada de Fourier de tiempo corto , las transformadas wavelet discretas o la transformada de Hilbert discreta . ^{[ 55 ] [ 56 ]} Estas transformadas permiten un análisis de frecuencia localizado al capturar información tanto de frecuencia como temporal.

Grandes FFT

Con la explosión de macrodatos en campos como la astronomía, ha surgido la necesidad de FFT de 512K para ciertos cálculos de interferometría. Los datos recopilados por proyectos como WMAP y LIGO requieren FFT de decenas de miles de millones de puntos. Dado que este tamaño no cabe en la memoria principal, las denominadas FFT fuera de memoria son un área de investigación activa. ^{[ 57 ]}

Transformadas de Fourier rápidas aproximadas

Para aplicaciones como la resonancia magnética, es necesario calcular transformadas discretas de Fourier (DFT) para puntos de la cuadrícula y/o frecuencias no uniformemente espaciados. Los enfoques basados ​​en multipolos pueden calcular cantidades aproximadas con un factor de aumento del tiempo de ejecución. ^{[ 58 ]}

FFT de grupo

La FFT también puede explicarse e interpretarse utilizando la teoría de representación de grupos , lo que permite una mayor generalización. Una función en cualquier grupo compacto, incluso los no cíclicos, tiene una expansión en términos de una base de elementos de matriz irreducibles. Sigue siendo un área activa de investigación encontrar un algoritmo eficiente para realizar este cambio de base. Las aplicaciones incluyen la expansión eficiente de armónicos esféricos , el análisis de ciertos procesos de Markov , la robótica, etc. ^{[ 59 ]}

Transformadas de Fourier rápidas cuánticas

El algoritmo rápido de Shor para la factorización de enteros en una computadora cuántica incluye una subrutina para calcular la DFT de un vector binario. Esta se implementa como una secuencia de puertas cuánticas de 1 o 2 bits, ahora conocida como FFT cuántica, que es, en esencia, la FFT de Cooley-Tukey realizada como una factorización particular de la matriz de Fourier. Actualmente se están explorando extensiones de estas ideas. ^{[ 60 ]}

Algoritmos relacionados con la FFT:

• Permutación de inversión de bits
• Algoritmo de Goertzel : calcula los términos individuales de la transformada discreta de Fourier.

Implementaciones de FFT:

• FFTW : una biblioteca de software libre desarrollada por Matteo Frigo y Steven G. Johnson en el MIT.
• FFTReal : una implementación altamente optimizada, limpia y concisa con soporte para escalares o vectores SIMD en una clase de C++ creada por Dmitry Boldyrev y alojada en GITHUB https://github.com/mewza/realfft/
• ALGLIB : una biblioteca de C++ y C# con licencia dual/GPL (que también admite otros lenguajes), con implementación de FFT real/compleja.
• FFTPACK – otra biblioteca FFT para Fortran (dominio público)
• Específico de la arquitectura:
  • Bibliotecas de rendimiento de Arm ^{[ 61 ]}
  • Primitivas de rendimiento integrado de Intel
  • Biblioteca del núcleo matemático de Intel
• Existen muchas más implementaciones disponibles, ^{[ 62 ]} para CPU y GPU, como PocketFFT para C++.

Otros enlaces:

• Diagrama de mariposa : un diagrama utilizado para describir las transformadas rápidas de Fourier (FFT).
• Algoritmos rápidos para señales multidimensionales
• Telescopio de transformada rápida de Fourier
• Transformación rápida de Walsh-Hadamard
• Ley distributiva generalizada
• Análisis espectral por mínimos cuadrados
• convolución discreta multidimensional
• Transformación multidimensional
• El algoritmo Odlyzko-Schönhage aplica la FFT a series finitas de Dirichlet
• Algoritmo de Schönhage-Strassen : algoritmo de multiplicación asintóticamente rápido para números enteros grandes
• Música espectral (implica la aplicación del análisis DFT a la composición musical)
• Analizador de espectro : cualquiera de los diversos dispositivos que realizan análisis de espectro, a menudo mediante una transformada discreta de Fourier (DFT).
• Series temporales

• Brigham, Elbert Oran (1974). La transformada rápida de Fourier (  ed. posterior). Englewood Cliffs, NJ: Prentice-Hall . ISBN 978-0-13-307496-3.
• Briggs, William L.; Henson, Van Emden (1995). La DFT: Manual del propietario de la transformada discreta de Fourier . Filadelfia: Society for Industrial and Applied Mathematics . ISBN 978-0-89871-342-8.
• Chu, Eleanor; George, Alan (2000). Dentro de la caja negra de la FFT: algoritmos de transformada rápida de Fourier en serie y en paralelo . Serie de matemáticas computacionales. Boca Raton, Florida. Londres: CRC Press . ISBN 978-0-8493-0270-1.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). «Capítulo 30: Polinomios y la FFT». Introducción a los algoritmos (2.ª  ed.). Cambridge (Massachusetts): MIT Press . ISBN 978-0-262-03293-3.
• Elliott, Douglas F.; Rao, K. Ramamohan (1982). Transformaciones rápidas: algoritmos, análisis, aplicaciones . Nueva York: Academic Press . ISBN 978-0-12-237080-9.
• Guo, H.; Sitton, GA; Burrus, CS (1994). "La transformada discreta de Fourier rápida". Actas de ICASSP '94. Conferencia Internacional IEEE sobre Acústica, Habla y Procesamiento de Señales . Vol.  iii. IEEE . págs.  III/445–III/448. doi : 10.1109/ICASSP.1994.389994 . ISBN 978-0-7803-1775-8. S2CID 42639206 . 
• Johnson, Steven G.; Frigo, Matteo (enero de 2007). "Una FFT de raíz dividida modificada con menos operaciones aritméticas" ( PDF) . IEEE Transactions on Signal Processing . 55 (1): 111– 119. Bibcode : 2007ITSP...55..111J . CiteSeerX 10.1.1.582.5497 . doi : 10.1109/TSP.2006.882087 . ISSN 1053-587X . S2CID 14772428. Archivado (PDF) del original el 26 de mayo de 2005.   
• Nussbaumer, Henri J. (1990). Algoritmos de convolución y transformada rápida de Fourier . Serie Springer en ciencias de la información (2., corr. y  edición actualizada). Berlín Heidelberg: Springer . ISBN 978-3-540-11825-1.
• Press, William H.; Teukolsky , Saul A .; Vetterling, William T.; Flannery, Brian P. (2007). «Capítulo 12. Transformada rápida de Fourier». Recetas numéricas: el arte de la computación científica (PDF) . Recetas numéricas (3.ª  ed.). Cambridge: Cambridge University Press . págs. 600–639 . ISBN  978-0-521-88068-8.
• Singleton, R. (junio de 1969). "Una breve bibliografía sobre la transformada rápida de Fourier". IEEE Transactions on Audio and Electroacoustics . 17 (2): 166– 169. Bibcode : 1969ITAuE..17..166S . doi : 10.1109/TAU.1969.1162040 . ISSN 0018-9278 . (Nota: Contiene una extensa bibliografía.)
• Prestini, Elena (2004). La evolución del análisis armónico aplicado: modelos del mundo real . Análisis armónico aplicado y numérico. Boston; Berlín: Springer Media . Sección 3.10: Gauss y los asteroides: historia de la FFT. ISBN 978-0-8176-4125-2.
• Van Loan, Charles F. (1992). Marcos computacionales para la transformada rápida de Fourier . Fronteras en matemáticas aplicadas. Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas . ISBN 978-0-89871-285-8.
• Terras, Audrey (1999). Análisis de Fourier en grupos finitos y aplicaciones . Textos para estudiantes de la London Mathematical Society. Cambridge (GB): Cambridge University Press . ISBN 978-0-521-45718-7.(Capítulo 9 y otros capítulos)

• Transformada rápida de Fourier para la multiplicación de polinomios – algoritmo rápido de Fourier 
• Transformada rápida de Fourier (FFT): programación de FFT en C++ : el algoritmo de Cooley-Tukey  
• Documentación en línea, enlaces, libro y código
• Sri Welaratna, " Treinta años de analizadores FFT Archivado el 12/01/2014 en Wayback Machine ", Sound and Vibration (enero de 1997, número del 30 aniversario) – una revisión histórica de los dispositivos FFT de hardware 
• ALGLIB FFT Code : una biblioteca multilingüe (VBA, C++, Pascal, etc.) para análisis numérico y procesamiento de datos con licencia dual/GPL. 
• SFFT: Transformada rápida de Fourier dispersa – Algoritmo FFT disperso (tiempo sublineal) del MIT , sFFT, e implementación. 
• VB6 FFT : una implementación de biblioteca optimizada para VB6 con código fuente. 
• Tutorial interactivo de FFT : una introducción visual e interactiva a las transformadas de Fourier y los métodos FFT. 
• Introducción al análisis de Fourier de series temporales : tutorial sobre cómo utilizar la transformada de Fourier en el análisis de series temporales.