DFT算法能够获取信号频域特征,但是算法计算量大,耗时长,不利于计算机实时对信号进行处理。因此至DFT被发现以来,在很长的一段时间内都不能被应用到实际的工程项目中,直到一种快速的离散傅立叶计算方法——FFT,被发现,离散傅立叶变换才在实际的工程中得到广泛应用。FFT并不是一种新的频域特征获取方式,而是DFT的一种快速实现算法。
DFT计算量
1)计算一个X(k)值的运算量:
复数乘法次数:N
复数加法次数:N-1
2)计算全部N个X(k)值的运算量:
复数乘法次数:N*N
复数加法次数:N*(N-1)
FFT快速算法的依据如下:
FFT原理:
以8点为例第一次奇偶分离
以8点为例第2次奇偶分离
以8点为例第3次奇偶分离
IFFT:
IFFT的另外一种算法: