Algoritmo de Cooley-Tukey (FFT)
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. 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 la
TFR 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:
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. 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:
El primer
elemento es:
X1[0]=X0[0]+W0X0[2]
No hay comentarios:
Publicar un comentario