transformada rrapida de furiel

Transformada rápida de Fourier
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 en derivadas parciales o losalgoritmos 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 defrecuencias cubierto por el análisis TRF depende de la cantidad de muestras recogidas y de la proporción de muestreo.
Uno de los algoritmos aritméticos más ampliamente utilizados es la transformada rápida de Fourier, un medio eficaz de ejecutar un cálculo matemático básico y de frecuente empleo. La transformada rápida de Fourier es de importancia fundamental en el análisis matemático y ha sido objeto denumerosos estudios. La aparición de un algoritmo eficaz para esta operación fue una piedra angular en la historia de la informática.
Las aplicaciones de la transformada rápida de Fourier son múltiples. Es la base de muchas operaciones fundamentales del procesamiento de señales, donde tiene amplia utilización. Además, proporciona un medio oportuno para mejorar el rendimiento de los algoritmospara un conjunto de problemas aritméticos comunes.
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 dela 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 queagruparlas 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 elcálculo de la transformada inversa. Por lo general, tenemos que:
Un algoritmo que es mucho más eficiente en cuanto al tiempo de cómputo para grandes arreglos de entrada cuya longitud es una potencia entera de dos, recibe el nombre de Transformada de Fourier Rápida (TFR), y dicho algoritmo fue popularizado por Cooley y Tukey en 1965. Se puede ilustrar mediante el siguiente ejemplo, calculando laTFR de un conjunto de cuatro muestras de datos utilizando el algoritmo. Defina el conjunto de muestras de una señal como la señal X₀[n] en TD de forma que los datos de entrada para el algoritmo sea {X₀[0],X₀[1],X₀[2],X₀[3]}. La fórmula de la TFD es la siguiente:
Se recomienda usar la notación:
W=e-j(2π/NF)
Para este caso de 4 puntos de datos, es posible escribir la TFR en forma de matriz como:Efectuar la multiplicación usual de matrices directa requeriría N² multiplicaciones complejas y N(N-1) adiciones complejas. Por lo tanto puedes escribirse de la siguiente manera:

Debido a que Wn=Wn+mNF , donde m es un entero, es posible factorizar la matriz en el producto de dos matrices;

Los elementos “1” y “2” han cambiado de lugar en el vector que se encuentra del lado izquierdo....