注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周法哲的博客

重新认识我们的世界

 
 
 

日志

 
 
关于我

做过工,开过荒,教过书,扛过枪,当过干部仍在党,现任公司董事长。业余以探索天地人和谐之道为乐!

网易考拉推荐

(原创)快速傅里叶变换(FFT)(图)  

2009-08-10 22:42:01|  分类: 信息科学札记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

上一回说到,为了节省电脑的计算时间,实现数字信号的实时处理,科学界千方百计减少离散傅里叶变换(DFT)的计算量。

1965年,库利(T.W.Cooley)和图基(J.W.Tukey)发表《一个复数傅立叶级数之机械计算算法》论文,首次提出了DFT运算的一种快速算法。此后科学界创造出了各种各样的DFT快速算法,逐渐发展完善形成了一整套行之有效的算法设计思想和方法。这就是快速傅立叶变换(Fast Fouier Transform),简称FFT。

可见所谓的快速傅里叶变换(FFT),并不是一种新的傅立叶分析理论,而是减少DFT计算量的算法设计思想和DFT各种快速算法的统称。

上一回我们知道了:DFT的计算量与点数N的平方成正比。DFT的变换因子(也叫旋转因子):

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(1)

具有周期性和对称性。也就是说:

1、以N为周期,即:

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(2)

2、复共轭对称性(关于实轴对称),即:

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(3)

3、中心对称性(关于原点对称),即:

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(4)

FFT算法设计的基本思想,就是充分利用DFT的周期性和对称性,减少重复的计算量;并把N点长序列分成几个短序列,减少每个序列长度,可大大减少计算量。

实践中使用最多的FFT是“基2”算法。所谓“基2”,就是令DFT的点数N满足

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(5)

FFT基2算法分为时域抽取法(Decimation In Time)和频域抽取法(Decimation In Frequency)两大类。本文重点介绍其中的时域抽取法快速傅里叶变换(DIT-FFT),算法设计思想要点如下:

1、把长度为N的时域序列x(n)按n的奇偶分为两组,变成两个序列,长度均为N/2。即

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(6)

其中一个N/2点的DFT为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(7)

另一个N/2点的DFT为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(8)

2、不难推出原序列x(n)的N/2点DFT为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(9)

注意:上式仅是X(k)的前一半即N/2点运算,整个N点DFT结果还要加上后一半计算。如果老老实实计算后一半N/2点DFT,则并没有减少任何计算量。

但考虑可利用DFT及其变换因子的周期性和对称性,并利用前一半计算结果,后一半计算可表示为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(10)

这种“一分为二”的DFT算法叫做蝶形运算。可以看出其计算量为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(11)

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(12)

与普通的DFT相比,计算量减少了一半!

3、同理,如果把式(6)表示的时间序列“二分为四”,长度均为N/4,同时把式(9)、(10)中的N/2点DFT分解为N/4点的DFT,反复使用蝶形运算的方法,即

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(13)

后一半DFT为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(14)

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(15)

后一半DFT为

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(16)

计算量可在式(11)和(12)的基础上再减少一半!

4、依此类推,直到把长度为N的序列细分成N/2个2点序列为止,循环使用蝶形运算的方法,即把N点DFT分解成N/2个2点DFT运算。这样,计算量大大减少。由式(5)知

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(17)

则复数乘法总次数从原来的N^2减少为:

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(18)

复数加法总次数从原来的约N^2减少为:

(原创)快速傅里叶变换(FFT)(图) - 周法哲 - 周法哲的博客

(19)

假设N=1024,复数乘法从原来直接DFT计算的104万次,减少为5120次,计算速度提高约200倍!

综上所述,快速傅里叶变换(FFT)大大降低了数字信号处理中的运算量,它的价值在于节省了CPU的处理时间,使得更多更复杂的数字信号得以快速的处理,为实现信息的实时处理开辟了广阔的发展前景。因此,FFT是数字信号处理技术发展史上的一个重要里程碑。

作为其快速算法设计思想精髓的典型代表,基2算法的时域抽取法快速傅里叶变换(DIT-FFT)中的蝶形运算式(9)、(10)和(13)、(14)、(15)、(16)等公式,被英国科学期刊《物理世界》2004年10月号公布为读者选出的“科学界历来最伟大的公式”之一,并且名列第九。

同期推选出的“科学界历来最伟大的公式”还有许多,有兴趣的朋友们请查阅周法哲的博文《科学的皇后》栏目。

(作者:周法哲2009-8-9于广东)

  评论这张
 
阅读(17198)| 评论(29)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017