FFT (Fast Fourier Transform)
La importancia de DFT estriba en que es posible utilizar un algoritmo, llamado FFT, que lo realiza de forma eficiente y rápida.
El DFT de una secuencia x[n] es :
Una primera aproximación al cálculo del DFT requeriría la suma compleja de N multiplicaciones complejas para cada uno de las salidas. En total, N2 multiplicaciones complejas y N2 sumas complejas para realizar un DFT de N puntos.
Lo que consigue el algoritmo FFT es simplicar enormemente el cálculo del DFT introduciendo “atajos” matemáticos para reducir drasticamente el número de operaciones.