TRANSFORMADA RAPIDA DE FOURIER (FAST FOURIER TRANSFORM)

 

Recordemos que la Transformada Discreta de Fourier (DFT del inglés Discrete Fourier Transform) es el equivalente discreto de la Transformada de Fourier donde se ha transformado la variable continua ‘t’ por la variable discreta ‘nTs’ siendo ‘Ts’ el periodo de muestreo. Sin embargo, Hay dos situaciones a considerar en cuanto al uso de la Transformada Discreta de Fourier: Sólo sirve para señales potencia del tipo periódico y la mayoría de las señales a estudiar no son periódicas.

 No obstante, la DFT es una operación ampliamente empleada en tratamiento de señales y en campos afines para analizar las frecuencias presentes en una señal muestreada, resolver  ecuaciones diferenciales parciales y realizar otras operaciones, como: convoluciones y correlaciones y  puede calcularse de modo muy eficiente mediante el algoritmo FFT. Por lo que, ha causado un gran impacto en la comunidad científica el hecho de que se haya desarrollado en MIT, un algoritmo capaz de acelerar sustancialmente el cálculo de la FFT como se anunció el pasado enero durante el Simposio ACM-SIAM en algoritmos discretos.

Cito textualmente a Gilbert Strang, autor del libro de texto de álgebra lineal y sus aplicaciones, quien  se refirió a la transformada rápida de Fourier o FFT, como "el algoritmo numérico más importante en nuestra vida." No es extraño, ya que la FFT se utiliza para procesar los datos en el mundo digital altamente interconectado de hoy.

Algunas aplicaciones que definen a la FFT son: compresión de imagen y audio, filtrado digital, reducción de ruido en señales: como el ruido blanco, resolución de ecuaciones diferenciales parciales, análisis en frecuencia de cualquier señal discreta, ya sea periódicas o aperiódicas.

análisis de materiales y estadística, síntesis, mediante la transformada inversa IFFT, los ya mencionados algoritmos rápidos de convolución, correlación y detección de movimiento, por solo mencionar algunas.

 Aunque la mayoría de los ingenieros asocian la FFT con el procedimiento James Cooley de IBM y John Tukey de Princeton descrito en 1965, los especialistas reconocen que tiene raíces mucho más profundas. Aunque nunca lo publicó, el famoso matemático alemán Carl Friedrich Gauss había elaborado el enfoque básico, probablemente ya en 1805, precediendo, muy poco, incluso el propio trabajo de Fourier sobre el tema, quien quizás no pudo establecer el alcance de su trabajo en aquel momento.

La razón fundamental  de estos avances, es que los nuevos métodos están diseñados para correr rápido sólo para algunas señales-ondas que se denominan "escasas",  es decir, contienen un número relativamente pequeño de componentes de frecuencia de tamaño significativo. Estas señales, se encuentran abundantemente en la naturaleza, ya sean imágenes astronómicas o gorjeos de aves, tiende a concentrarse en las frecuencias más bajas. La FFT tradicional toma la misma cantidad de tiempo de cálculo para cualquier señal.

El nuevo algoritmo de MIT, que se describe en el “paper”  que pronto será publicado, es mejor que la tradicional FFT siempre y cuando el número de componentes de frecuencia presente un porcentaje de un dígito del número de muestras que toma de la señal. Funciona para cualquier señal, pero funciona más rápido que el FFT solamente bajo esas condiciones.

El mejor tiempo que tarda en ejecutar el mejor algoritmo FFT aumenta en proporción a la cuarta potencia del logaritmo del número de muestras, mientras que el más reciente algoritmo de MIT tiene un tiempo de ejecución que es proporcional a sólo la primera potencia de ese número. Lo cual constituye un gran avance.