El algoritmo FFT lo único que busca es resolver de la manera más eficiente posible la siguiente expresión:
donde como sabemos 
. La evaluación directa de este sumatorio implica N^2 multiplicaciones. Haciendo una serie de reordenaciones, conseguiremos con la FFT reducirlo a N*Log2(N) operaciones.
Primero se deben separar las muestras pares y las impares:
A continuación sacamos fuera de el sumatorio impar la exponencial E-jkW :
Si paramos a observar esta expresión, podemos ver que si ponemos
- Y=FFT(x[0], x[2], x[4], ..., x[N-2])
y
Z=FFT(x[1], x[3], x[5], ..., x[N-1])
entonces
El problema ha sido reducido al cálculo de dos FFTs de tamaño N/2 y realizar N multiplicaciones complejas. Es conveniente observar que el bit menos significativo de k determina siempre si k es par o impar. Repitiendo este proceso reiteradamente, conseguimos extraer la transformada de x. A continuación veremos como podemos codificar el algoritmo.
Gran aprte, solo hay que afinarlo para hacerlo mejor de lo que ya es. Saludos