FFT (Fast Fourier Transform)
La optimización del proceso de cálculo del DFT está basado en las siguientes ideas :
- Simetría y Periodicidad de los términos WN.
- Elegimos el valor de N de forma que N=rm. Al factor r se le denomina radix y su valor más habitual es 2, de forma que N=2m y algoritmo se denomina FFT radix-2.
Radix-2 FFT-Decimación en el Tiempo.
- Dividimos la secuencia de datos de entrada x[n] en dos grupos, uno de índices par y el otro de índices impar. Con estas sub-secuencias se realiza el DFT de N/2 puntos y sus resultados se combinan para formar el DFT de N puntos.