Transformada rápida de Fourier

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

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

Un análisis de Fourier discreto de una suma de ondas coseno 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 lenta para ser práctica. Una FFT calcula rápidamente tales 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 desde , que surge si uno simplemente aplica la definición de DFT, hasta , donde n es el tamaño de los datos. La diferencia de velocidad puede ser enorme, especialmente para conjuntos de datos largos donde n puede ser de miles o millones. En presencia de error de redondeo , muchos algoritmos FFT son mucho más precisos que evaluar la definición DFT directa o indirectamente. Existen muchos algoritmos FFT diferentes basados ​​en una amplia gama de teorías publicadas, desde la simple aritmética 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 transformación de Fourier.

Las transformadas rápidas de Fourier se utilizan ampliamente para aplicaciones en ingeniería, música, ciencias y matemáticas. Las ideas básicas se popularizaron en 1965, pero algunos algoritmos se derivaron ya en 1805. ^[1] En 1994, Gilbert Strang describió la FFT como "el algoritmo numérico más importante de nuestra vida", ^{[3] [4]} y Fue incluido en el Top 10 de 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 los primos , n . Muchos algoritmos FFT dependen sólo del hecho de que es una raíz primitiva enésima de la unidad y , por lo tanto, pueden aplicarse a transformaciones análogas sobre cualquier campo finito , como las transformaciones de teoría de números . Dado que la DFT inversa es igual que la DFT, pero con el signo opuesto en el exponente y un factor 1/ n , cualquier algoritmo FFT se puede adaptar fácilmente. ${\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 muestras; ^{[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 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 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 análisis de experimentos. En 1942, GC Danielson y Cornelius Lanczos publicaron su versión para calcular DFT para cristalografía de rayos X , un campo donde el cálculo de las transformadas de Fourier presentaba un cuello de botella formidable. ^{[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 usar la "periodicidad" y aplicar un "truco de duplicación" a " duplicar [ n ] con sólo 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 realizadas por 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 sólo a los problemas de seguridad nacional, sino también a una amplia gama de problemas, incluido uno de interés inmediato para él, la determinación de las periodicidades de las orientaciones de espín en un cristal tridimensional. de Helio-3. ^[13] Garwin le dio la idea de Tukey a Cooley (ambos trabajaron 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 trabajó 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 siguiente década, 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}}$

La evaluación de esta definición requiere operaciones directamente : 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 hay pruebas conocidas de que una menor complejidad sea imposible. ^[dieciséis] ${\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 sumas complejas para puntos de datos. La evaluación de las sumas de la DFT implica directamente multiplicaciones y sumas complejas, de las cuales las operaciones se pueden salvar eliminando operaciones triviales como las multiplicaciones por 1, dejando alrededor de 30 millones de operaciones. Por el contrario, el algoritmo Radix-2 Cooley-Tukey, para n una potencia de 2, puede calcular el mismo resultado solo con multiplicaciones complejas (nuevamente, ignorando las simplificaciones de multiplicaciones por 1 y similares) y sumas complejas, en total alrededor de 30.000 operaciones. mil veces menos que con evaluación directa. En la práctica, el rendimiento real de las computadoras modernas suele estar dominado por factores distintos de la velocidad de las operaciones aritméticas y el análisis es un tema complicado (por ejemplo, ver 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

Con diferencia, la FFT más utilizada es el algoritmo Cooley-Tukey. Este es un algoritmo de divide y vencerás que descompone recursivamente una DFT de cualquier tamaño compuesto en muchas DFT más pequeñas de tamaños y , junto con multiplicaciones por raíces complejas de unidad tradicionalmente llamadas factores de giro (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) fue popularizado por una publicación de Cooley y Tukey en 1965, ^[12] pero más tarde se descubrió ^[1] que esos dos autores habían reinventado de forma independiente 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 transformación en dos partes de tamaño n/2 en cada paso y, por lo tanto, está limitado a potencias de dos tamaños, pero en general se puede utilizar cualquier factorización (como se hizo conocido tanto por Gauss como por Cooley/Tukey ^[1] ). Estos se denominan casos de base 2 y de 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 recursividad 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 algoritmos FFT distintos de Cooley-Tukey.

Porque con coprimo y , se puede utilizar 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 de giro. El algoritmo de Rader-Brenner (1976) ^[20] es una factorización tipo Cooley-Tukey pero con factores de giro puramente imaginarios, que reducen las multiplicaciones a costa de mayores sumas y una estabilidad numérica reducida ; Más tarde fue reemplazada por la variante de base dividida de Cooley-Tukey (que logra el mismo recuento de multiplicaciones pero con menos sumas y sin sacrificar la precisión). Los algoritmos que factorizan recursivamente la DFT en operaciones más pequeñas distintas a las DFT incluyen los algoritmos Bruun y QFT. (Los algoritmos Rader-Brenner ^[20] y QFT se propusieron para tamaños de potencia de dos, pero es posible que puedan adaptarse al compuesto general n . 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 coeficiente real 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 (si es que hay alguna) multiplicaciones, por lo que Winograd puede ser se utiliza para obtener FFT de multiplicación mínima y, a menudo, se utiliza para encontrar algoritmos eficientes para factores pequeños. De hecho, Winograd demostró que la DFT se puede calcular sólo con multiplicaciones irracionales, lo que lleva a un límite inferior alcanzable en el número de multiplicaciones para potencias de dos tamaños; esto tiene el costo 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 utiliza PFA, así como 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 puede calcularse mediante un par de FFT ordinarias a través de la teorema de convolución (aunque Winograd utiliza otros métodos de convolución). Otra FFT de tamaño principal 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 puede rellenarse con ceros a una potencia de dos y evaluarse mediante FFT Cooley-Tukey radix-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 hexagonal rápida de Fourier (HFFT) tiene como objetivo calcular una FFT eficiente para los datos muestreados hexagonalmente mediante el uso de un nuevo esquema de direccionamiento para cuadrículas hexagonales, llamado Array Set Addressing (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 (ver, 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 real e imaginaria son los elementos pares/impares de los datos reales originales), seguida de operaciones de posprocesamiento. ${\displaystyle O(n)}$

Alguna vez se creyó que las DFT de entrada real podrían calcularse de manera más eficiente mediante la transformada discreta de Hartley (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 correspondiente (FHT) para el mismo número de entradas. ^[23] El algoritmo de Bruun (arriba) es otro método que se propuso inicialmente para aprovechar entradas reales, pero no ha resultado popular.

Existen más especializaciones de FFT para los casos de datos reales que tienen simetría par/impar , en cuyo caso se puede obtener otro factor de aproximadamente dos en tiempo y memoria y la DFT se convierte en la 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 mediante FFT de datos reales combinados con procesamiento previo y posterior. ${\displaystyle O(n)}$

Problemas computacionales

Límites de complejidad y operaciones

Problema no resuelto 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 de larga data es demostrar los límites inferiores de la complejidad y el recuento exacto de operaciones de las transformadas rápidas de Fourier, y quedan muchos problemas abiertos. No está rigurosamente demostrado si las DFT realmente requieren (es decir, orden o mayores) operaciones, incluso para el caso simple de potencia de dos tamaños, aunque no se conocen algoritmos con menor complejidad. En particular, el recuento de operaciones aritméticas suele ser el foco de estas preguntas, aunque el rendimiento real en las computadoras modernas está determinado por muchos otros factores, como la caché o la optimización de 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 sólo 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 & 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 algunos supuestos restrictivos sobre los algoritmos. En 1973, Morgenstern ^[27] demostró un límite inferior en el recuento de sumas para algoritmos donde las constantes multiplicativas tienen magnitudes acotadas (lo cual es cierto para la mayoría de los algoritmos FFT, pero no para todos). Pan (1986) ^[28] demostró un límite inferior suponiendo 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 potencia de dos n , Papadimitriou (1979) ^[29] argumentó que el número de sumas de números complejos logrados por los algoritmos de Cooley-Tukey es óptimo bajo ciertos supuestos en la gráfica del algoritmo (sus supuestos 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 sumas reales, aunque esto no es un límite estricto porque se requieren sumas adicionales como parte de las multiplicaciones de números complejos). Hasta ahora, ningún algoritmo FFT publicado ha logrado menos sumas que las de números complejos ( o su equivalente) para potencia de dos n . ${\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 llamado "complejidad aritmética" (aunque en este contexto lo que se considera es el recuento exacto y no la complejidad asintótica). Una vez más, no se ha demostrado ningún límite inferior estricto. Sin embargo, desde 1968, el recuento más bajo publicado para 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 la base dividida para n ≥ 256 ) es óptima para n ≤ 512 bajo restricciones adicionales en los posibles algoritmos (gráficos de flujo tipo base dividida con factores multiplicativos de módulo unitario), mediante reducción a un problema de teorías de módulo de satisfacibilidad que se puede resolver mediante fuerza bruta (Haynal & 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 ordinario de datos complejos, 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 discretas de coseno , las transformadas discretas de Hartley , etc., que cualquier mejora en una de ellas conduciría inmediatamente a mejoras en las demás ( 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. Dichos algoritmos intercambian el error de aproximación por una mayor velocidad u otras propiedades. Por ejemplo, un algoritmo FFT aproximado de Edelman et al. (1999) ^[33] logra menores requisitos de comunicación para la computación paralela con la ayuda de un método multipolar rápido . Una FFT aproximada basada en wavelets realizada por Guo y Burrus (1996) ^[34] tiene en cuenta entradas/salidas escasas (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 resultados de 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 propia matriz de Fourier en lugar de la compresibilidad (escasez) de los datos. Por el contrario, si los datos son escasos, es decir, si sólo 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 ²² ) usando un algoritmo probabilístico aproximado (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 la aritmética de punto flotante de precisión finita, pero estos errores suelen ser 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 del algoritmo Cooley-Tukey es , en comparación con la fórmula ingenua DFT, ^[18] donde 𝜀 es la precisión relativa de punto flotante de la máquina. De hecho, los errores cuadráticos medios (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 giro utilizados en la FFT (es decir, los valores de la función trigonométrica ), y no es inusual que implementaciones imprudentes de FFT tengan una precisión mucho peor, por ejemplo, si utilizan datos inexactos. Fórmulas de recurrencia trigonométrica . Algunas FFT distintas de Cooley-Tukey, como el algoritmo de 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 aritmética de punto fijo , los errores de precisión finita acumulados por los algoritmos FFT son peores, y los errores rms crecen como en el algoritmo Cooley-Tukey (Welch, 1969). ^[38] Lograr esta precisión requiere una cuidadosa atención al escalado para minimizar la pérdida de precisión, y los algoritmos FFT de punto fijo implican un reescalado en cada etapa intermedia de descomposiciones como Cooley-Tukey. ${\textstyle O({\sqrt {n}})}$

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

FFT multidimensionales

Como se define en el artículo DFT multidimensional , el 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 d -dimensional mediante un conjunto de d sumaciones anidadas ( para cada j ), donde la división se realiza por elementos. De manera equivalente, es la composición de una secuencia de d conjuntos de DFT unidimensionales, realizadas en 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 común, conocido como algoritmo fila-columna (después del caso bidimensional, a continuación). Es decir, uno simplemente 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 (en realidad, cualquier orden funciona). Se demuestra fácilmente que este método tiene la complejidad habitual, donde se transforma el número total de puntos de datos. En particular, hay n / n ₁ transformadas 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 (respectivamente columnas), agrupando las filas transformadas resultantes (respectivamente columnas) como otra matriz, y luego realizar la FFT en cada una de las columnas (respectivamente 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 para la localidad de caché agrupar las dimensiones de forma recursiva. Por ejemplo, una FFT tridimensional podría realizar primero FFT bidimensionales de cada "corte" plano para cada n ₁ fijo y luego realizar las FFT unidimensionales a lo largo de la dirección n ₁ . De manera más general, un algoritmo asintóticamente óptimo sin conciencia de caché consiste en dividir recursivamente las dimensiones en dos grupos y que se transforman recursivamente (redondeando si d no es par) (ver Frigo y Johnson, 2005). ^[17] Aún así, esto sigue siendo una variación sencilla del algoritmo fila-columna que en última instancia requiere solo un algoritmo FFT unidimensional como caso base, y aún tiene complejidad. Otra variación más es realizar transposiciones de matrices entre transformaciones de dimensiones posteriores, de modo que las transformaciones operen en datos contiguos; Esto es especialmente importante para situaciones de memoria distribuida y fuera del núcleo donde el acceso a datos no contiguos requiere 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 tienen complejidad. Quizás la FFT sin filas y columnas más simple es el algoritmo FFT de base vectorial , que es una generalización del algoritmo ordinario de Cooley-Tukey donde se dividen las dimensiones de la transformación por un vector de raíces en cada paso. (Esto también puede tener beneficios de caché). El caso más simple de vector-radix es cuando todas las raíces son iguales (por ejemplo, vector-radix-2 divide todas las dimensiones por dos), pero esto no es necesario. La base vectorial con una sola base no unitaria a la vez, es decir , es esencialmente un algoritmo de fila-columna. Otros métodos más complicados incluyen algoritmos de transformación polinómica debidos a Nussbaumer (1977), ^[40] que ven la transformación en términos de convoluciones y productos polinomiales. Véase 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 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 armónico esférico 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 en 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.

Varios grupos también han publicado algoritmos "FFT" para datos no equiespaciados, como se revisa 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 a la misma (una transformada de Fourier discreta no uniforme , o NDFT, que a menudo se calcula solo aproximadamente). De manera más general, existen 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 deriva del hecho de que ha hecho que trabajar en el dominio de la frecuencia sea igualmente factible desde el punto de vista computacional que 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 enteros grandes y multiplicación de polinomios,
• multiplicación eficiente de matrices-vectores para Toeplitz , matrices circulantes y otras matrices estructuradas,
• algoritmos de filtrado (ver métodos de superposición-agregar y superposición-guardar ),
• algoritmos rápidos para transformaciones discretas de coseno o seno (por ejemplo, DCT rápido utilizado para codificación y decodificación JPEG y MPEG / MP3 ),
• aproximación rápida de Chebyshev ,
• resolver ecuaciones en diferencias ,
• Cálculo de distribuciones isotópicas . ^[47]
• Modulación y demodulación de símbolos de datos complejos mediante multiplexación por división de frecuencia ortogonal (OFDM) para 5G, LTE, Wi-Fi, DSL y otros sistemas de comunicación modernos.

Marcello Minenna desarrolló una aplicación original de la FFT en las finanzas , particularmente en la valoración de opciones . ^[48]

Áreas de investigación

Grandes FFT

Con la explosión del big data 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 MRI, es necesario calcular DFT para puntos y/o frecuencias de la cuadrícula espaciados de manera no uniforme. 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, incluido el no cíclico, tiene una expansión en términos de una base de elementos matriciales irreducibles. Sigue siendo un área activa de investigación encontrar un algoritmo eficiente para realizar este cambio de base. Aplicaciones que incluyen expansión armónica esférica eficiente , análisis de ciertos procesos de Markov , robótica, etc. ^[51]

FFT cuánticas

El rápido algoritmo de Shor para la factorización de enteros en una computadora cuántica tiene una subrutina para calcular la DFT de un vector binario. Esto se implementa como una secuencia de puertas cuánticas de 1 o 2 bits ahora conocida 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 idiomática

Ver también

Algoritmos relacionados con FFT:

• Permutación de inversión de bits

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

Implementaciones de FFT:

• ALGLIB : una biblioteca C++ y C# con licencia dual/GPL (que también admite otros lenguajes), con implementación FFT real/compleja
• FFTPACK : otra biblioteca Fortran FFT (dominio público)
• Específico de la arquitectura:
  • Bibliotecas de rendimiento del brazo ^[53]
  • Primitivas de rendimiento integrado de Intel
  • Biblioteca del núcleo matemático 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 FFT
• Música espectral (implica la aplicación del análisis DFT a la composición musical)
• Analizador de espectro : cualquiera de los varios dispositivos que realizan análisis de espectro, a menudo a través de un DFT
• Series de tiempo
• 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. Préstamo de furgoneta, Charles (1992). "Marcos computacionales para la transformada rápida de Fourier ". SIAM .
3. Strang, Gilbert (mayo-junio de 1994). "Ondas". Científico americano . 82 (3): 250–255. JSTOR  29775194.
4. Kent, Ray D.; Leer, Charles (2002). Análisis Acústico del Habla . Aprendizaje singular/Thomson. ISBN 0-7693-0112-6.
5. Dongarra, Jack; Sullivan, Francis (enero de 2000). "Introducción de los editores invitados a los 10 algoritmos principales". Computación en ciencia e ingeniería . 2 (1): 22–23. Código Bib : 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 (1 de septiembre de 1985). "Gauss y la historia de la rápida transformada 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 No. 35 de la Oficina de Suelos del Commonwealth . 142 (3585): 90–92. Código Bib :1938Natur.142...90F. doi :10.1038/142090a0. S2CID  23501205.
9. Danielson, Gordon C .; Lanczos, Cornelio (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". Revista del Instituto Franklin . 233 (4): 365–380. doi :10.1016/S0016-0032(42)90767-1.
10. Lanczos, Cornelio (1956). Análisis Aplicado . Prentice Hall .
11. Cooley, James W .; Lewis, Peter AW; Welch, Peter D. (junio de 1967). "Notas históricas sobre la rápida transformada de Fourier". Transacciones IEEE sobre audio y electroacústica . 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 automático 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 lograr un uso amplio de una nueva técnica" (PDF) . Transacciones IEEE sobre audio y electroacústica . 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 puede utilizar toda la familia". Computación en ciencia e ingeniería . 2 (1): 60–64. Código Bib : 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 raíz dividida modificada con menos operaciones aritméticas". Transacciones IEEE sobre procesamiento de señales . 55 (1): 111-119. Código Bib : 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. Código Bib : 2005IEEEP..93..216F. CiteSeerX 10.1.1.66.3097 . doi :10.1109/jproc.2004.840301. S2CID  6644892. Archivado (PDF) desde el original el 7 de febrero de 2005. 
18. Caballero, W. Morven; Sandé, G. (1966). "Transformaciones rápidas de Fourier, por diversión y ganancias". 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 transformación rápida de Fourier". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 24 (3): 264–266. doi :10.1109/TASSP.1976.1162805.
21. Winograd, Shmuel (1978). "Sobre el cálculo de la transformada discreta de Fourier". 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 discreta de Fourier". 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 de valor real". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 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 con valor real "". Transacciones IEEE sobre acústica, voz 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 longitud-2 ⁿ DFT". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 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 DFT de longitud 2 ⁿ y su conexión con algoritmos prácticos". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 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, Víctor Ya. (2 de enero de 1986). "La compensación entre la complejidad aditiva y la asincronicidad de los algoritmos lineales y bilineales". Cartas de procesamiento de información . 22 (1): 11-14. doi :10.1016/0020-0190(86)90035-9 . Consultado el 31 de octubre de 2017 .
29. Papadimitriou, Christos H. (1979). "Optimidad 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 FFT reales y convoluciones de longitud 2 ^k ". Informática . 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 Bib : 2011arXiv1103.5740H. doi :10.3233/SAT190084. S2CID  173109. Archivado desde el original (PDF) el 26 de abril de 2012.
32. Duhamel, Pierre; Vetterli, Martín (1990). "Transformadas rápidas de Fourier: una revisión del tutorial y un estado del arte". Procesamiento de la señal . 19 (4): 259–299. doi :10.1016/0165-1684(90)90158-U.
33. Edelman, Alan; McCorquodale, Peter; Toledo, Siván (1999). "¿La futura transformada rápida de Fourier?" (PDF) . Revista SIAM de Computación 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). Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F. (eds.). "Transformada de Fourier rápida y aproximada mediante transformada wavelets". Actas de SPIE . Aplicaciones Wavelet en el procesamiento de señales e imágenes IV. 2825 : 250–259. Código Bib : 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 la señal . 41 (3): 261–277. doi :10.1016/0165-1684(94)00103-7.
36. Hassanieh, Haitham; Indyk, Piotr ; Katabi, Dina; Precio, Eric (enero de 2012). "Algoritmo simple y práctico para la transformada dispersa de Fourier" (PDF) . Simposio ACM-SIAM sobre Algoritmos Discretos . Archivado (PDF) desde el original el 4 de marzo de 2012.(NB. Consulte también la página web de sFFT).
37. Schatzman, James C. (1996). "Precisión de la transformada discreta de Fourier y la transformada rápida de Fourier". Revista SIAM de Computación Científica . 17 (5): 1150-1166. Código bibliográfico : 1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184 . doi :10.1137/s1064827593247023. 
38. Welch, Peter D. (1969). "Un análisis de errores de transformada rápida de Fourier de punto fijo". Transacciones IEEE sobre audio y electroacústica . 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 ACM sobre teoría de la informática - STOC '95 . Kyoto, Japón. págs. 407–416. doi :10.1145/225058.225167. ISBN 978-0897917186. S2CID  15512806.{{cite book}}: CS1 maint: location missing publisher (link)
40. Nussbaumer, Henri J. (1977). "Filtrado digital mediante transformadas polinómicas". Letras de Electrónica . 13 (13): 386–387. Código bibliográfico : 1977ElL....13..386N. doi :10.1049/el:19770280.
41. Mohlenkamp, ​​Martín J. (1999). "Una transformación rápida para armónicos esféricos" (PDF) . Revista de análisis y aplicaciones de Fourier . 5 (2–3): 159–184. CiteSeerX 10.1.1.135.9830 . doi :10.1007/BF01261607. S2CID  119482349. Archivado (PDF) desde el original el 6 de mayo de 2017 . Consultado el 11 de enero de 2018 . 
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 Computación Científica . 27 (6): 1903-1928. Código Bib : 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). La historia de la producción musical. Prensa de la Universidad de Oxford. ISBN 978-0199357178. Consultado el 1 de agosto de 2019 .
46. Chu, Leonor; 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 paralelo" . Prensa CRC . págs. 153-168. ISBN 978-1-42004996-1.
47. Fernández-de-Cossio Díaz, Jorge; Fernández-de-Cossio, Jorge (8 de agosto de 2012). "Cálculo de la distribución de masa central del pico isotópico mediante 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 estable y revisado para modelos de difusión de salto afín". Revista de Banca y Finanzas . 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 (1 de noviembre de 1993). "Transformadas rápidas de Fourier para datos no equiespaciados". Revista SIAM de Computación Científica . 14 (6): 1368-1393. Código bibliográfico : 1993SJSC...14.1368D. doi :10.1137/0914081. ISSN  1064-8275.
51. Rockmore, Daniel N. (2004). "Progresos recientes y aplicaciones en FFT grupales". En Byrnes, Jim (ed.). Álgebra computacional no conmutativa y aplicaciones . Serie Científica II de la OTAN: Matemáticas, Física y Química. vol. 136. Springer Países Bajos. págs. 227-254. CiteSeerX 10.1.1.324.4700 . doi :10.1007/1-4020-2307-3_9. ISBN  978-1-4020-1982-1. S2CID  1412268.
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 Bib : 2020QuiP...19..277A. doi :10.1007/s11128-020-02776-5. S2CID  207847474.
53. "Bibliotecas de rendimiento de Arm". Brazo . 2020 . Consultado el 16 de diciembre de 2020 .
54. "Lista completa de bibliotecas FFT de C/C++". Comunidad VCV . 2020-04-05 . Consultado el 3 de marzo de 2021 .

Otras lecturas

• Brigham, E. Orán (2002). La transformada rápida de Fourier . Nueva York: Prentice-Hall .
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 30: Polinomios y FFT". Introducción a los algoritmos (2 ed.). Prensa del MIT / McGraw-Hill . ISBN 0-262-03293-7.
• Elliott, Douglas F.; Rao, K. Ramamohan (1982). Transformaciones rápidas: algoritmos, análisis, aplicaciones . Nueva York, Estados Unidos: Academic Press .
• Guo, Haitao; Sitton, Gary A.; Burrus, Charles Sidney (1994). "La transformada rápida y discreta de Fourier". Actas de ICASSP '94. Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales . vol. 3. págs. 445–448. doi :10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID  42639206.
• Johnson, Steven G.; Frigo, Mateo (2007). "Una FFT de base dividida modificada con menos operaciones aritméticas" (PDF) . Transacciones IEEE sobre procesamiento de señales . 55 (1): 111-119. Código Bib : 2007ITSP...55..111J. CiteSeerX  10.1.1.582.5497 . doi :10.1109/tsp.2006.882087. S2CID  14772428. Archivado (PDF) desde el original el 26 de mayo de 2005.
• Prensa, William H.; Teukolsky, Saúl A.; Vetterling, William T.; Flannery, Brian P. (2007). "Capítulo 12. Transformada rápida de Fourier". Recetas numéricas: el arte de la informática científica (3 ed.). Nueva York, Estados Unidos: Cambridge University Press . ISBN 978-0-521-88068-8.
• Singleton, Richard Collom (junio de 1969). "Una breve bibliografía sobre la transformada rápida de Fourier". Número especial sobre la transformada rápida de Fourier . vol. AU-17. Grupo de Audio y Electroacústica IEEE. págs. 166-169. doi :10.1109/TAU.1969.1162029.(NB. Contiene una extensa bibliografía.)
• Elena Prestini: "La evolución del análisis armónico aplicado", Springer, ISBN 978-0-8176-4125-2 (2004), Sec.3.10 'Gauss y los asteroides: historia de la FFT'.

enlaces externos

• Transformada rápida de Fourier para multiplicación polinómica: algoritmo rápido de Fourier
• Fast Fourier Transforms , libro en línea Connexions editado por Charles Sidney Burrus, con capítulos de Charles Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo y Steven G. Johnson (2008)
• Transformada rápida de Fourier - FFT - Programación FFT en C++ - el 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 ", Sonido y vibración (enero de 1997, número del 30 aniversario): una revisión histórica de los dispositivos FFT de hardware
• Código ALGLIB FFT: una biblioteca de análisis numérico y procesamiento de datos en varios idiomas con licencia dual/GPL (VBA, C++, Pascal, etc.)
• SFFT: Transformada rápida dispersa de Fourier: algoritmo FFT disperso (tiempo sublineal), 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 FFT