离散傅里叶变换及其快速算法.docx

《离散傅里叶变换及其快速算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上机实验一：离散傅里叶变换及其快速算法一、设计目的通过编写程序，深入理解快速傅里叶变换算法（FFT）的含义，完成FFT算法的软件实现。二、设计任务利用时间抽取算法，编写基2的快速傅立叶变换（FFT）程序，并在FFT程序基础上编写快速傅立叶反变换（IFFT）。三、设计要求1、FFT和IFFT子程序相对独立、具有一般性，并加详细注释；2、验证例5-4，并能得到正确结果；四、设计条件C语言五、编程规则1）程序输入元素的数目为2的整数次幂，即N为2M幂，整个运算需要M级蝶形运算。2）输入序列按二进制码位倒置排列，输出序列按自然顺序排列。3）输出数据占用输入数据的存储单元。4

2、）每一级含N/2个基本蝶形运算。第L级中有N/2L个群，群与群间隔为2L。同一级中各个群的系数W分布相同。处于第L级的群的系数是2L.8）对于第L级的蝶形运算，输入数据的间隔为2L-1。根据上述要求，设计程序源代码如下所示：#include#include#include#defineswap(a,b){floatT;T=(a);(a)=b;(b)=T;}voidfft(floatA[],floatB[],unsignedM)//蝶形运算程序，A存实部，B存虚部，M是级数{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循环表示须向次高位进一位{J-=K;K>>=1;//K>>=1表示K=K/2}J+=K;}for(L=1;L<=M;L++)//for循环为M级FFT运算,外层循

4、环由级数L控制，执行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<<"请输入转换类别(FFT，请输入1；IFFT，请输入0)"<>lb;cout<<"请输入序列长度N"<>N;float*A=newfloat[N];float*B=newfloat[N];M=log(N)/log(2);cout<<"请输入序列的实部"<

6、l;//输入序列实部for(i=0;i>A[i];}cout<<"请输入序列的虚部"<>B[i];}cout<

7、fft(A,B,M);for(i=0;i