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
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:用FPGA实现FFT算法
下一篇:IFFT的计算方法

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利
推荐阅读
全部
算法

小广播

独家专题更多

东芝在线展会——芯科技智社会创未来
东芝在线展会——芯科技智社会创未来
2017东芝PCIM在线展会
2017东芝PCIM在线展会
TI车载信息娱乐系统的音视频解决方案
TI车载信息娱乐系统的音视频解决方案
汇总了TI汽车信息娱乐系统方案、优质音频解决方案、汽车娱乐系统和仪表盘参考设计相关的文档、视频等资源
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2017 EEWORLD.com.cn, Inc. All rights reserved