Transformada rápida de Fourier

Algoritmo de transformada de Fourier discreta O(N log N)

Un ejemplo de estructura de algoritmo FFT, utilizando una descomposición en FFT de tamaño medio

Un análisis de Fourier discreto de una suma de ondas cosenoidales a 10, 20, 30, 40 y 50 Hz

Una transformada rápida de Fourier ( FFT ) es un algoritmo que calcula la transformada discreta de Fourier (DFT) de una secuencia, o su inversa (IDFT). El análisis de Fourier convierte una señal de su dominio original (a menudo tiempo o 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 de calcular la DFT de , que surge si uno simplemente aplica la definición de DFT, a , donde n es el tamaño de los datos. La diferencia en velocidad puede ser enorme, especialmente para conjuntos de datos largos donde n puede estar en miles o millones. En presencia de un error de redondeo , muchos algoritmos FFT son mucho más precisos que evaluar la definición DFT de forma directa o indirecta. Existen muchos algoritmos 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 . ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

Representación basada en el tiempo (arriba) y representación basada en la frecuencia (abajo) de la misma señal, donde la representación inferior se puede obtener a partir de la superior mediante la transformación de Fourier

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 ya se habían derivado en 1805. ^[1] En 1994, Gilbert Strang describió la FFT como "el algoritmo numérico más importante de nuestra era", ^{[3] [4]} y fue incluida en los 10 mejores algoritmos del siglo XX por la revista IEEE Computing in Science & Engineering . ^[5]

Los algoritmos FFT más conocidos dependen de la factorización de n , pero hay FFT con complejidad para todos, incluso primos , n . Muchos algoritmos FFT dependen solo del hecho de que es una raíz primitiva n 'ésima de la unidad , y por lo tanto se pueden aplicar a transformadas análogas sobre cualquier cuerpo finito , como las transformadas de 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 1/ n , cualquier algoritmo FFT se puede adaptar fácilmente para ella. ${\displaystyle O(n\log n)}$ ${\textstyle e^{-2\pi i/n}}$

Historia

El desarrollo de algoritmos rápidos para DFT se remonta al 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 sería publicado en 1965 por 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 fue anterior incluso a los resultados de 1822 de Joseph Fourier , 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 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 en el que 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 el cálculo aprovechando las "simetrías", Danielson y Lanczos se dieron cuenta de que se podía utilizar 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 al escalamiento. ^[11] ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

James Cooley y John Tukey redescubrieron de forma independiente 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 escala. ^[12] A Tukey se le ocurrió la idea durante una reunión del Comité Asesor Científico del Presidente Kennedy donde un tema de discusión involucraba la detección de pruebas nucleares por parte 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 la discusión con Tukey, Richard Garwin reconoció la aplicabilidad general del algoritmo no solo a los problemas de seguridad nacional, sino también a una amplia gama de problemas, incluido uno de interés inmediato para él, determinar las periodicidades de las orientaciones de espín en un cristal 3-D de helio-3. ^[13] Garwin le dio la idea de Tukey a Cooley (ambos trabajaban en los laboratorios Watson de IBM ) para su implementación. ^[14] Cooley y Tukey publicaron el artículo en un tiempo relativamente corto de seis meses. ^[15] Como Tukey no trabajaba en IBM, se puso en duda la patentabilidad de la idea y el algoritmo pasó al dominio público, lo que, a través de la revolución informática de la década siguiente, convirtió a FFT en uno de los algoritmos indispensables en el procesamiento de señales digitales . ${\textstyle O(n\log n)}$

Definición

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

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

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

Para evaluar esta definición directamente se requieren 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 operaciones. Todos los algoritmos FFT conocidos requieren operaciones, aunque no se conoce ninguna prueba de que una complejidad menor sea imposible. ^[16] ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$ ${\textstyle O(n\log n)}$

Para ilustrar los ahorros de una FFT, considere el recuento de multiplicaciones y adiciones complejas para los puntos de datos. La evaluación directa de las sumas de la DFT involucra multiplicaciones complejas y adiciones complejas, de las cuales las operaciones se pueden ahorrar eliminando operaciones triviales como multiplicaciones por 1, dejando alrededor de 30 millones de operaciones. En contraste, el algoritmo de Cooley-Tukey de base 2, para n una potencia de 2, puede calcular el mismo resultado solo con multiplicaciones complejas (de nuevo, ignorando las simplificaciones de multiplicaciones por 1 y similares) y adiciones complejas, en total alrededor de 30.000 operaciones, mil 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, consulte Frigo & Johnson , 2005), ^[17] pero la mejora general de a permanece. ${\textstyle n=4096}$ ${\textstyle n^{2}}$ ${\textstyle n(n-1)}$ ${\textstyle O(n)}$ ${\textstyle (n/2)\log _{2}(n)}$ ${\textstyle n\log _{2}(n)}$ ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

Algoritmos

Algoritmo de Cooley-Tukey

La FFT más utilizada es el algoritmo Cooley-Tukey. Se trata de un algoritmo de divide y vencerás que descompone recursivamente una DFT de cualquier tamaño compuesto en DFT más pequeñas de tamaño , junto con multiplicaciones por raíces complejas de la unidad, tradicionalmente llamadas factores de twiddle (según Gentleman y Sande, 1966). ^[18] ${\textstyle n=n_{1}n_{2}}$ ${\textstyle n_{1}}$ ${\textstyle n_{2}}$ ${\displaystyle O(n)}$

Este método (y la idea general de una FFT) se popularizó gracias a una publicación de Cooley y Tukey en 1965, ^[12] pero más tarde se descubrió ^[1] que esos dos autores habían reinventado juntos e independientemente un algoritmo conocido por Carl Friedrich Gauss alrededor de 1805 ^[19] (y posteriormente redescubierto varias veces en formas limitadas).

El uso más conocido del algoritmo Cooley-Tukey es dividir la transformada en dos partes de tamaño n/2 en cada paso, y por lo tanto está limitado a tamaños de potencia de dos, pero cualquier factorización se puede utilizar en general (como lo sabían tanto Gauss como Cooley/Tukey ^[1] ). Estos se denominan casos de base 2 y base mixta , respectivamente (y otras variantes como la FFT de base dividida también tienen sus propios nombres). Aunque la idea básica es recursiva, la mayoría de las implementaciones tradicionales reorganizan el algoritmo para evitar la recursión explícita. Además, 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, como los que se describen a continuación.

Otros algoritmos FFT

Existen otros algoritmos FFT además de Cooley-Tukey.

Para con coprimos y , se puede usar el algoritmo de factor primo (Good–Thomas) (PFA), basado en el teorema del resto chino , para factorizar la DFT de manera similar a Cooley–Tukey pero sin los factores twiddle. El algoritmo de Rader–Brenner (1976) ^[20] es una factorización similar a Cooley–Tukey pero con factores twiddle puramente imaginarios, reduciendo las multiplicaciones a costa de mayores adiciones y una estabilidad numérica reducida ; luego fue reemplazado por la variante de base dividida de Cooley–Tukey (que logra el mismo conteo de multiplicaciones pero con menos adiciones y sin sacrificar la precisión). Los algoritmos que factorizan recursivamente la DFT en operaciones más pequeñas distintas de las DFT incluyen los algoritmos de Bruun y QFT. (Los algoritmos Rader–Brenner ^[20] y QFT se propusieron para tamaños de potencia de dos, pero es posible que se puedan adaptar a n compuestos generales . El algoritmo de Bruun se aplica a tamaños compuestos pares arbitrarios). El algoritmo de Bruun , en particular, se basa en interpretar la FFT como una factorización recursiva del polinomio , aquí en polinomios de coeficientes reales de la forma y . ${\textstyle n=n_{1}n_{2}}$ ${\textstyle n_{1}}$ ${\textstyle n_{2}}$ ${\displaystyle z^{n}-1}$ ${\displaystyle z^{m}-1}$ ${\displaystyle z^{2m}+az^{m}+1}$

Otro punto de vista polinomial es explotado por el algoritmo FFT de Winograd, ^{[21] [22]} que factoriza en polinomios ciclotómicos —estos a menudo tienen coeficientes de 1, 0 o −1, y por lo tanto requieren pocas multiplicaciones (si es que hay alguna), por lo que Winograd puede usarse para obtener FFT de multiplicación mínima y a menudo se usa para encontrar algoritmos eficientes para factores pequeños. De hecho, Winograd demostró que la DFT puede calcularse solo con multiplicaciones irracionales, lo que conduce a un límite inferior alcanzable probado en el número de multiplicaciones para tamaños de potencia de dos; esto se produce a costa de muchas más adiciones, una compensación que ya no es favorable en los procesadores modernos con multiplicadores de hardware . En particular, Winograd también hace uso del PFA, así como de un algoritmo de Rader para FFT de tamaños primos . ${\displaystyle z^{n}-1}$ ${\displaystyle O(n)}$

El algoritmo de Rader , que explota la existencia de un generador para el grupo multiplicativo módulo primo n , expresa una DFT de tamaño primo n como una convolución cíclica de tamaño (compuesto) n – 1 , que luego se puede calcular mediante un par de FFT ordinarias a través del teorema de convolución (aunque Winograd utiliza otros métodos de convolución). Otra FFT de tamaño primo se debe a LI Bluestein, y a veces se denomina algoritmo chirp-z ; también reexpresa una DFT como una convolución, pero esta vez del mismo tamaño (que se puede rellenar con ceros hasta una potencia de dos y evaluar mediante FFT de Cooley–Tukey de base 2, por ejemplo), a través de la identidad

${\displaystyle nk=-{\frac {(k-n)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}.}$

La transformada rápida de Fourier hexagonal (HFFT) tiene como objetivo calcular una FFT eficiente para los datos muestreados hexagonalmente utilizando un nuevo esquema de direccionamiento para cuadrículas hexagonales, llamado Direccionamiento de Conjunto de Arreglos (ASA).

Algoritmos FFT especializados para datos reales o simétricos

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

${\displaystyle X_{n-k}=X_{k}^{*}}$

y se han diseñado algoritmos FFT eficientes para esta situación (véase, por ejemplo, Sorensen, 1987). ^{[23] [24]} 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 reales e imaginarias son los elementos pares/impares de los datos reales originales), seguida de operaciones de posprocesamiento. ${\displaystyle O(n)}$

Se creía que las DFT de entrada real se podían calcular de manera más eficiente mediante la transformada Hartley discreta (DHT), pero posteriormente se argumentó que normalmente se puede encontrar un algoritmo DFT de entrada real (FFT) especializado que requiera menos operaciones que el algoritmo DHT (FHT) correspondiente para la misma cantidad de entradas. ^[23] El algoritmo de Bruun (arriba) es otro método que se propuso inicialmente para aprovechar las entradas reales, pero no ha demostrado ser popular.

Existen otras especializaciones 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 de FFT para estos casos, las DCT/DST también se pueden calcular a través de FFT de datos reales combinadas con preprocesamiento y posprocesamiento. ${\displaystyle O(n)}$

Problemas computacionales

Límites en la complejidad y el número de operaciones

Problema sin resolver en informática :

¿Cuál es el límite inferior de la complejidad de los algoritmos de transformada rápida de Fourier? ¿Pueden ser más rápidos que ? ${\displaystyle O(N\log N)}$

(más problemas sin resolver en informática)

Una cuestión fundamental de interés teórico desde hace mucho tiempo es demostrar límites inferiores a la complejidad y el número exacto de operaciones de las transformadas rápidas de Fourier, y aún quedan muchos problemas abiertos. No se ha demostrado rigurosamente si las DFT realmente requieren operaciones (es decir, de orden o mayor), incluso para el caso simple de potencia de dos tamaños, aunque no se conocen algoritmos con menor complejidad. En particular, el número de operaciones aritméticas suele ser el foco de tales preguntas, aunque el rendimiento real en las computadoras modernas está determinado por muchos otros factores, como la optimización de la memoria caché o la canalización de la CPU . ${\textstyle \Omega (n\log n)}$ ${\displaystyle n\log n}$

Siguiendo el trabajo de Shmuel Winograd (1978), ^[21] se conoce un límite inferior estricto para el número de multiplicaciones reales requeridas por una FFT. Se puede demostrar que solo se requieren multiplicaciones reales irracionales para calcular una DFT de longitud de potencia de dos . Además, se conocen algoritmos explícitos que logran este recuento (Heideman y Burrus , 1986; ^[25] Duhamel, 1990 ^[26] ). Sin embargo, estos algoritmos requieren demasiadas adiciones para ser prácticos, al menos en computadoras modernas con multiplicadores de hardware (Duhamel, 1990; ^[26] Frigo y Johnson , 2005). ^[17] ${\displaystyle \Theta (n)}$ ${\textstyle 4n-2\log _{2}^{2}(n)-2\log _{2}(n)-4}$ ${\displaystyle n=2^{m}}$

No se conoce un límite inferior estricto para el número de adiciones requeridas, aunque se han demostrado límites inferiores bajo algunas suposiciones restrictivas sobre los algoritmos. En 1973, Morgenstern ^[27] demostró un límite inferior para el recuento de adiciones para algoritmos donde las constantes multiplicativas tienen magnitudes acotadas (lo que es cierto para la mayoría de los algoritmos FFT, pero no para todos). Pan (1986) ^[28] demostró un límite inferior asumiendo un límite en una medida de la "asincronicidad" del algoritmo FFT, pero la generalidad de esta suposición no está clara. Para el caso de la potencia de dos n , Papadimitriou (1979) ^[29] argumentó que el número de adiciones de números complejos logradas por los algoritmos Cooley-Tukey es óptimo bajo ciertas suposiciones sobre el gráfico del algoritmo (sus suposiciones implican, entre otras cosas, que no se explotan identidades aditivas en las raíces de la unidad). (Este argumento implicaría que se requieren al menos adiciones reales, aunque este no es un límite estricto porque se requieren adiciones adicionales como parte de las multiplicaciones de números complejos). Hasta el momento, ningún algoritmo FFT publicado ha logrado menos de adiciones de números complejos (o su equivalente) para n de potencia de dos . ${\displaystyle \Omega (n\log n)}$ ${\displaystyle \Omega (n\log n)}$ ${\textstyle n\log _{2}n}$ ${\textstyle 2N\log _{2}N}$ ${\textstyle n\log _{2}n}$

Un tercer problema es minimizar el número total de multiplicaciones y sumas reales, a veces llamada "complejidad aritmética" (aunque en este contexto es el recuento exacto y no la complejidad asintótica lo que se está considerando). Nuevamente, no se ha demostrado un límite inferior estricto. Sin embargo, desde 1968, el recuento publicado más bajo para la potencia de dos n se logró durante mucho tiempo mediante el algoritmo FFT de base dividida , que requiere multiplicaciones y sumas reales para n > 1. Esto se redujo recientemente a (Johnson y Frigo, 2007; ^[16] Lundy y Van Buskirk, 2007 ^[30] ). Se demostró que un recuento ligeramente mayor (pero aún mejor que el radix dividido para n ≥ 256 ) era demostrablemente óptimo para n ≤ 512 bajo restricciones adicionales en los algoritmos posibles (gráficos de flujo similares a radix dividido con factores multiplicativos de módulo unitario), por reducción a un problema de teorías de módulo de satisfacibilidad solucionable por fuerza bruta (Haynal y Haynal, 2011). ^[31] ${\textstyle 4n\log _{2}(n)-6n+8}$ ${\textstyle \sim {\frac {34}{9}}n\log _{2}n}$

La mayoría de los intentos de reducir o demostrar la complejidad de los algoritmos FFT se han centrado en el caso de datos complejos ordinarios, porque es el más simple. Sin embargo, las FFT de datos complejos están tan estrechamente relacionadas con algoritmos para problemas relacionados, como las FFT de datos reales, las transformadas de coseno discretas , las transformadas de Hartley discretas , etc., que cualquier mejora en una de ellas conduciría inmediatamente a mejoras en las otras (Duhamel y Vetterli, 1990). ^[32]

Aproximaciones

Todos los algoritmos FFT discutidos anteriormente calculan la DFT exactamente (es decir, ignorando los errores de punto flotante ). Sin embargo, se han propuesto algunos algoritmos "FFT" que calculan la DFT aproximadamente , con un error que puede hacerse arbitrariamente pequeño a expensas de mayores cálculos. Tales algoritmos intercambian el error de aproximación por mayor velocidad u otras propiedades. Por ejemplo, un algoritmo FFT aproximado de Edelman et al. (1999) ^[33] logra menores requisitos de comunicación para computación paralela con la ayuda de un método multipolar rápido . Una FFT aproximada basada en wavelets de Guo y Burrus (1996) ^[34] tiene en cuenta entradas/salidas dispersas (localización de tiempo/frecuencia) de manera más eficiente de lo que es posible con una FFT exacta. Otro algoritmo para el cálculo aproximado de un subconjunto de las salidas de la DFT se debe a Shentov et al. (1995). ^[35] El algoritmo de Edelman funciona igualmente bien para datos dispersos y no dispersos, ya que se basa en la compresibilidad (deficiencia de rango) de la matriz de Fourier en sí misma en lugar de la compresibilidad (esparcimiento) de los datos. Por el contrario, si los datos son dispersos (es decir, si solo k de n coeficientes de Fourier son distintos de cero), entonces la complejidad se puede reducir a , y se ha demostrado que esto conduce a aceleraciones prácticas en comparación con una FFT ordinaria para n / k > 32 en un ejemplo de n grande ( n = 2 ²² ) utilizando un algoritmo aproximado probabilístico (que estima los coeficientes k más grandes con varios decimales). ^[36] ${\displaystyle O(k\log n\log n/k)}$

Exactitud

Los algoritmos FFT tienen errores cuando se utiliza aritmética de punto flotante de precisión finita, pero estos errores son típicamente bastante pequeños; la mayoría de los algoritmos FFT, por ejemplo Cooley–Tukey, tienen excelentes propiedades numéricas como consecuencia de la estructura de suma por pares de los algoritmos. El límite superior del error relativo para el algoritmo Cooley–Tukey es , comparado con para la fórmula DFT ingenua, ^[18] donde 𝜀 es la precisión relativa de punto flotante de la máquina. De hecho, los errores de raíz cuadrada media (rms) son mucho mejores que estos límites superiores, siendo solo para Cooley–Tukey y para la DFT ingenua (Schatzman, 1996). ^[37] Estos resultados, sin embargo, son muy sensibles a la precisión de los factores de twiddle utilizados en la FFT (es decir, los valores de la función trigonométrica ), y no es inusual que las implementaciones de FFT imprudentes tengan una precisión mucho peor, por ejemplo, si utilizan fórmulas de recurrencia trigonométrica inexactas . Algunas FFT distintas de Cooley-Tukey, como el algoritmo Rader-Brenner, son intrínsecamente menos estables. ${\textstyle O(\varepsilon \log n)}$ ${\textstyle O(\varepsilon n^{3/2})}$ ${\textstyle O(\varepsilon {\sqrt {\log n}})}$ ${\textstyle O(\varepsilon {\sqrt {n}})}$

En la aritmética de punto fijo , los errores de precisión finita acumulados por los algoritmos FFT son peores, con errores rms crecientes como en el algoritmo Cooley-Tukey (Welch, 1969). ^[38] Lograr esta precisión requiere una cuidadosa atención al escalamiento para minimizar la pérdida de precisión, y los algoritmos FFT de punto fijo implican un reescalamiento en cada etapa intermedia de las descomposiciones como Cooley-Tukey. ${\textstyle O({\sqrt {n}})}$

Para verificar la corrección de una implementación de FFT, se pueden obtener garantías rigurosas en el tiempo mediante un procedimiento simple que verifica las propiedades de linealidad, respuesta al impulso y desplazamiento temporal de la transformación en entradas aleatorias (Ergün, 1995). ^[39] ${\textstyle O(n\log n)}$

Los valores de las frecuencias intermedias pueden obtenerse mediante diversos métodos de promediado.

FFT multidimensionales

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 mediante un conjunto de d sumas anidadas ( para cada j ), donde la división se realiza elemento por elemento. De manera 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). ${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$ ${\textstyle n_{j}=0\ldots N_{j}-1}$ ${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}$

Este punto de vista compositivo proporciona inmediatamente el algoritmo DFT multidimensional más simple y más común, conocido como el algoritmo fila-columna (después del caso bidimensional, a continuación). Es decir, uno simplemente realiza una secuencia de d FFT unidimensionales (por cualquiera de los algoritmos anteriores): primero se transforma a lo largo de la dimensión n _{1 , luego a lo largo de la dimensión} n ₂ , y así sucesivamente (en realidad, cualquier orden funciona). Se demuestra fácilmente que este método tiene la complejidad habitual, donde 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: ${\textstyle O(n\log n)}$ ${\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}$

${\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, x _k puede verse como una matriz , y este algoritmo corresponde a realizar primero la FFT de todas las filas (resp. columnas), agrupar las filas transformadas resultantes (resp. columnas) juntas como otra matriz, y luego realizar la FFT en cada una de las columnas (resp. filas) de esta segunda matriz, y agrupar de manera similar los resultados en la matriz de resultados final. ${\displaystyle n_{1}\times n_{2}}$ ${\displaystyle n_{1}\times n_{2}}$

En más de dos dimensiones, suele ser ventajoso que la localidad de caché agrupe las dimensiones de forma recursiva. Por ejemplo, una FFT tridimensional podría realizar primero FFT bidimensionales de cada "rebanada" planar para cada n ₁ fijo , y luego realizar las FFT unidimensionales a lo largo de la dirección n _{1. De manera más general, un algoritmo} asintóticamente óptimo que ignora la caché consiste en dividir recursivamente las dimensiones en dos grupos y que se transforman recursivamente (redondeando si d no es par) (consulte Frigo y Johnson, 2005). ^[17] Aún así, esto sigue siendo una variación sencilla del algoritmo de fila-columna que, en última instancia, requiere solo un algoritmo FFT unidimensional como caso base, y aún tiene complejidad. Otra variación es realizar transposiciones de matriz entre las transformaciones de dimensiones posteriores, de modo que las transformaciones operen sobre datos contiguos; esto es especialmente importante para situaciones de memoria distribuida y fuera del núcleo donde acceder a datos no contiguos consume mucho tiempo. ${\textstyle (n_{1},\ldots ,n_{d/2})}$ ${\textstyle (n_{d/2+1},\ldots ,n_{d})}$ ${\displaystyle O(n\log n)}$

Existen otros algoritmos FFT multidimensionales que son distintos del algoritmo fila-columna, aunque todos ellos tienen complejidad. Quizás el algoritmo FFT sin fila-columna más simple es el algoritmo FFT vector-raíz , que es una generalización del algoritmo Cooley-Tukey ordinario donde uno divide las dimensiones de la transformada por un vector de raíces en cada paso. (Esto también puede tener beneficios de caché). El caso más simple de vector-raíz es donde todas las raíces son iguales (por ejemplo, vector-raíz-2 divide todas las dimensiones por dos), pero esto no es necesario. El vector-raíz con solo una única raíz no unitaria a la vez, es decir , es esencialmente un algoritmo fila-columna. Otros métodos más complicados incluyen algoritmos de transformada polinómica debido a Nussbaumer (1977), ^[40] que ven la transformada en términos de convoluciones y productos polinómicos. Consulte Duhamel y Vetterli (1990) ^[32] para obtener más información y referencias. ${\textstyle O(n\log n)}$ ${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$ ${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$

Otras generalizaciones

^{Mohlenkamp [41]} describió una generalización a los armónicos esféricos en la esfera S ² con n ² nodos , junto con un algoritmo que se conjetura (pero no se ha demostrado) que tiene complejidad; Mohlenkamp también proporciona una implementación en la biblioteca libftsh. ^[42] Rokhlin y Tygert describen un algoritmo esférico-armónico con complejidad. ^[43] ${\textstyle O(n^{5/2}\log n)}$ ${\textstyle O(n^{2}\log ^{2}(n))}$ ${\textstyle O(n^{2}\log n)}$

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 del componente.

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

Aplicaciones

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

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

• Algoritmos rápidos de multiplicación de números enteros grandes y multiplicación de polinomios.
• Multiplicación eficiente de matrices y vectores para matrices de Toeplitz , circulantes y otras matrices estructuradas.
• algoritmos de filtrado (ver métodos de superposición-adición y superposición-guardado ),
• Algoritmos rápidos para transformaciones discretas de coseno o seno (por ejemplo, DCT rápida utilizada para codificación y decodificación de JPEG y MPEG / MP3 ),
• aproximación rápida de Chebyshev ,
• resolver ecuaciones diferenciales ,
• Cálculo de distribuciones isotópicas . ^[47]
• Modulación y demodulación de símbolos de datos complejos utilizando multiplexación por división de frecuencia ortogonal (OFDM) para 5G, LTE, Wi-Fi, DSL y otros sistemas de comunicación modernos.

Una aplicación original de la FFT en finanzas, particularmente en la valoración de opciones, fue desarrollada por Marcello Minenna. ^[48]

Áreas de investigación

Grandes FFT

Con la explosión de los 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. Como este tamaño no cabe en la memoria principal, las llamadas FFT fuera del núcleo son un área activa de investigación. ^[49]

FFT aproximadas

Para aplicaciones como la resonancia magnética, es necesario calcular las DFT para puntos de 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. ^[50]

FFT grupales

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, incluidos 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 una expansión armónica esférica eficiente , el análisis de ciertos procesos de Markov , la robótica, etc. ^[51]

Transformaciones cuánticas de Fourier (FFT)

El algoritmo rápido de Shor para la factorización de números enteros en una computadora cuántica tiene una subrutina para calcular la FFT de un vector binario. Esto se implementa como una secuencia de puertas cuánticas de 1 o 2 bits conocida ahora como FFT cuántica, que es efectivamente la FFT de Cooley-Tukey realizada como una factorización particular de la matriz de Fourier. Actualmente se está explorando la extensión de estas ideas. ^[52]

Referencia del idioma

Véase también

Algoritmos relacionados con FFT:

• Permutación de inversión de bits

• Algoritmo de Goertzel : calcula términos individuales de la transformada de Fourier discreta

Implementaciones de FFT:

• ALGLIB : una biblioteca C++ y C# con licencia dual/GPL (que también admite otros lenguajes), con implementación de FFT real/compleja
• FFTPACK : otra biblioteca FFT de Fortran (dominio público)
• Específico de la arquitectura:
  • Bibliotecas de rendimiento de brazo ^[53]
  • Primitivas de rendimiento integradas de Intel
  • Biblioteca de núcleos matemáticos de Intel
• Hay muchas más implementaciones disponibles, ^[54] para CPU y GPU, como PocketFFT para C++

Otros enlaces:

• 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
• Diagrama de mariposa : un diagrama utilizado para describir las FFT
• Música espectral (implica la aplicación del análisis DFT a la composición musical)
• Analizador de espectro : cualquiera de varios dispositivos que realizan análisis de espectro, a menudo a través de una DFT
• Serie temporal
• Transformada rápida de Walsh-Hadamard
• Ley distributiva generalizada
• Análisis espectral de mínimos cuadrados
• Transformación multidimensional
• Convolución discreta multidimensional
• Telescopio de transformada rápida de Fourier

Referencias

1. Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "Gauss y la historia de la transformada rápida de Fourier" (PDF) . Revista IEEE ASSP . 1 (4): 14–21. CiteSeerX  10.1.1.309.181 . doi :10.1109/MASSP.1984.1162257. S2CID  10032502. Archivado (PDF) desde el original el 19 de marzo de 2013.
2. Van Loan, Charles (1992). Marcos computacionales para la transformada rápida de Fourier . SIAM .
3. Strang, Gilbert (mayo-junio de 1994). "Wavelets". American Scientist . 82 (3): 250–255. JSTOR  29775194.
4. Kent, Ray D.; Read, Charles (2002). Análisis acústico del habla . Singular/Thomson Learning. ISBN 0-7693-0112-6.
5. Dongarra, Jack; Sullivan, Francis (enero de 2000). "Introducción de los editores invitados a los 10 algoritmos principales". Computing in Science & Engineering . 2 (1): 22–23. Bibcode :2000CSE.....2a..22D. doi :10.1109/MCISE.2000.814652. ISSN  1521-9615.
6. Gauss, Carl Friedrich (1866). "Theoria interpolationis Methodo nova tractata" [Teoría sobre un nuevo método de interpolación]. Nachlass (manuscrito inédito). Werke (en latín y alemán). vol. 3. Göttingen, Alemania: Königlichen Gesellschaft der Wissenschaften zu Göttingen. págs. 265–303.
7. Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). "Gauss y la historia de la transformada rápida de Fourier". Archivo de Historia de las Ciencias Exactas . 34 (3): 265–277. CiteSeerX 10.1.1.309.181 . doi :10.1007/BF00348431. ISSN  0003-9519. S2CID  122847826. 
8. Yates, Frank (1937). "El diseño y análisis de experimentos factoriales". Comunicación técnica n.º 35 de la Oficina de Suelos de la Commonwealth . 142 (3585): 90–92. Bibcode :1938Natur.142...90F. doi :10.1038/142090a0. S2CID  23501205.
9. Danielson, Gordon C. ; Lanczos, Cornelius (1942). "Algunas mejoras en el análisis práctico de Fourier y su aplicación a la dispersión de rayos X de líquidos". Journal of the Franklin Institute . 233 (4): 365–380. doi :10.1016/S0016-0032(42)90767-1.
10. Lanczos, Cornelius (1956). Análisis aplicado . Prentice–Hall .
11. Cooley, James W. ; Lewis, Peter AW; Welch, Peter D. (junio de 1967). "Notas históricas sobre la transformada rápida de Fourier". IEEE Transactions on Audio and Electroacoustics . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . doi :10.1109/TAU.1967.1161903. ISSN  0018-9278. 
12. Cooley, James W. ; Tukey, John W. (1965). "Un algoritmo para el cálculo de máquinas de series complejas de Fourier". Matemáticas de la computación . 19 (90): 297–301. doi : 10.1090/S0025-5718-1965-0178586-1 . ISSN  0025-5718.
13. Cooley, James W. (1987). "El redescubrimiento del algoritmo de la transformada rápida de Fourier" (PDF) . Microchimica Acta . Vol. III. Viena, Austria. págs. 33–45. Archivado (PDF) desde el original el 20 de agosto de 2016.{{cite book}}: CS1 maint: location missing publisher (link)
14. Garwin, Richard (junio de 1969). "La transformada rápida de Fourier como ejemplo de la dificultad de conseguir un uso amplio de una nueva técnica" (PDF) . IEEE Transactions on Audio and Electroacoustics . AU-17 (2): 68–72. Archivado (PDF) desde el original el 17 de mayo de 2006.
15. Rockmore, Daniel N. (enero de 2000). "La FFT: un algoritmo que toda la familia puede usar". Computing in Science & Engineering . 2 (1): 60–64. Bibcode :2000CSE.....2a..60R. CiteSeerX 10.1.1.17.228 . doi :10.1109/5992.814659. ISSN  1521-9615. S2CID  14978667. 
16. Frigo, Matteo; Johnson, Steven G. (enero de 2007) [19 de diciembre de 2006]. "Una FFT de radio dividido modificada con menos operaciones aritméticas". 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. S2CID  14772428. 
17. Frigo, Matteo; Johnson, Steven G. (2005). "El diseño y la implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. Bibcode :2005IEEEP..93..216F. CiteSeerX 10.1.1.66.3097 . doi :10.1109/jproc.2004.840301. S2CID  6644892. Archivado (PDF) desde el original el 2005-02-07. 
18. Gentleman, W. Morven; Sande, G. (1966). "Transformadas rápidas de Fourier: por diversión y beneficio". Actas de la AFIPS . 29 : 563–578. doi : 10.1145/1464291.1464352 . S2CID  207170956.
19. Gauss, Carl Friedrich (1866) [1805]. Theoria interpolationis método nova tractata. Werke (en latín y alemán). vol. 3. Gotinga, Alemania: Königliche Gesellschaft der Wissenschaften. págs. 265–327.
20. Brenner, Norman M.; Rader, Charles M. (1976). "Un nuevo principio para la transformada rápida de Fourier". IEEE Transactions on Acoustics, Speech, and Signal Processing . 24 (3): 264–266. doi :10.1109/TASSP.1976.1162805.
21. Winograd, Shmuel (1978). "Sobre el cálculo de la transformada de Fourier discreta". Matemáticas de la computación . 32 (141): 175–199. doi :10.1090/S0025-5718-1978-0468306-4. JSTOR  2006266. PMC 430186 . PMID  16592303. 
22. Winograd, Shmuel (1979). "Sobre la complejidad multiplicativa de la transformada de Fourier discreta". Avances en Matemáticas . 32 (2): 83–117. doi :10.1016/0001-8708(79)90037-9.
23. Sorensen, Henrik V.; Jones, Douglas L .; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Algoritmos de transformada rápida de Fourier con valor real". IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (6): 849–863. CiteSeerX 10.1.1.205.4523 . doi :10.1109/TASSP.1987.1165220. 
24. Sorensen, Henrik V.; Jones, Douglas L .; Heideman, Michael T.; Burrus, Charles Sidney (1987). "Correcciones a los "Algoritmos de transformada rápida de Fourier de valor real"". Transacciones IEEE sobre acústica, habla y procesamiento de señales . 35 (9): 1353. doi :10.1109/TASSP.1987.1165284.
25. Heideman, Michael T.; Burrus, Charles Sidney (1986). "Sobre el número de multiplicaciones necesarias para calcular una DFT de longitud 2 ^{n ".} IEEE Transactions on Acoustics, Speech, and Signal Processing . 34 (1): 91–95. doi :10.1109/TASSP.1986.1164785.
26. Duhamel, Pierre (1990). "Algoritmos que cumplen los límites inferiores de la complejidad multiplicativa de las DFT de longitud 2 ⁿ y su conexión con algoritmos prácticos". IEEE Transactions on Acoustics, Speech, and Signal Processing . 38 (9): 1504–1511. doi :10.1109/29.60070.
27. Morgenstern, Jacques (1973). "Nota sobre un límite inferior de la complejidad lineal de la transformada rápida de Fourier". Revista de la ACM . 20 (2): 305–306. doi : 10.1145/321752.321761 . S2CID  2790142.
28. Pan, Victor Ya. (2 de enero de 1986). "El equilibrio entre la complejidad aditiva y la asincronicidad de los algoritmos lineales y bilineales". Information Processing Letters . 22 (1): 11–14. doi :10.1016/0020-0190(86)90035-9 . Consultado el 31 de octubre de 2017 .
29. Papadimitriou, Christos H. (1979). "Optimalidad de la transformada rápida de Fourier". Revista de la ACM . 26 : 95–102. doi : 10.1145/322108.322118 . S2CID  850634.
30. Lundy, Thomas J.; Van Buskirk, James (2007). "Un nuevo enfoque matricial para las FFT reales y las convoluciones de longitud 2 ^k ". Computing . 80 (1): 23–45. doi :10.1007/s00607-007-0222-6. S2CID  27296044.
31. Haynal, Steve; Haynal, Heidi (2011). "Generación y búsqueda de familias de algoritmos FFT" (PDF) . Revista sobre satisfacibilidad, modelado booleano y computación . 7 (4): 145–187. arXiv : 1103.5740 . Código Bibliográfico :2011arXiv1103.5740H. doi :10.3233/SAT190084. S2CID  173109. Archivado desde el original (PDF) el 26 de abril de 2012.
32. Duhamel, Pierre; Vetterli, Martin (1990). "Transformadas rápidas de Fourier: una revisión tutorial y un estado del arte". Procesamiento de señales . 19 (4): 259–299. Código Bibliográfico :1990SigPr..19..259D. doi :10.1016/0165-1684(90)90158-U.
33. Edelman, Alan; McCorquodale, Peter; Toledo, Sivan (1999). "¿La futura transformada rápida de Fourier?" (PDF) . Revista SIAM sobre informática científica . 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339 . doi :10.1137/S1064827597316266. Archivado (PDF) desde el original el 5 de julio de 2017. 
34. Guo, Haitao; Burrus, Charles Sidney (1996). "Transformada de Fourier aproximada rápida mediante la transformada wavelets". En Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F. (eds.). Aplicaciones wavelet en procesamiento de señales e imágenes IV . Actas de SPIE . Vol. 2825. págs. 250–259. Código Bibliográfico :1996SPIE.2825..250G. CiteSeerX 10.1.1.54.3984 . doi :10.1117/12.255236. S2CID  120514955. 
35. Shentov, Ognjan V.; Mitra, Sanjit K.; Alto, Ulrich; Hossen, Abdul N. (1995). "Subbanda DFT. I. Definición, interpretaciones y ampliaciones". Procesamiento de señales . 41 (3): 261–277. doi :10.1016/0165-1684(94)00103-7.
36. Hassanieh, Haitham; Indyk, Piotr ; Katabi, Dina; Price, Eric (enero de 2012). "Algoritmo simple y práctico para la transformada de Fourier dispersa" (PDF) . Simposio ACM-SIAM sobre algoritmos discretos . Archivado (PDF) desde el original el 4 de marzo de 2012.(NB. Véase también la página web de sFFT.)
37. Schatzman, James C. (1996). "Exactitud de la transformada de Fourier discreta y la transformada de Fourier rápida". Revista SIAM de Informática Científica . 17 (5): 1150–1166. Bibcode :1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184 . doi :10.1137/s1064827593247023. 
38. Welch, Peter D. (1969). "Un análisis de error de transformada rápida de Fourier de punto fijo". IEEE Transactions on Audio and Electroacoustics . 17 (2): 151–157. doi :10.1109/TAU.1969.1162035.
39. Ergün, Funda (1995). "Prueba de funciones lineales multivariadas". Actas del vigésimo séptimo simposio anual de la ACM sobre teoría de la computación - STOC '95 . Kioto, Japón. págs. 407–416. doi :10.1145/225058.225167. ISBN 978-0897917186. Número de identificación del sujeto  15512806.{{cite book}}: CS1 maint: location missing publisher (link)
40. Nussbaumer, Henri J. (1977). "Filtrado digital mediante transformadas polinómicas". Electronics Letters . 13 (13): 386–387. Bibcode :1977ElL....13..386N. doi :10.1049/el:19770280.
41. Mohlenkamp, ​​Martin J. (1999). "Una transformada rápida para armónicos esféricos" (PDF) . Journal of Fourier Analysis and Applications . 5 (2–3): 159–184. Bibcode :1999JFAA....5..159M. CiteSeerX 10.1.1.135.9830 . doi :10.1007/BF01261607. S2CID  119482349. Archivado (PDF) desde el original el 2017-05-06 . Consultado el 2018-01-11 . 
42. "biblioteca libftsh". Archivado desde el original el 23 de junio de 2010. Consultado el 9 de enero de 2007 .
43. Rokhlin, Vladimir; Tygert, Mark (2006). "Algoritmos rápidos para expansiones armónicas esféricas" (PDF) . Revista SIAM de informática científica . 27 (6): 1903–1928. Bibcode :2006SJSC...27.1903R. CiteSeerX 10.1.1.125.7415 . doi :10.1137/050623073. Archivado (PDF) desde el original el 17 de diciembre de 2014 . Consultado el 18 de septiembre de 2014 . [1]
44. Potts, Daniel; Steidl, Gabriele ; Tasche, Manfred (2001). "Transformadas rápidas de Fourier para datos no equiespaciados: un tutorial" (PDF) . En Benedetto, JJ; Ferreira, P. (eds.). Teoría moderna del muestreo: matemáticas y aplicaciones . Birkhäuser . Archivado (PDF) desde el original el 26 de septiembre de 2007.
45. Burgess, Richard James (2014). Historia de la producción musical. Oxford University Press. ISBN 978-0199357178. Recuperado el 1 de agosto de 2019 .
46. Chu, Eleanor; George, Alan (11 de noviembre de 1999) [11 de noviembre de 1999]. "Capítulo 16". Dentro de la caja negra de FFT: algoritmos de transformada rápida de Fourier en serie y en paralelo . CRC Press . págs. 153–168. ISBN 978-1-42004996-1.
47. Fernandez-de-Cossio Diaz, Jorge; Fernandez-de-Cossio, Jorge (2012-08-08). "Cálculo de la distribución de masas centrales de picos isotópicos mediante la transformada de Fourier". Química analítica . 84 (16): 7052–7056. doi :10.1021/ac301296a. ISSN  0003-2700. PMID  22873736.
48. Minenna, Marcello (octubre de 2008). "Un método de transformada de Fourier revisado y estable para modelos de difusión por salto afín". Journal of Banking and Finance . 32 (10): 2064–2075. doi :10.1016/j.jbankfin.2007.05.019.
49. Cormen, Thomas H.; Nicol, David M. (1998). "Realización de FFT fuera del núcleo en sistemas de discos paralelos". Computación paralela . 24 (1): 5–20. CiteSeerX 10.1.1.44.8212 . doi :10.1016/S0167-8191(97)00114-2. S2CID  14996854. 
50. Dutt, Alok; Rokhlin, Vladimir (1993-11-01). "Transformadas rápidas de Fourier para datos no equiespaciados". Revista SIAM de informática científica . 14 (6): 1368–1393. Bibcode :1993SJSC...14.1368D. doi :10.1137/0914081. ISSN  1064-8275.
51. Rockmore, Daniel N. (2004). "Progreso reciente y aplicaciones en las FFT de grupo". En Byrnes, Jim (ed.). Álgebra no conmutativa computacional y aplicaciones . NATO Science Series II: Matemáticas, física y química. Vol. 136. Springer Netherlands. págs. 227–254. CiteSeerX 10.1.1.324.4700 . doi :10.1007/1-4020-2307-3_9. ISBN.  978-1-4020-1982-1.S2CID1412268  .​
52. Ryo, Asaka; Kazumitsu, Sakai; Ryoko, Yahagi (2020). "Circuito cuántico para la transformada rápida de Fourier". Procesamiento de información cuántica . 19 (277): 277. arXiv : 1911.03055 . Código Bibliográfico :2020QuIP...19..277A. doi :10.1007/s11128-020-02776-5. S2CID  207847474.
53. "Bibliotecas de rendimiento de Arm". Arm . 2020 . Consultado el 16 de diciembre de 2020 .
54. "Lista completa de bibliotecas FFT de C/C++". Comunidad VCV . 2020-04-05 . Consultado el 2021-03-03 .

Lectura adicional

• Brigham, Elbert Oran (1974). La transformada rápida de Fourier (edición anterior). Englewood Cliffs, NJ: Prentice-Hall . ISBN 978-0-13-307496-3.
• 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 (Mass.): 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 rápida discreta de Fourier". Actas de ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing. Vol. iii. IEEE . págs. III/445–III/448. doi :10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. Número de identificación del sujeto  42639206.
• Johnson, Steven G.; Frigo, Matteo (enero de 2007). "Una FFT de radio dividido 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) desde el original el 26 de mayo de 2005.
• 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ág. 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. doi :10.1109/TAU.1969.1162040. ISSN  0018-9278.(NB. Contiene bibliografía extensa.)
• 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.

Enlaces externos

• Transformada rápida de Fourier para multiplicación de polinomios: algoritmo rápido de Fourier
• Transformada rápida de Fourier (FFT) – Programación FFT en C++ – Algoritmo Cooley–Tukey
• Documentación en línea, enlaces, libro y código
• Sri Welaratna, "Treinta años de analizadores FFT Archivado el 12 de enero de 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
• Código FFT de ALGLIB: una biblioteca de procesamiento de datos y análisis numérico multilingüe (VBA, C++, Pascal, etc.) con licencia dual/GPL
• SFFT: Transformada rápida de Fourier dispersa: algoritmo FFT de tiempo sublineal disperso 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 interactiva a las transformadas de Fourier y los métodos de 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