FFT遞推運(yùn)算框圖

1、fft遞推運(yùn)算框圖外層的循環(huán)控制變量m，其中n輸入數(shù)據(jù)的個數(shù)，一般取n為2的冪次方的整數(shù)，如果輸入的數(shù)據(jù)的個數(shù)n2m，則在序列后面補(bǔ)零，讓其達(dá)到n2m個，n,m均可以認(rèn)為是事先給定的常數(shù)。 對上述的遞推運(yùn)算框圖有如下幾點(diǎn)說明：1) 該遞推框圖實(shí)現(xiàn)的程序是一個子程序塊，調(diào)用時a，m，n由主程序賦值，因此在框圖中，可以認(rèn)為a，m，n是事先給定的常數(shù)。2) 框圖中，共有級（列）蝶形，每級有n/2個蝶形。3) 框圖中，用l表示運(yùn)算的級數(shù)，則第l（l1，2，m）級中系數(shù)有個，它們是（可0，1，），u中存有，其起始值u。4）每一級各個系數(shù)對應(yīng)的蝶形有個，它們依次相距l(xiāng)e=點(diǎn)。用循環(huán)變量i來控制同一種類型的

2、蝶算，顯然步進(jìn)為le。這就是框圖中的最內(nèi)層循環(huán)。同一類蝶形中參加運(yùn)算的兩點(diǎn)相距為le1點(diǎn)。用j來控制各個類型的蝶形都做到，j的步進(jìn)為1，這對應(yīng)于框圖中的次內(nèi)層循環(huán)。也可以認(rèn)為框圖中的最內(nèi)層循環(huán)完成每級蝶式運(yùn)算，次內(nèi)層循環(huán)完成因子的運(yùn)算。5）由l控制運(yùn)算的級數(shù)。l由1變到m步進(jìn)為1，對應(yīng)于框圖的最外層循環(huán)，每改變一個l值，則le1、le、系數(shù)u都會發(fā)生變化?？驁D中，u、w、t為存放復(fù)數(shù)單元，相應(yīng)的乘法為復(fù)數(shù)乘法，系數(shù)用遞推公式： （為乘號）上述fft遞推運(yùn)算框圖的fortran程序?qū)崿F(xiàn)如下：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上述程序中，標(biāo)號為a的do循環(huán)來完成的是整序運(yùn)算，然后整個fft運(yùn)算用三個嵌套循環(huán)完成，其中標(biāo)號