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

周法哲的博客

重新认识我们的世界

 
 
 

日志

 
 
关于我

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

网易考拉推荐

(原创)DFT的计算量及对称性(图)  

2009-08-07 00:28:46|  分类: 信息科学札记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

上一回说到,为了克服DFT存在的栅栏效应、频谱泄漏和混叠失真等问题,可以增加采样点数N。但点数N的增加又会带来DFT计算量呈幂函数规律大幅度增加。即对于长度为N有限长序列x(n),完成其一个N点DFT

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(1)

需要进行的计算量为:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(2)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(3)

完成一个如下的逆变换运算量亦然:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(4)

假设一个点数N=1024的信号,则DFT计算量仅复数乘法运算就高达104万次以上。现在工程技术实际中采样点数N可达

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(5)

那么仅复数乘法计算量就高达

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(6)

简直是天文数字!如果有许多路信号序列的实时控制系统,你让计算机怎么来得及处理啊?可见我们必须千方百计减少DFT的运算量!科学家们首先想到的就是利用DFT的“对称性”。

一、复共轭序列的DFT

我们知道DFT中的序列都可以表示为复数项级数,那么自然就有与之相对的复共轭序列。

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客的复共轭序列,长度也为N,若

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(7)

则复共轭序列的离散傅里叶变换为

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(8)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(9)

证明:由DFT的定义式(1)有

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(10)

注意上式中使用了

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(11)

且因为DFT的概念是建立在周期序列的基础之上的,所以X(k)隐含周期性,根据DFT的定义式(1)便有

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(12)

即DFT的末点就是其起始点。证毕。

同理可证

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(13)

二、共轭对称性的定义

根据序列的偶对称和奇对称性质,有限长共轭对称序列定义为

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(14)

有限长共轭反对称序列定义为

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(15)

由此推论出

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(16)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(17)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(18)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(19)

注意:上述结论对频域序列X(k)也成立。

此处的对称性指关于变换区间中点(N/2点)的对称性。因为x(n)和X(k)均是区间[0,N-1]上的有限长序列。

三、序列表示为共轭对称部分和共轭反对称部分时的DFT

因为任何有限长序列x(n)都可以表示为其共轭对称部分和共轭反对称部分之和,即:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(20)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(21)

其中,X(k)的实部对应于x(n)的共轭对称部分的DFT:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(22)

X(k)的虚部(包括虚数单位j)对应于x(n)的共轭反对称部分的DFT:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(23)

四、序列表示为实部和虚部时的DFT

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(24)

其中序列的实部为

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(25)

序列的虚部(包括虚数单位j)为

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(26)

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(27)

其中,X(k)的共轭对称部分对应于x(n)的实部的DFT:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(28)

X(k)的共轭反对称部分对应于x(n)的虚部(含j)的DFT:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(29)

五、实序列的DFT

特殊地,如果有实序列:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(30)

则其DFT

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(31)

此时不难由式(8)推论出

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(32)

六、DFT的共轭对称性的应用

利用共轭对称性,进行一次DFT可以变换两个实序列。即构建一个新的序列:

(原创)DFT的计算量及对称性(图) - 周法哲 - 周法哲的博客

(33)

利用上述理论和式(32)可减少一半计算量。

科学界正是从千方百计减少DFT的计算量出发,创造出了快速傅里叶变换(FFT),其中用途最广的一种FFT算法公式,成为科学界历来最伟大的公式之一。详情且听周法哲下回分解。

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

  评论这张
 
阅读(5486)| 评论(17)
推荐 转载

历史上的今天

评论

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

页脚

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