Diferencia entre revisiones de «Transformada rápida de Fourier»

Sea <math> x(n) </math> una señal aperiódica discreta en el tiempo. La transformada discreta de Fourier (DFT, por sus siglas en inglés) de esta señal se define<ref>{{Cita libro|apellidos=Proakis|nombre=John|enlaceautor=|título=Digital Signal Processing (Pearson New International Edition)|url=|fechaacceso=|año=2014|editorial=Pearson Education Limited|isbn=978-1-292-02573-5|editor=|ubicación=|edición=4|página=468|idioma=en|capítulo=7. The Discrete Fourier Transform: Its Properties

:<math> X(k)X_k = \sum_{n=0}^{N-1} x(n)x_n e^{-\frac{j 2\pi k \frac{ni}{N}} kn},

en la cual <math> X(k)X_k </math> es un conjunto de [[Número complejo|números complejos]]. La evaluación directa de esa fórmula requiere <math> O\left(N^{2 }\right)</math>operaciones aritméticas, pero con un algoritmo FFT se puede obtener el mismo resultado con solo <math> O(N\,log \,N )</math>operaciones. <ref name=":0">{{Cita publicación|url=https://www-elec.inaoep.mx/~jmram/cvjmr/El%20algoritmo%20de%20la%20FFT%20y%20su%20controvertido%201998.pdf|título=El algoritmo de la Transformada Rápida de Fourier y su controvertido origen|apellidos=Ramírez Cortés|nombre=Juan Manuel|apellidos2=Gómez Gil|nombre2=María del Pilar|fecha=marzo-abril de 1998|publicación=Ciencia y Desarrollo|volumen=24|número=139|páginas=70-77|fechaacceso=20 de octubre de 2018|doi=|pmid=|apellidos3=Báez López|nombre3=David}}</ref>En general, dichos algoritmos dependen de la factorización de ''n'' pero, al contrario de lo que frecuentemente se cree, existen FFTs para cualquier ''n'', incluso con ''n'' primo.

Dado que la transformada discreta de Fourier inversa es análoga a la transformada discreta de Fourier, con distinto signo en el exponente y un factor 1/''nN'', cualquier algoritmo FFT puede ser fácilmente adaptado para el cálculo de la transformada inversa discreta de Fourier (conocida por su sigla inglesa, IDFT). Por lo general, tenemos que:

&:<math> x_n = \text{IDFT}\{X_k\} = \frac{1}{N}\left(\text{DFT}\left\{{X_k}^*\right\}\right)^*\\ </math>

:donde el símbolo de asterisco (*) denota la [[Conjugado (matemática)|conjugada compleja]] de la expresión que le antecede.

:<math>X[k]=\sum_{n=0}^{N_FN-1}X_0[n]\, e^{-i2\pi(k \frac{n2\pi i}{N_FN}) kn}</math>

:<math>W=e^{-i(\frac{2\pi i}{N_FN})}</math>

Debido a que <math>W^n=W^{n+mN_FmN}</math>, donde <math>m</math> es un entero, es posible factorizar la matriz en el producto de dos matrices:

Los elementos <math>X[1]</math> y <math>X[2]</math> han cambiado de lugar en el vector que se encuentra del lado izquierdo. Cuando se multipliquen las matrices, los renglones 1 y 2, también se intercambiarán. Después, se calcula el número de multiplicaciones y adiciones que se requieren. Primero, se identifica el resultado de multiplicar la segunda matriz cuadrada por el conjunto de datos de entrada como:

De manera similar, el cálculo de <math>X[1]</math> y <math>X[2]</math>requieren de una multiplicación y una adición.Aunque <math>W^0</math>es uno, se hará que <math>W^0=-W^2</math> y el producto ya se ha obtenido en el cálculo del primer elemento y puede, en consecuencia, solo almacenarse hasta que se necesite y luego restarse en vez de sumarse. De manera similar, <math>X[3]</math>solo requiere una adición más. Hasta ahora se tienen dos multiplicaciones y cuatro sumas. Apelando a condiciones de simetrías similares en la segunda multiplicación de matrices, se encuentra que se requieren dos multiplicaciones y cuatro sumas más. Así, en total, se necesitan cuatro multiplicaciones y ocho adiciones. Puesto que, computacionalmente, las multiplicaciones requieren por lo general mucho más tiempo de cómputo que las adiciones, el algoritmo de FFT para cuatro puntos es alrededor de cuatro veces más rápido que la FDT directa. El siguiente diagrama muestra, en forma de gráfica de flujo de señales, como se realizan las operaciones necesarias.

Es el algoritmo más famoso para el cálculo de una FFT, diseñado por Cooley y Tukey en 1965. Tomando como entrada una señal discreta ''x''[''n''] con ''N'' muestras, se basa en dividir la señal de entrada en otras dos señales de ''N''/2 muestras (por un lado los coeficientes pares y por otro los impares), y se envían cada una de estas subseñales a una FFT de tamaño ''N''/2 puntos. Cada uno de los coeficientes de salida de la FFT de las muestras impares se multiplica por <math>W_N^K=e^{-i\frac{2\pi }{N}k}</math>, donde ''k'' es la posición del vector salida, y se suma a las muestras pares. A su vez, las FFT de ''N''/2 puntos se pueden resolver de esta misma manera, realizando esta operación de manera recursiva hasta obtener una FFT de una señal de tamaño 2, cuyo resultado es: