Transformada rápida de Fourier - Fast Fourier transform

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. 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 tales transformaciones factorizando la matriz DFT en un producto de factores escasos (en su mayoría cero). Como resultado, logra reducir la complejidad de calcular la DFT desde , que surge si uno simplemente aplica la definición de DFT, a , donde está 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 de FFT son mucho más precisos que evaluar la definición de DFT directa o indirectamente. Hay 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 . ${\ Displaystyle O \ left (N ^ {2} \ right)}$${\ Displaystyle O (N \ log N)}$${\ Displaystyle N}$

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 habían derivado ya en 1805. En 1994, Gilbert Strang describió la FFT como "el algoritmo numérico más importante de nuestra vida", y se incluyó en los 10 mejores algoritmos del siglo XX. por la revista IEEE Computing in Science & Engineering .

Los algoritmos de FFT más conocidos dependen de la factorización de N , pero hay FFT con complejidad O ( N  log  N ) para todo N , incluso para N primo . 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 campo finito , como las transformadas teóricas 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 de FFT puede adaptarse fácilmente.  ${\ Displaystyle e ^ {- 2 \ pi i / N}}$

Historia

El desarrollo de algoritmos rápidos para DFT se remonta al trabajo inédito de Carl Friedrich Gauss en 1805 cuando lo necesitaba para interpolar la órbita de los asteroides Pallas y Juno a partir de observaciones de muestra. Su método fue muy similar al publicado en 1965 por James Cooley y John Tukey , a quienes generalmente se les atribuye la invención del algoritmo genérico FFT moderno. Si bien el trabajo de Gauss fue anterior incluso a los resultados de Joseph Fourier en 1822, no analizó el tiempo de cálculo y finalmente utilizó otros métodos para lograr su objetivo.

Entre 1805 y 1965, otros autores publicaron algunas versiones de FFT. Frank Yates en 1932 publicó su versión llamada algoritmo de interacción , que proporcionaba un cálculo eficiente de las transformadas de Hadamard y Walsh . 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 DFT para cristalografía de rayos X , un campo donde el cálculo de las transformadas de Fourier presentaba un cuello de botella formidable. Si bien muchos métodos en el pasado se habían enfocado 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" para "duplicar [N] con solo algo más del doble de la mano de obra ”, aunque al igual que Gauss no analizaron que esto conllevara un escalado. ${\ Displaystyle O \ left (N ^ {2} \ right)}$${\ Displaystyle O (N \ log N)}$

James Cooley y John Tukey redescubrieron independientemente estos algoritmos anteriores 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. 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 involucró 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 una discusión con Tukey, Richard Garwin reconoció la aplicabilidad general del algoritmo no solo a problemas de seguridad nacional, sino también a una amplia gama de problemas, incluido uno de interés inmediato para él, que determina las periodicidades de las orientaciones de espín en un cristal tridimensional. de Helio-3. Garwin le dio la idea de Tukey a Cooley (ambos trabajaron en los laboratorios Watson de IBM ) para su implementación. Cooley y Tukey publicaron el artículo en un período relativamente corto de seis meses. 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 próxima década, convirtió a FFT en uno de los algoritmos indispensables en el procesamiento de señales digitales. ${\ Displaystyle O (N \ log N)}$

Definición

Vamos , ..., ser números complejos . La DFT está definida por la fórmula ${\ Displaystyle x_ {0}}$${\ Displaystyle x_ {N-1}}$

${\ Displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- i2 \ pi kn / N} \ qquad k = 0, \ ldots, N-1, }$

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

Evaluar esta definición directamente requiere 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 las operaciones. Todos los algoritmos FFT conocidos requieren operaciones , aunque no hay pruebas conocidas de que una puntuación de complejidad más baja sea imposible. ${\ Displaystyle O \ left (N ^ {2} \ right)}$${\ Displaystyle O (N \ log N)}$${\ Displaystyle \ Theta (N \ log N)}$

Para ilustrar los ahorros de una FFT, considere el recuento de multiplicaciones y sumas complejas para N = 4096 puntos de datos. La evaluación de las sumas de la DFT implica directamente N ² multiplicaciones complejas y N ( N - 1) adiciones complejas, de las cuales se pueden guardar operaciones eliminando operaciones triviales como multiplicaciones por 1, dejando alrededor de 30 millones de operaciones. En contraste, el algoritmo radix-2 Cooley-Tukey , para N una potencia de 2, puede calcular el mismo resultado con solo ( N / 2) log ₂ ( N ) multiplicaciones complejas (nuevamente, ignorando las simplificaciones de multiplicaciones por 1 y similares) y adiciones complejas de N  log ₂ ( N ), en total unas 30.000 operaciones, mil veces menos que con la evaluación directa. En la práctica, el rendimiento real en las computadoras modernas generalmente está dominado por factores distintos a la velocidad de las operaciones aritméticas y el análisis es un tema complicado (por ejemplo, ver Frigo & Johnson , 2005), pero la mejora general de a permanece. ${\ Displaystyle O (N)}$${\ Displaystyle O \ left (N ^ {2} \ right)}$${\ Displaystyle O (N \ log N)}$

Algoritmos

Algoritmo de Cooley-Tukey

Con mucho, la FFT más utilizada es el algoritmo de Cooley-Tukey. Este es un algoritmo de divide y vencerás que descompone de forma recursiva una DFT de cualquier tamaño compuesto en muchas DFT más pequeñas de tamaños y , junto con las multiplicaciones por raíces complejas de unidad, tradicionalmente llamadas factores twiddle (según Gentleman y Sande, 1966). ${\ Displaystyle N = N_ {1} N_ {2}}$${\ Displaystyle N_ {1}}$${\ Displaystyle 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, pero más tarde se descubrió que esos dos autores habían reinventado de forma independiente un algoritmo conocido por Carl Friedrich Gauss alrededor de 1805 (y posteriormente redescubierto varias veces en formas limitadas).

El uso más conocido del algoritmo Cooley-Tukey es dividir la transformación en dos piezas de tamaño N / 2 en cada paso y, por lo tanto, está limitado a potencias de dos tamaños, pero cualquier factorización se puede utilizar en general (como se hizo conocido tanto por Gauss como por Cooley / Tukey). Estos se denominan casos radix-2 y mixed-radix , 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 de 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

Hay algoritmos de FFT distintos de Cooley-Tukey.

Para N = N ₁ N ₂ con coprimos N ₁ y N ₂ , 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 Rader-Brenner (1976) es una factorización similar a Cooley-Tukey pero con factores de giro puramente imaginarios, que reduce las multiplicaciones a costa de mayores adiciones y reducción de la estabilidad numérica ; más tarde fue reemplazada 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 Bruun y QFT . (Los algoritmos Rader-Brenner y QFT se propusieron para potencias de dos tamaños, 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 al interpretar la FFT como una factorización recursiva del polinomio z ^N  - 1, aquí en polinomios de coeficiente real de la forma z ^M  - 1 yz ^{2 M}  +  az ^M  + 1.

Otro punto de vista polinomial es explotado por el algoritmo FFT de Winograd, que factoriza z ^N  - 1 en polinomios ciclotómicos, que a menudo tienen coeficientes de 1, 0 o -1 y, por lo tanto, requieren pocas (si las hay) multiplicaciones, por lo que Winograd se puede utilizar para obtiene FFT de multiplicación mínima y se utiliza a menudo para encontrar algoritmos eficientes para factores pequeños. De hecho, Winograd demostró que la DFT se puede calcular con solo O ( N ) multiplicaciones irracionales, lo que conduce a un límite inferior alcanzable comprobado en el número de multiplicaciones para tamaños de potencia de dos; desafortunadamente, 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 hace uso del PFA, así como un algoritmo de Rader para FFT de tamaños principales .

El algoritmo de Rader , aprovechando 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 ser calculada por un par de FFT ordinarias a través de la teorema de convolución (aunque Winograd usa 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 se puede rellenar con ceros a una potencia de dos y evaluar mediante radix-2 Cooley-Tukey FFT, por ejemplo), a través de la identidad

${\ Displaystyle nk = - {\ frac {(kn) ^ {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 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_ {Nk} = X_ {k} ^ {*}}$

y se han diseñado algoritmos de FFT eficientes para esta situación (véase, por ejemplo, Sorensen, 1987). 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 O ( N ) post- operaciones de procesamiento.

Alguna vez se creyó que las DFT de entrada real podrían calcularse de manera más eficiente por medio de la transformada discreta de Hartley (DHT), pero posteriormente se argumentó que normalmente se puede encontrar un algoritmo DFT de entrada real especializado (FFT) que requiere menos operaciones que el algoritmo DHT correspondiente (FHT) para el mismo número de entradas. El algoritmo de Bruun (arriba) es otro método que se propuso inicialmente para aprovechar las entradas reales, pero no ha demostrado ser popular.

Hay más especializaciones de FFT para los casos de datos reales que tienen simetría par / impar , en cuyo caso uno puede ganar otro factor de aproximadamente dos en tiempo y memoria y la DFT se convierte en la (s) transformada (s) discreta 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 el pre y posprocesamiento O ( N ).

Problemas computacionales

Límites de complejidad y operaciones

Una cuestión fundamental de interés teórico desde hace mucho tiempo es demostrar límites inferiores en la complejidad y los recuentos exactos de operaciones de las transformadas rápidas de Fourier, y quedan muchos problemas abiertos. No está rigurosamente probado si las DFT realmente requieren operaciones Ω ( N  log  N ) (es decir, orden N  log  N o mayor), incluso para el caso simple de potencias 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 tales preguntas, aunque el rendimiento real en las computadoras modernas está determinado por muchos otros factores, como la optimización de la canalización de la CPU o la memoria caché .

Siguiendo el trabajo de Shmuel Winograd (1978), se conoce un límite inferior ajustado Θ ( N ) 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 potencia de dos de longitud . Además, se conocen algoritmos explícitos que logran este recuento (Heideman y Burrus , 1986; Duhamel, 1990). Sin embargo, estos algoritmos requieren demasiadas adiciones para ser prácticos, al menos en computadoras modernas con multiplicadores de hardware (Duhamel, 1990; Frigo & Johnson , 2005). ${\ Displaystyle 4N-2 \ log _ {2} ^ {2} (N) -2 \ log _ {2} (N) -4}$${\ Displaystyle N = 2 ^ {m}}$

No se conoce un límite inferior estricto en el número de adiciones requeridas, aunque se han demostrado límites inferiores bajo algunas suposiciones restrictivas sobre los algoritmos. En 1973, Morgenstern demostró un límite inferior Ω ( N  log  N ) en el recuento de sumas para los algoritmos en los que las constantes multiplicativas tienen magnitudes limitadas (lo cual es cierto para la mayoría de los algoritmos FFT, pero no para todos). Pan (1986) demostró un límite inferior Ω ( N  log  N ) 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) argumentó que el número de adiciones de números complejos logradas por los algoritmos de Cooley-Tukey es óptimo bajo ciertos supuestos en el gráfico 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 adiciones reales, aunque esto no es un límite estricto porque se requieren adiciones adicionales como parte de las multiplicaciones de números complejos). Hasta ahora, ningún algoritmo FFT publicado ha logrado menos que las adiciones de números complejos ( o su equivalente) para la energía-de-dos  N . ${\ Displaystyle N \ log _ {2} N}$${\ Displaystyle 2N \ log _ {2} N}$${\ Displaystyle 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 es el recuento exacto y no la complejidad asintótica lo que se está considerando). Una vez más, no se ha probado ningún límite inferior estricto. Sin embargo, desde 1968, el recuento más bajo publicado para la potencia de dos N se logró durante mucho tiempo mediante el algoritmo FFT de base dividida , que requiere multiplicaciones y adiciones reales para N > 1. Esto se redujo recientemente a (Johnson y Frigo, 2007; Lundy y Van Buskirk, 2007). Se demostró que un recuento ligeramente mayor (pero aún mejor que el radix dividido para N ≥ 256) es demostrablemente óptimo para N ≤ 512 bajo restricciones adicionales sobre los posibles algoritmos (diagramas de flujo similares a radix divididos con factores multiplicativos de módulo unitario), por reducción a un problema de teorías módulo de satisfacibilidad que se puede resolver mediante la fuerza bruta (Haynal y Haynal, 2011). ${\ Displaystyle 4N \ log _ {2} (N) -6N + 8}$${\ Displaystyle \ sim {\ frac {34} {9}} N \ log _ {2} N}$

La mayoría de los intentos de reducir o probar 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 los algoritmos para problemas relacionados, como las FFT de datos reales, las transformaciones discretas de coseno , las transformadas discretas de Hartley , etc., que cualquier mejora en uno de estos conduciría inmediatamente a mejoras en los demás ( Duhamel y Vetterli, 1990).

Aproximaciones

Todos los algoritmos de FFT discutidos anteriormente calculan la DFT exactamente (es decir, ignorando los errores de punto flotante ). Sin embargo, se han propuesto algunos algoritmos de "FFT" que calculan la DFT aproximadamente , con un error que puede hacerse arbitrariamente pequeño a expensas de un aumento de los 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) logra menores requisitos de comunicación para la computación en paralelo con la ayuda de un método multipolo rápido . Una FFT aproximada basada en ondículas de Guo y Burrus (1996) 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 las salidas de DFT se debe a Shentov et al. (1995). 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 (dispersión) de los datos. Por el contrario, si los datos son escasos, es decir, si solo K de N coeficientes de Fourier son distintos de cero, entonces la complejidad se puede reducir a O ( K  log ( N ) log ( N / K )), y esto se ha demostrado que conducir a aceleraciones prácticos en comparación con una FFT ordinario para N / K  > 32 en un a gran N ejemplo ( N  = 2 ²² ) utilizando un algoritmo aproximado probabilística (que estima los mayores K coeficientes a varios lugares decimales).

Precisión

Los algoritmos FFT tienen errores cuando se utiliza 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 para el algoritmo de Cooley-Tukey es O ( ε log N ), en comparación con O ( εN ^3/2 ) para la fórmula DFT ingenua, donde ε es la precisión relativa del punto flotante de la máquina. De hecho, los errores de raíz cuadrática media (rms) son mucho mejores que estos límites superiores, siendo solo O ( ε √ log N ) para Cooley-Tukey y O ( ε √ N ) para la DFT ingenua (Schatzman, 1996). Sin embargo, estos resultados 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 las implementaciones de FFT imprudentes tengan una precisión mucho peor, por ejemplo, si usan fórmulas de recurrencia trigonométricas inexactas. . Algunas FFT distintas de Cooley-Tukey, como el algoritmo Rader-Brenner, son intrínsecamente menos estables.

En aritmética de coma fija , los errores de precisión finita acumulados por los algoritmos FFT son peores, con errores rms creciendo como O ( √ N ) para el algoritmo Cooley-Tukey (Welch, 1969). Lograr esta precisión requiere una atención cuidadosa al escalado para minimizar la pérdida de precisión, y los algoritmos de FFT de punto fijo implican un cambio de escala en cada etapa intermedia de descomposiciones como Cooley-Tukey.

Para verificar la exactitud de una implementación de FFT, se pueden obtener garantías rigurosas en tiempo O ( N  log  N ) mediante un procedimiento simple que verifica las propiedades de linealidad, impulso-respuesta y desplazamiento de tiempo de la transformada en entradas aleatorias (Ergün, 1995) .

FFT multidimensionales

Como se define en el artículo de 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 d- dimensional de índices mediante un conjunto de d sumas anidadas (sobre para cada j ), donde la división n / N , definida como , se realiza por elementos. De manera equivalente, es la composición de una secuencia de d conjuntos de DFT unidimensionales, realizados a lo largo de una dimensión a la vez (en cualquier orden). ${\ Displaystyle \ mathbf {n} = \ left (n_ {1}, \ ldots, n_ {d} \ right)}$${\ Displaystyle n_ {j} = 0 \ ldots N_ {j} -1}$${\ Displaystyle \ 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 (o en realidad, cualquier orden funciona) . Se muestra fácilmente que este método tiene la complejidad O ( N  log  N ) habitual , donde es el número total de puntos de datos transformados. En particular, hay transformadas N / N ₁ de tamaño N ₁ , etcétera, por lo que la complejidad de la secuencia de FFT es: ${\ Displaystyle N = N_ {1} \ cdot N_ {2} \ cdot \ cdots \ cdot N_ {d}}$

${\ Displaystyle {\ begin {alineado} & {\ 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 {alineado}}}$

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), agrupando 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 resultado final. ${\ Displaystyle n_ {1} \ times n_ {2}}$ ${\ Displaystyle n_ {1} \ times n_ {2}}$

En más de dos dimensiones, a menudo es 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 de caché inconsciente 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). 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 una complejidad O ( N  log  N ). Otra variación más es realizar transposiciones matriciales entre la transformación de dimensiones posteriores, de modo que las transformadas operen sobre datos contiguos; esto es especialmente importante para situaciones de memoria distribuida y fuera del núcleo en las que el acceso a datos no contiguos requiere mucho tiempo. ${\ Displaystyle (n_ {1}, \ ldots, n_ {d / 2})}$${\ Displaystyle (n_ {d / 2 + 1}, \ ldots, n_ {d})}$

Hay otros algoritmos FFT multidimensionales que son distintos del algoritmo fila-columna, aunque todos tienen complejidad O ( N  log  N ). 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 en el que se dividen las dimensiones de la transformada por un vector de radicales en cada paso. (Esto también puede tener beneficios de caché). El caso más simple de vector-radix es donde todos los radix son iguales (por ejemplo, vector-radix-2 divide todas las dimensiones entre dos), pero esto no es necesario. Base vectorial con una sola base no unitaria a la vez, es decir , es esencialmente un algoritmo fila-columna. Otros métodos, más complicados, incluyen algoritmos de transformadas polinómicas de Nussbaumer (1977), que ven la transformada en términos de convoluciones y productos polinomiales. Consulte Duhamel y Vetterli (1990) para obtener más información y referencias. ${\ Displaystyle \ mathbf {r} = \ left (r_ {1}, r_ {2}, \ ldots, r_ {d} \ right)}$${\ Displaystyle \ mathbf {r} = \ left (1, \ ldots, 1, r, 1, \ ldots, 1 \ right)}$

Otras generalizaciones

Mohlenkamp describió una generalización O ( N ^5/2 log  N ) a armónicos esféricos en la esfera S ² con nodos N ² , junto con un algoritmo conjeturado (pero no probado) que tiene O ( N ² log ² ( N )) complejidad; Mohlenkamp también proporciona una implementación en la biblioteca libftsh. Rokhlin y Tygert describen un algoritmo armónico esférico con complejidad O ( N ² log  N ).

El algoritmo de plegado rápido es análogo al 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 una 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). Dichos algoritmos no calculan estrictamente la DFT (que solo se define para datos equiespaciados), sino alguna aproximación de la misma (una transformada discreta de Fourier no uniforme , o NDFT, que a menudo se calcula solo aproximadamente). 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 .

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 FFT incluyen:

• multiplicación rápida de números enteros grandes y polinomios,
• multiplicación eficiente de matriz-vector para Toeplitz , circulante y otras matrices estructuradas,
• algoritmos de filtrado (ver métodos de superposición-añadir y superponer-guardar ),
• algoritmos rápidos para transformaciones de seno o coseno discretas (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 .
• 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.

Áreas de investigación

Grandes FFT

Con la explosión de 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.

FFT aproximados

Para aplicaciones como MRI, es necesario calcular DFT para puntos de cuadrícula y / o frecuencias no espaciados uniformemente. Los enfoques basados ​​en múltiples polos pueden calcular cantidades aproximadas con un factor de aumento del tiempo de ejecución.

FFT de grupo

La FFT también puede explicarse e interpretarse utilizando la teoría de la 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 de investigación activa para 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.

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 cuántica FFT, que es efectivamente la Cooley-Tukey FFT realizada como una factorización particular de la matriz de Fourier. Actualmente se está explorando la extensión de estas ideas.

Referencia idiomática

Idioma	Comando / Método	Prerrequisitos
R	estadísticas :: fft (x)	Ninguno
Octava / MATLAB	fft (x)	Ninguno
Pitón	fft.fft (x)	numpy
Mathematica	Fourier [x]	Ninguno
Fortran	fftw_one (plan, adentro, afuera)	FFTW
Julia	fft (A [, atenúa])	FFTW
Oxido	fft.process (& mut x);	rustfft
Haskell	dft x	fft

Ver también

Algoritmos relacionados con FFT:

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

Implementaciones 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 FFT de Fortran (dominio público)
• Específico de la arquitectura:
  • Bibliotecas Arm Performance
  • Primitivas de rendimiento integradas de Intel
  • Biblioteca de kernel matemático de Intel
• Hay muchas más implementaciones disponibles 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 : diagrama que se utiliza 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 los varios dispositivos que realizan análisis de espectro, a menudo a través de una 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

Otras lecturas

• Brigham, E. Oran (2002). "La Transformada Rápida de Fourier". Nueva York, Estados Unidos: Prentice-Hall . Cite journal requiere |journal=( ayuda )
• 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.). 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 rápida transformada de Fourier discreta". Actas de ICASSP '94. Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales . Actas de la Conferencia IEEE sobre acústica, habla y procesamiento de señales (ICASSP) . 3 . págs. 445–448. doi : 10.1109 / ICASSP.1994.389994 . ISBN 978-0-7803-1775-8. S2CID  42639206 .
• Johnson, Steven G .; Frigo, Matteo (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 bibliográfico : 2007ITSP ... 55..111J . CiteSeerX  10.1.1.582.5497 . doi : 10.1109 / tsp.2006.882087 . S2CID  14772428 .
• Prensa, 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 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 . Transacciones IEEE sobre audio y electroacústica . AU-17. Grupo IEEE Audio y Electroacústica. 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 de polinomios  : 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, enlaces, libro y código en línea
• Sri Welaratna, " Treinta años de analizadores FFT ", Sound and Vibration (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 procesamiento de datos y análisis numérico con licencia dual / GPL en varios idiomas (VBA, C ++, Pascal, etc.)
• SFFT: Transformada rápida dispersa de Fourier:  algoritmo de FFT disperso (tiempo sublineal), sFFT e implementación del MIT
• 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