《FFT递推运算框图.doc》由会员分享，可在线阅读，更多相关《FFT递推运算框图.doc（3页珍藏版）》请在三一办公上搜索。
1、FFT递推运算框图外层的循环控制变量M，其中N输入数据的个数，一般取N为2的幂次方的整数，如果输入的数据的个数N2M，则在序列后面补零，让其达到N2M个，N,M均可以认为是事先给定的常数。 对上述的递推运算框图有如下几点说明：1) 该递推框图实现的程序是一个子程序块，调用时A，M，N由主程序赋值，因此在框图中，可以认为A，M，N是事先给定的常数。2) 框图中，共有级（列）蝶形，每级有N/2个蝶形。3) 框图中，用L表示运算的级数，则第L（L1，2，M）级中系数有个，它们是（可0，1，），U中存有，其起始值U。4）每一级各个系数对应的蝶形有个，它们依次相距LE=点。用循环变量I来控制同一种类型的
2、蝶算，显然步进为LE。这就是框图中的最内层循环。同一类蝶形中参加运算的两点相距为LE1点。用J来控制各个类型的蝶形都做到，J的步进为1，这对应于框图中的次内层循环。也可以认为框图中的最内层循环完成每级蝶式运算，次内层循环完成因子的运算。5）由L控制运算的级数。L由1变到M步进为1，对应于框图的最外层循环，每改变一个L值，则LE1、LE、系数U都会发生变化。框图中，U、W、T为存放复数单元，相应的乘法为复数乘法，系数用递推公式： （为乘号）上述FFT递推运算框图的FORTRAN程序实现如下：SUBROUTINE FFT(A,M,N)COMPLEX A(N),U,W,TN=NV2=N/2NM1=N
3、-1J=1a DO 7 I=1,NM1IF (IGEJ)GO TO 5T=A(J)A(J)=A(I)A(I)=T5 K=KV26 IF=(KGEJ)GO TO 7J=J-KK=K/2GO TO 67 J=J+KPI=3.14159b DO 20 L=1,MLE=LE1=LE/2U=(1.0,0.0)W=CMPLEX(cos(PI/FLOAT(LE1),-sin(PI/FLOAT(LE1)c DO 20 J=1,LE1d DO 10 I=J,N,LEIP=I+LE1T=A(IP) * UA(IP)=A(I)-T10 A(I)=A(I)+T20 U=U * WRETURNEND上述程序中，标号为a的DO循环来完成的是整序运算，然后整个FFT运算用三个嵌套循环完成，其中标号为d的DO循环完成每级蝶式运算，标号为c的DO循环完成因子的运算，标号为b的DO循环完成M级运算。
