Transformada rápida de Fourier
De Wikipedia, la enciclopedia libre
FFT es la abreviatura usual (del inglés Fast Fourier Transform) de un eficiente algoritmo que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones diferenciales parciales o los algoritmos de multiplicación rápida de grandes enteros. El algoritmo pone algunas limitaciones en la señal y en el espectro resultante. Por ejemplo: la señal de la que se tomaron muestras y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores TRF permiten la transformación de 512, 1024, 2048 o 4096 muestras. El rango de frecuencias cubierto por el análisis TRF depende de la cantidad de muestras recogidas y de la proporción de muestreo.
Teniendo en cuenta únicamente las multiplicaciones, un PC que realiza 40000 multiplicaciones reales por segundo necesitaría, aproximadamente, ¡dos meses! para transformar una simple imagen de 512x512 píxeles. Incluso un superordenador con una potencia operacional de 1000 MFLOPS ( millones de operaciones en coma flotante por segundo ) tardaría unos tres minutos. Estas cifras hacen urgente la minimización del número de operaciones que se necesitan en el tratamiento de la imagen mediante la elección de un algoritmo adecuado. Para conseguir esto, debemos estudiar la estructura interna de una tarea dada, su complejidad operacional y tratar de averiguar cómo puede resolverse con el mínimo número de operaciones.
Como ejemplo, consideremos el siguiente problema de búsqueda: Un amigo vive en un rascacielos de N plantas. Queremos averiguar en qué planta está su apartamento. Nuestras preguntas sólo serán contestadas con " sí " o " no ". ¿Cuántas preguntas debemos formular para averiguar dónde vive?.
La aproximación más sencilla y más directa consiste en preguntar: " ¿Vives en la planta n? ". En el mejor de los casos, nuestra sospecha inicial resulta cierta, pero es más probable estar equivocados, de tal manera que habrá que repetir la misma pregunta con otras plantas. En el peor de los casos, haremos exactamente N-1 preguntas. Con cada pregunta sólo podemos excluir una de las N posibilidades.
Sin embargo, con la pregunta " ¿Vives en la mitad superior del edificio? ", podemos excluir la mitad de las posibilidades de una sola vez.
Tras la respuesta, sabremos si él vive en la mitad superior o inferior del edificio, y podemos seguir haciendo nuestras preguntas de la misma manera, mediante la partición de las restantes posibilidades en dos mitades (método de la búsqueda dicotómica). Con esta estrategia, necesitamos un menor número de preguntas.
Una medida de la complejidad operacional de un problema con N componentes es la potencia más grande de N que aparece en el cálculo de operaciones necesarias para resolverlo. Esta aproximación es útil, ya que la potencia más grande en N domina el número de operaciones necesarias para un valor de N grande.
Tras esta breve introducción a los algoritmos rápidos, comenzamos a tratar la transformada rápida de Fourier (FFT, del inglés Fast Fourier Transform). La FFT constituye uno de los mayores desarrollos en la tecnología del tratamiento de la imagen (en general, de cualquier tipo de señal). Las diversas aplicaciones de la FFT surgen de sus raíces: la transformada discreta de Fourier y de ahí, la transformada de Fourier.
La evolución de la informática, particularmente la del ordenador personal, ha hecho de la FFT una herramienta de análisis manejable y potente.
Durante el estudio del algoritmo FFT, podremos apreciar su enorme potencia. Además, haremos una comparación entre el número de operaciones que supone un cálculo directo de la DFT y el que supone el cálculo de la DFT mediante el algoritmo FFT.
Primero veremos a fondo la FFT unidimensional. Después, la FFT bidimensional se comprenderá fácilmente.
Contenido |
[editar] Definición
Sean x0, ...., xn-1 números complejos. La transformada discreta de Fourier (DFT, por sus siglas en inglés) se define como
La evaluación directa de esa fórmula requiere O(n²) operaciones aritméticas. Mediante un algoritmo FFT se puede obtener el mismo resultado con sólo O(n log n) operaciones. 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.
La idea que permite esta optimización es la descomposición de la transformada a tratar en otras más simples y éstas a su vez hasta llegar a transformadas de 2 elementos donde k puede tomar los valores 0 y 1. Una vez resueltas las transformadas más simples hay que agruparlas en otras de nivel superior que deben resolverse de nuevo y así sucesivamente hasta llegar al nivel más alto. Al final de este proceso, los resultados obtenidos deben reordenarse.
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/n, cualquier algoritmo FFT puede ser fácilmente adaptado para el cálculo de la transformada inversa.
[editar] Aplicaciones
- Tratamiento de imagen (JPEG) y audio (MP3)
- Reducción de ruido en señales, como el ruido blanco
- Análisis en frecuencia de cualquier señal discreta
- Análisis de materiales y estadística
- Síntesis, mediante la transformada inversa IFFT
[editar] Véase también
[editar] Enlaces externos
- Fast Fourier Transform en inglés.
- "The Scientist and Engineer's Guide to Digital Signal Processing": se encuentra numerosa información relacionada con el tema, concretamente en los capítulos 10, 11, 12 y 31.
