关于FFT这里只想提到两点:
(1)DFT变换对的表达式(必须记住)
—— 称旋转因子
2)FFT用途——目标只有一个,加速DFT的计算效率。
DFT计算X(k)需要N^2次复数乘法和N(N-1)次复数加法;FFT将N^2的计算量降为。
“FFT其实是很难的东西,即使常年在这个领域下打拼的科学家也未必能很好的写出FFT的算法。”——摘自参考上面提供的参考文献[1]
因此,我们不必太过纠结于细节,当明白FFT理论后,将已有的算法挪过来用就OK了,不必为闭着教材写不出FFT而郁闷不堪。
FFT的BASIC程序伪代码如下:
FFT算法的流程图如下图,总结为3过程3循环:
(1)3过程:单点时域分解(倒位序过程) + 单点时域计算单点频谱 + 频域合成
(2)3循环:外循环——分解次数,中循环——sub-DFT运算,内循环——2点蝶形算法
分解过程或者说倒位序的获得参考下图理解:
一周热门 更多>