一种少数点FFT递归算法

《一种少数点FFT递归算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、振动与冲击第25卷第2期JOURNALOFVIBRATIONANDSHOCKVo.l25No.22006*一种少数点FFT递归算法1,21赵建洋张令弥(11南京航空航天大学振动工程研究所,南京210016;2.淮阴工学院计算机系,淮安223001)摘要FFT广泛应用于数字信号处理中,其算法主要为"同址运算"FFT算法,即使用从前往后逐层算出各结点的数据,因其在计算时总是用当前层替代前一层,具有地址不变的关系而得名,该算法在计算全部分析点数据时具有很高的效率,但是在大部分应用中求出全部谱线是多余的。给出了一种只求有限谱线的高效方法的递归表达式及推导过程,以及在使用此方法的旋转

2、因子的规范化处理方法,比较了此方法与传统方法的时间与空间的效率,得出此方法在计算谱线数少于层数时具有更高的效率,而占用空间大小只有传统方法的1/3。列举了几种应用实例,说明了用于系统计算机时程序编制的方法,特别说明了用于嵌入式系统中的表达式及生成方法,具有更直接和方便的应用形式。这些方法特别适用于少数谱线的分析,如ZOOM分析、实验模态分析、局部谱线识别数字信号处理中。关键词:少数点蝶形FFT,递归表达式,旋转因子规范化,直接FFT多项式中图分类号:TN911.72;TP301文献标识码:A点,而从图1可以看出,如果只求图中X4,那么只涉及0引言图中/箭头0线经过的结点,而

3、与其它结点关系,因此作[9,10]许多文献都介绍了蝶形FFT(FastFourierTrans-者在中只给出频率抽取的一个递归关系。[1]form)的算法,进行了图解(如图1),给出经典的/同为解决上述问题,本文给出一种时间抽取少数点址运算0迭代算法,为叙述清楚起见,对图1作一些约递归算法(RecursionAlgorithmforSparsePoints-定:规定从左到右每一列为一层,用m(m=1,,,L)表RASP),据此写出的多项式生成程序和直接多项式法[2]示。节点所在行从上到下每一行为一个自然序号用在计算少数点时有很高的效率。k(k=0,,,N-1)表示,这样节点

4、Xm,k就表示第m层1少数点递归算法(RASP)的第k个节点,习惯上将第一列和最后一列的层下标省去,分别表示为xk和Xk。要得到指定频点Xk的值,可以从最后一层开始,根/同址运算0(SameAddressAlgorithm-SAA)迭代据递推关系进行递归,其递推关系由以下两定理给出:算法是从第一层开始,以m层的各个节点Xm,k作为已定理1:设采样点数为N,FFT总层数为L=知点,将(m+1)层的各个节点Xm+1,k迭代出来,直到算log2N,节点Xm,k表示第m(m=1,,,L)层的对应于第k出最后一层为止,为了节省存储空间,将已算得的对应(k=0,,,N-1)个元素,Xm

5、-1,K项为斜线通节点,节点数据替换前一节点,对应数据作为下一轮迭代的MXm-1,k项为直通节点,wL为旋转因子,xk和xK为样本已知数据,/同址运算0由此得名,该算法容易实现,利值(自然序列图1最左列),则用旋转因子中出现1处进行基分解(split-radix)省去xK+xk(kK)计算全部谱线时效率很高,但是在计算局部谱线时存Xm,k=MXm-1,k+wm#Xm-1,k(kK)首先,分析FFT结果的特点可知X(k)与X(N

6、-(2)k)有:证明:由图1知

7、Xk

8、=

9、XN-k

10、(1)当m=1时arg(Xk)=-arg(X(N-k))Mwm=1,(其中L=log2N,M由定理2确定)上式表明对N点的FFT只要求出(0-N/2)点,利用对当k

11、963年生第2期赵建洋等:一种少数点FFT递归算法49w图116点时间抽取蝶形FFT图解当k>K时K的序号为X1,k=X0,K-X0,k=xK-xkm-1km-1K=(kmod2)+Intm-1+1mod2#2证毕。当mX1时2且当kK时上述算法的推导中有许多关于取余运算(mod)、取MMXm,k=Xm-1,k-wm#Xm-1,K整运算(Int[])和旋转因子wm等复杂的表达式,应用X1,k=X0,K-X0,k=xK-xk证毕。中如果直接引用会影