FFT算法的完整DSP实现：有关FFT理论的一点小小解释

登录 · 发表于 2014-7-31 18:32

关于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程序伪代码如下:

登录 · 发表于 2014-7-31 18:34

IFFT的BASIC程序伪代码如下（IFFT通过调用FFT计算）：

  FFT算法的流程图如下图，总结为3过程3循环：
   （1）3过程：单点时域分解（倒位序过程） + 单点时域计算单点频谱 + 频域合成
   （2）3循环：外循环——分解次数，中循环——sub-DFT运算，内循环——2点蝶形算法

分解过程或者说倒位序的获得参考下图理解：

发表于 2014-7-31 23:10

英文版的但是其中的流程图很直观

FFT算法的完整DSP实现：有关FFT理论的一点小小解释

本帖子中包含更多资源

相关帖子

本帖子中包含更多资源

浏览过的版块

无冕之王奖章

奔腾之江水

技术奇才奖章

伴坛终老

技术领袖奖章

十世金身

坚毅之洋流

荣誉元老奖章