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

[复制链接]
1520|2
 楼主| tianli1980 发表于 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程序伪代码如下:


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×
 楼主| tianli1980 发表于 2014-7-31 18:34 | 显示全部楼层
IFFT的BASIC程序伪代码如下(IFFT通过调用FFT计算):

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


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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×
zhangmangui 发表于 2014-7-31 23:10 | 显示全部楼层
英文版的  但是其中的流程图很直观
您需要登录后才可以回帖 登录 | 注册

本版积分规则

482

主题

2214

帖子

11

粉丝
快速回复 在线客服 返回列表 返回顶部