新闻中心

EEPW首页 > 嵌入式系统 > 设计应用 > N为合数的FFT算法

N为合数的FFT算法

作者:时间:2011-06-06来源:网络收藏

上面讨论的以2为基(即N=2M)的时间抽选和频率抽选,由于具有程序简单、 计算效率高、对存储量要求不很高等优点,因而在实际中得到了最广泛的应用。如果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,这样就可使用基2。有限长序列补零以后,只是频谱的取样点有所增加而不会影响它的频谱X(ejω)的形状。
(2)采用以任意数为基数的
设N等于两个整数p和q 的乘积,即N=p·q,则可将N点DFT分解成p个q点DFT或q个p点DFT来计算。为此,首先将x(n) 分为p组,每组长为q,即

本文引用地址:http://www.eepw.com.cn/article/150638.htm

从而说明:一个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的运算获得最高效率。



关键词: 算法 FFT

评论


相关推荐

技术专区

关闭