De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Un ejemplo de estructura de algoritmo de FFT, utilizando una descomposición en FFT de tamaño medio
Un análisis discreto de Fourier 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 lento para ser práctico. Una FFT calcula rápidamente tales transformaciones factorizando la matriz DFTen un producto de factores escasos (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, 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 yteoría de números .

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. [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 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 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. 

Historia [ editar ]

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. [6] [7] 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 FFT genérico 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 . [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 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 paracómputo 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 obtener el tiempo de ejecución. [11]

James Cooley y John Tukey publicaron una versión más general de FFT en 1965 que es aplicable cuando N es compuesto y no necesariamente una potencia de 2. [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 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 discusión con Tukey, Richard Garwinreconoció 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. [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 período 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 próxima década, convirtió a FFT en uno de los algoritmos indispensables en el procesamiento de señales digitales.

Definición [ editar ]

Vamos , ..., ser números complejos . La DFT está definida por la fórmula

donde es una raíz N- ésima primitiva de 1.

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 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. [dieciséis] Θ ( norte Iniciar sesión ⁡ norte ) {\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 2 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 2 ( N ) multiplicaciones complejas (nuevamente, ignorando las simplificaciones de multiplicaciones por 1 y similares) yAdiciones complejas de N  log 2 ( N ), 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 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), [17] pero la mejora general de a permanece.

Algoritmos [ editar ]

Algoritmo de Cooley-Tukey [ editar ]

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 [18] ) .

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 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 de 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 [1] ). 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 [ editar ]

Hay algoritmos de FFT distintos de Cooley-Tukey. Cornelius Lanczos realizó un trabajo pionero en FFT y FFS ( método de muestreo rápido de Fourier ) con GC Danielson (1940). [ cita requerida ]

Para N = N 1 N 2 con coprimos N 1 y N 2 , 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 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 reemplazado por el split-radixvariante 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 [20] 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.) Algoritmo de Bruun , en particular , se basa en 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, [21] [22] 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 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 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 conmultiplicadores de hardware . En particular, Winograd también utiliza el 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 la 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 evaluado por radix-2 Cooley – Tukey FFT, por ejemplo), a través de la identidad

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 [ editar ]

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

y se han diseñado algoritmos de 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 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. [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.

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 de FFT para estos casos, las DCT / DST también se pueden calcular a través de FFT de datos reales combinados con el procesamiento previo y posterior de O ( N ).

Problemas de computación [ editar ]

Límites de complejidad y operaciones [ editar ]

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 ?

(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 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 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 optimización de la canalización de la CPU o la memoria caché .

Siguiendo el trabajo de Shmuel Winograd (1978), [21] se conoce un límite inferior estrecho de Θ ( 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; [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]

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 [27] demostró un límite inferior Ω ( N  log  N ) en el recuento de sumas para 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). Sin embargo, este resultado se aplica solo a la transformada de Fourier no normalizada (que es una escala de una matriz unitaria por un factor de ), y no explica por qué la matriz de Fourier es más difícil de calcular que cualquier otra matriz unitaria (incluida la matriz de identidad) bajo la misma escala. Pan (1986) [28] demostró ser un Ω ( N log  N ) 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 de Cooley-Tukey es óptimo bajo ciertos supuestos en el gráfico del algoritmo (sus supuestos implican, entre otras cosas, que no se exploten identidades aditivas en las raíces de la unidad). (Este argumento implicaría que al menosse requieren 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 potencias de -dos  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; [16] Lundy y Van Buskirk, 2007 [30] ). Un recuento ligeramente mayor (pero aún mejor que la base dividida para N≥ 256) demostró ser óptimamente probada para N ≤ 512 bajo restricciones adicionales sobre los posibles algoritmos (diagramas de flujo similares a radix dividido con factores multiplicativos de módulo unitario), mediante la reducción a un problema de teorías de módulo de satisfacibilidad que se puede resolver mediante la fuerza bruta (Haynal y Haynal, 2011). [31]

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). [32]

Aproximaciones [ editar ]

Todos los algoritmos de FFT discutidos anteriormente calculan la DFT exactamente (es decir, ignorando los errores de coma 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) [33] 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) [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 las salidas 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 (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 ha sido demostrado para dar lugar a aceleraciones prácticos en comparación con una FFT ordinario para N / K  > 32 en un a gran N ejemplo ( N  = 2 22 ) utilizando un algoritmo aproximado probabilística (que estima los mayores K coeficientes a varios lugares decimales). [36]

Precisión [ editar ]

Los algoritmos FFT tienen errores cuando se usa 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 ), comparado con O ( εN 3/2 ) para la fórmula DFT ingenua, [18] donde ε es la precisión relativa del punto flotante de la máquina. De hecho, los errores de la raíz cuadrada media (rms) son mucho mejores que estos límites superiores, siendo solo O ( ε log N) para Cooley-Tukey y O ( ε N ) para el ingenuo DFT (Schatzman, 1996). [37] Estos resultados, sin embargo, son muy sensibles a la precisión de los factores de twiddle usados ​​en la FFT (es decir, los valores de la función trigonométrica ), y no es inusual que las implementaciones imprudentes de FFT tengan una precisión mucho peor, por ejemplo, si usan valores inexactos fórmulas de recurrencia trigonométrica . 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). [38] Lograr esta precisión requiere una cuidadosa atención 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) . [39]

FFT multidimensionales [ editar ]

Como se define en el artículo de DFT multidimensional , el DFT multidimensional

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).

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 1 , luego a lo largo de la dimensión n 2 , 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 de tamaño N / N 1N 1 , etcétera, por lo que la complejidad de la secuencia de FFT es:

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 (o filas) de esta segunda matriz, y agrupar de manera similar los resultados en la matriz de resultado final.

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 1 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 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). [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 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.

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 de fila-columna. Otros métodos, más complicados, incluyen los algoritmos de transformadas polinómicas de Nussbaumer (1977), [40] que ven la transformada en términos de convoluciones y productos polinomiales. Consulte Duhamel y Vetterli (1990) [32] para obtener más información y referencias.

Otras generalizaciones [ editar ]

Mohlenkamp describió una generalización O ( N 5/2 log  N ) a armónicos esféricos en la esfera S 2 con nodos N 2 , [41] junto con un algoritmo conjeturado (pero no probado) que tiene O ( N 2 log 2 ( N )) 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 O ( N 2 log  N ). [43]

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). [44] 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 [ editar ]

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 computacionalmente que trabajar en el dominio temporal o espacial. Algunas de las aplicaciones importantes de la FFT incluyen: [15] [46]

  • 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 . [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.

Áreas de investigación [ editar ]

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. [48]
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. [49]
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. [50]
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 que ahora se conocen 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.

Referencia de idioma [ editar ]

Ver también [ editar ]

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 de Fortran FFT (dominio público)
  • Específico de la arquitectura:
    • Bibliotecas Arm Performance [51]
    • Primitivas de rendimiento integradas de Intel
    • Biblioteca de kernel matemático de Intel
  • Hay muchas más implementaciones disponibles, [52] 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

Referencias [ editar ]

  1. ^ a b c d 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 .
  2. ^ Van Loan, Charles (1992). Marcos computacionales para la transformada rápida de Fourier . SIAM .
  3. ^ Strang, Gilbert (mayo-junio de 1994). "Wavelets". Científico estadounidense . 82 (3): 250-255. JSTOR 29775194 . 
  4. ^ Kent, Ray D .; Leer, Charles (2002). Análisis acústico del habla . ISBN 0-7693-0112-6.
  5. ^ Dongarra, Jack; Sullivan, Francis (enero de 2000). "Introducción a los 10 mejores algoritmos de los editores invitados". Computación en ciencia e ingeniería . 2 (1): 22-23. Código Bibliográfico : 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). 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 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 No. 35 de la Oficina de Suelos del Commonwealth . 142 (3585): 90–92. Código Bibliográfico : 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". Revista del Instituto Franklin . 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". 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. ↑ a b Cooley, James W .; Tukey, John W. (1965). "Un algoritmo para el cálculo mecánico 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 transformación rápida de Fourier (PDF) . Microchimica Acta . III . Viena, Austria. págs. 33–45.
  14. ^ Garwin, Richard (junio de 1969). "La transformada rápida de Fourier como ejemplo de la dificultad para obtener un amplio uso de una nueva técnica" (PDF) . Transacciones IEEE sobre audio y electroacústica . AU-17 (2): 68–72.
  15. ↑ a b 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 Bibliográfico : 2000CSE ..... 2a..60R . CiteSeerX 10.1.1.17.228 . doi : 10.1109 / 5992.814659 . ISSN 1521-9615 .  
  16. ^ a b Frigo, Matteo; Johnson, Steven G. (enero de 2007) [19 de diciembre de 2006]. "Una FFT de base dividida modificada con menos operaciones aritméticas". 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 .  
  17. ^ a b c Frigo, Matteo; Johnson, Steven G. (2005). "El Diseño e Implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi : 10.1109 / jproc.2004.840301 . S2CID 6644892 .   
  18. ^ a b Caballero, W. Morven; Sande, G. (1966). "Transformaciones rápidas de Fourier, por diversión y ganancias". Actuaciones de la AFIPS . 29 : 563–578. doi : 10.1145 / 1464291.1464352 . S2CID 207170956 . 
  19. ^ Gauss, Carl Friedrich (1866) [1805]. Theoria interpolationis methodo nova tractata . Werke (en latín y alemán). 3 . Gotinga, Alemania: Königliche Gesellschaft der Wissenschaften. págs. 265–327.
  20. ↑ a b Brenner, Norman M .; Rader, Charles M. (1976). "Un nuevo principio para la transformación rápida de Fourier". Transacciones IEEE sobre acústica, habla y procesamiento de señales . 24 (3): 264–266. doi : 10.1109 / TASSP.1976.1162805 .
  21. ↑ a b 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. ↑ a b 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, habla 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" 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 longitud-2 n DFT". Transacciones IEEE sobre acústica, habla y procesamiento de señales . 34 (1): 91–95. doi : 10.1109 / TASSP.1986.1164785 .
  26. ↑ a b Duhamel, Pierre (1990). "Algoritmos que cumplen los límites inferiores de la complejidad multiplicativa de las DFT de longitud 2 n y su conexión con algoritmos prácticos". Transacciones IEEE sobre acústica, habla 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, Victor Ya. (2 de enero de 1986). "El compromiso 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 de matriz para FFT reales y convoluciones de longitud 2 k ". Computación . 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 de Satisfacción, 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. ↑ a b Duhamel, Pierre; Vetterli, Martin (1990). "Transformaciones rápidas de Fourier: una revisión tutorial y un estado del arte" . Procesamiento de señales . 19 (4): 259–299. 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 de Computación Científica . 20 (3): 1094-1114. CiteSeerX 10.1.1.54.9339 . doi : 10.1137 / S1064827597316266 .  
  34. ^ Guo, Haitao; Burrus, Charles Sidney (1996). "Transformada de Fourier rápida aproximada a través de la transformada de ondas". Procedimientos de SPIE . Aplicaciones de wavelet en el procesamiento de señales e imágenes IV. 2825 : 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 .; Heute, 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 . (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. 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". 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: Superar el cuello de botella del generador . Actas del 27º Simposio ACM sobre Teoría de la Computación . Kyoto, Japón. págs. 407–416. doi : 10.1145 / 225058.225167 . ISBN 978-0897917186. S2CID  15512806 .
  40. ^ Nussbaumer, Henri J. (1977). "Filtrado digital mediante transformadas polinómicas". Cartas de electrónica . 13 (13): 386–387. doi : 10.1049 / el: 19770280 .
  41. ^ Mohlenkamp, ​​Martin 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 . 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. CiteSeerX 10.1.1.125.7415 . doi : 10.1137 / 050623073 . Consultado el 18 de septiembre de 2014 .   [1]
  44. ^ Potts, Daniel; Steidl, Gabriele ; Tasche, Manfred (2001). "Transformaciones rápidas de Fourier para datos no espaciados: un tutorial" (PDF) . En Benedetto, JJ; Ferreira, P. (eds.). Teoría moderna del muestreo: matemáticas y aplicaciones . Birkhäuser .
  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, 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 . Prensa CRC . págs. 153-168. ISBN 978-1-42004996-1.
  47. Fernandez-de-Cossio Diaz, Jorge; Fernández-de-Cossio, Jorge (8 de agosto de 2012). "Cálculo de la distribución de masa de centro de pico isotópico por transformada de Fourier". Química analítica . 84 (16): 7052–7056. doi : 10.1021 / ac301296a . ISSN 0003-2700 . PMID 22873736 .  
  48. ^ Cormen, Thomas H .; Nicol, David M. (1998). "Realización de FFT fuera del núcleo en sistemas de disco paralelo" (PDF) . Computación paralela . 24 (1): 5-20. CiteSeerX 10.1.1.44.8212 . doi : 10.1016 / S0167-8191 (97) 00114-2 .  [ enlace muerto permanente ]
  49. ^ Dutt, Alok; Rokhlin, Vladimir (1 de noviembre de 1993). "Transformadas rápidas de Fourier para datos no espaciados". Revista SIAM de Computación Científica . 14 (6): 1368-1393. doi : 10.1137 / 0914081 . ISSN 1064-8275 . 
  50. ^ Rockmore, Daniel N. (2004). "Avances recientes y aplicaciones en FFT grupales". En Byrnes, Jim (ed.). Álgebra computacional no conmutativa y aplicaciones . Serie de Ciencias de la OTAN II: Matemáticas, Física y Química. 136 . Springer Holanda. 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 .
  51. ^ "Bibliotecas de rendimiento de brazo" . Brazo . 2020 . Consultado el 16 de diciembre de 2020 .
  52. ^ "Lista completa de bibliotecas FFT C / C ++" . Comunidad VCV . 2020-04-05 . Consultado el 3 de marzo de 2021 .

Lectura adicional [ editar ]

  • Brigham, E. Oran (2002). "La Transformada Rápida de Fourier". Nueva York, Estados Unidos: Prentice-Hall . Cite journal requires |journal= (help)
  • 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 discreta de Fourier". 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).

Enlaces externos [ editar ]

  • 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