N为合数的FFT算法

2011-08-11 10:50:38来源: 互联网

上面讨论的以2为基(即N=2M)的时间抽选和频率抽选FFT算法,由于具有程序简单、 计算效率高、对存储量要求不很高等优点,因而在实际中得到了最广泛的应用。如果N不等于 2的幂2M,通常有两种处理办法:
(1)用补零的办法将x(n)延长为2M。例如N=60,可在序列x(n)的末尾填补4个0,即 令x(60)=x(61) =x(62)=x(63)=0,使N达到26=64,这样就可使用基2FFT算法。有限长序列补零以后,只是频谱的取样点有所增加而不会影响它的频谱X(ejω)的形状。
(2)采用以任意数为基数的FFT算法。
设N等于两个整数p和q 的乘积,即N=p·q,则可将N点DFT分解成p个q点DFT或q个p点DFT来计算。为此,首先将x(n) 分为p组,每组长为q,即

从而说明:一个N=p·q点的DFT可以用p个q点DFT来组成,如下图所示。

在最一般的情况下,设
     N=p1p2···pm,其中p1~pm是m个素因子。首先把N分解为两个因子,即N=p1q1,其中q1=p2p3···pm,并用以上讨论的方法将DFT分解为p1个q1点DFT; 然后,将q1分解为q1=p2q2,其中q2=p3p4···pm,即将每一个q1点DFT分解为p2个q2 点DFT;这样,通过m次分解,最后达到pm点 DFT。这种算法可以使DFT的运算获得最高效率。

关键字:算法

编辑:eeleader 引用地址:http://www.eeworld.com.cn/gykz/2011/0811/article_7984.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
算法

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved