Transformada Rápida de Fourier (FFT)

[gL.edu] Este artículo recoge contribuciones de Adrià Espí Escrihuela, elaboradas en el contexto de la Clarificación conceptual en torno al "tratamiento digital de la señal", bajo la supervisión de Antonio Jesús Muñoz Montoro y J.M. Díaz Nafría.

ND: Este artículo requiere las mejoras indicadas a continuación: {{{Observaciones}}}

La Transformada Rápida de Fourier (FFT) es un algoritmo eficiente para calcular la Transformada de Fourier Discreta (DFT) y su inversa. Tiene amplias aplicaciones en el procesamiento digital de señales, ecuaciones en derivadas parciales y multiplicación rápida de enteros. Sin embargo, impone limitaciones, ya que requiere que la señal de entrada consista en un número de muestras que sea una potencia de dos. A pesar de estas restricciones, la FFT es fundamental en el análisis matemático y ha sido objeto de numerosos estudios, marcando un hito en la historia de la informática.

Transformada discreta de Fourier

La Transformada Discreta de Fourier (DFT) es una herramienta matemática utilizada en el análisis de Fourier. Transforma una función del dominio del tiempo en el dominio de la frecuencia, proporcionando una representación de la función original. Sin embargo, la DFT requiere que la función de entrada sea una secuencia discreta y de duración finita, generada a partir del muestreo de una función continua, como la voz humana. A diferencia de la Transformada de Fourier en tiempo discreto (DTFT), la DFT evalúa solo las componentes frecuenciales necesarias para reconstruir el segmento finito analizado. Para garantizar resultados precisos, se utilizan ventanas para reducir los efectos no deseados del espectro. La DFT es una transformada de Fourier adecuada para señales de tiempo discreto y dominio finito.

La transformada discreta de Fourier de define matemáticamente como:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi k{\frac {n}{N}}},\quad k=0,...,N-1.$

Idea básica de la FFT

La optimización de la DFT se basa en descomponer la transformada en transformadas más simples, empezando por transformadas de 2 elementos, donde k puede ser 0 o 1. Una vez resueltas estas transformadas básicas, se agrupan en transformadas de nivel superior que se resuelven nuevamente. Este proceso continúa hasta alcanzar el nivel más alto. Al finalizar, los resultados obtenidos deben ser reordenados.

Complejidad temporal

La computación directa de la DFT requiere realizar $O(N^{2})$ operaciones aritméticas (tiempo cuadrático), sin embargo, mediante el uso de un algoritmo FFT se puede obtener el mismo resultado utilizando únicamente $O(N\log(N))$ operaciones (tiempo linealitmico).

Algoritmo Cooley y Tukey

El algoritmo más conocido para calcular la Transformada Rápida de Fourier (FFT) fue desarrollado por Cooley y Tukey en 1965. Este algoritmo opera sobre una señal discreta x[n] con N muestras. Su enfoque consiste en dividir la señal de entrada en dos subseñales de tamaño N/2, una conteniendo los coeficientes pares y la otra los impares. Estas subseñales son luego enviadas a una FFT de N/2 puntos cada una. De esta manera, el algoritmo aprovecha la recursividad y la simetría de la transformada para calcular eficientemente la FFT de la señal completa.

Referencias

Proakis, J.G., Manolakis, D.G. (2007). Tratamiento digital de señales. Madrid: Pearson Educación.