資源描述:
《離散傅里葉變換及其快速算法.docx》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、上機(jī)實(shí)驗(yàn)一:離散傅里葉變換及其快速算法一、設(shè)計(jì)目的通過編寫程序,深入理解快速傅里葉變換算法(FFT)的含義,完成FFT算法的軟件實(shí)現(xiàn)。二、設(shè)計(jì)任務(wù)利用時(shí)間抽取算法,編寫基2的快速傅立葉變換(FFT)程序,并在FFT程序基礎(chǔ)上編寫快速傅立葉反變換(IFFT)。三、設(shè)計(jì)要求1、FFT和IFFT子程序相對獨(dú)立、具有一般性,并加詳細(xì)注釋;2、驗(yàn)證例5-4,并能得到正確結(jié)果;四、設(shè)計(jì)條件C語言五、編程規(guī)則1)程序輸入元素的數(shù)目為2的整數(shù)次冪,即N為2M冪,整個(gè)運(yùn)算需要M級蝶形運(yùn)算。2)輸入序列按二進(jìn)制碼位倒置排列,輸出序列按自然順序排列。3)輸出數(shù)據(jù)占用輸入數(shù)據(jù)的存儲單元。4
2、)每一級含N/2個(gè)基本蝶形運(yùn)算。第L級中有N/2L個(gè)群,群與群間隔為2L。同一級中各個(gè)群的系數(shù)W分布相同。處于第L級的群的系數(shù)是2L.8)對于第L級的蝶形運(yùn)算,輸入數(shù)據(jù)的間隔為2L-1。根據(jù)上述要求,設(shè)計(jì)程序源代碼如下所示:#include#include#include#defineswap(a,b){floatT;T=(a);(a)=b;(b)=T;}voidfft(floatA[],floatB[],unsignedM)//蝶形運(yùn)算程序,A存實(shí)部,B存虛部,M是級數(shù){unsignedlongN,I,
3、J,K,L,LE,LE1,P,Q,R;floatWr,Wi,Wlr,Wli,WTr,WTi,theta,Tr,Ti;N=1<>1;//K=N>>1表示K=N/2while(K>=2&&J>=K)//while循環(huán)表示須向次高位進(jìn)一位{J-=K;K>>=1;//K>>=1表示K=K/2}J+=K;}for(L=1;L<=M;L++)//for循環(huán)為M級FFT運(yùn)算,外層循
4、環(huán)由級數(shù)L控制,執(zhí)行M次{LE=1<5、Q]=B[P]-Ti;A[P]+=Tr;B[P]+=Ti;}WTr=Wr;WTi=Wi;Wr=WTr*Wlr-WTi*Wli;Wi=WTr*Wli+WTi*Wlr;}}return;}}voidmain()//主程序{inti,M,N,lb;cout<<"請輸入轉(zhuǎn)換類別(FFT,請輸入1;IFFT,請輸入0)"<>lb;cout<<"請輸入序列長度N"<>N;float*A=newfloat[N];float*B=newfloat[N];M=log(N)/log(2);cout<<"請輸入序列的實(shí)部"<6、l;//輸入序列實(shí)部for(i=0;i>A[i];}cout<<"請輸入序列的虛部"<>B[i];}cout<7、fft(A,B,M);for(i=0;i