Fft

La Transformada Rápida de Fourier (FFT, Fast Fourier Transform) es un algoritmo muy eficiente (de orden polinómico) para calcular la DFT (Discrete Fourier Transform), i.e., la Transformada Discreta de Fourier. Sin entrar en derivaciones, la FFT de una secuencia x(n) de N puntos complejos numerados del 0 al N-1, se basa en las ecuaciones siguientes:
X(k) = Y(k) + w(N)^k*Z(k)
X(N/2+k) = Y(k) - w(N)^k*Z(k)
donde N es una potencia de 2, w(N) es el "factor twiddle" enésimo dado por
w(N)=e^(-j*2*pi/N) , donde j es la unidad imaginaria. Y(k) es la FFT de los puntos de X numerados pares y Z(k) es la FFT de los puntos de X numerados impares. Es decir, tenemos un algoritmo recursivo. El fin de la recursividad se produce cuando sólo nos quedan grupos de dos puntos, en cuyo caso utilizamos las ecuaciones:
X(0)=x(0)+x(1) (la x minúscula es la secuencia original,
X(1)=x(0)-x(1) y la X la FFT de x)
Se va a ver mucho más claro con un ejemplo.
Imaginemos que queremos realizar la transformada discreta de Fourier de la siguiente secuencia:
x(0)=1
x(1)=0'86688
x(2)=0'75148
x(3)=0'65144
x(4)=0'56472
x(5)=0'48954
x(6)=0'42437
x(7)=0'36788
N=8
Podemos organizar los cálculos en forma de tabla:
1 | 1 | 1 || 1'56472 | 2'74057 | 5'11631
0'.6688 | 0'.5148 | 0'56472 || 0.43528 | 0'435-j0.327 | 0'5-j0'794
| |----------||-----------| |
0'.5148 | 0'56472 | 0'.5148 || 1'17585 | 0'389 | 0'389-j0'337
0'.5144 | 0'42437 | 0'42437 || 0'32711 | 0.435+j0.327| 0'369-j0'140
|-----------|----------||----------|-------------- |
0'56472 | 0'.6688 | 0'.6688 || 1'35642 | 2'3757 | 0'36483
0'48954 | 0'.5144 | 0'48954 || 0.37734 | 0377-j0'283 | 0'389+j0'140
| |-----------||----------| |
0'42437 | 0'48954 | 0'.5144 || 1.01932 | 0'337 | 0'389+j0'337
0'36788 | 0'36788 | 0'36788 || 0.28356 | 0'377+j0'283 | 0'5+j0'794
La primera columna es la secuencia original, a la que queremos aplicar el algoritmo de la FFT. Para ello, separamos primero los puntos con índices pares de los que tienen índices impares. Para resolver el problema en este momento necesitaríamos las FFTs de las dos subsecuencias de la segunda columna. Pero, para eso, aplicamos el mismo procedimiento. Separamos los pares e imapres RELATIVOS a cada secuencia de la columna dos apareciendo en la columna 3 cuatro secuencias de dos puntos. Realizamos sus FFTs sumando y restando los puntos, obteniendo la cuarta columna. La quinta columna se obtiene al aplicar las fórmulas dadas al principio, obteniendo dos secuencias de cuatro puntos. Finalmente, volvemos a aplicar dichas expresiones y resulta una secuencia de N=8 puntos, la DFT, X(k), de la secuencia original.
Espero que me haya explicado con claridad y te haya servido de ayuda.