fft算法实现(实验二).docx

《fft算法实现(实验二).docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验项目：FFT算法的实现实验课程：数字信号处理实验时间：2014年3月25日实验地点：理科实验大楼A222软件工程实验室成绩：1.实验目的掌握基于时间抽取的基2FFT算法原理和实现方法。2．实验报告要求根据实验程序框图，写出程序清单。自定义时域序列，分析实验结果，并用matlab自带的FFT程序验证程序正确性。3.实验原理与方法设序列x(n)的长度为N，且满足N=2M，M为自然数。按n的奇偶把x(n)分解为两个N/2点的子序列则x(n)的DFT为因为所以其中Ｘ1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT。X(k)又可表示为这样

2、，就将N点DFT分解为两个N/2点DFT的运算了。与第一次分解相同，将x1(r)和x2(r)还可以继续分解为两个N/4点DFT的运算。依次类推，经过M次分解，最后将N点DFT分解成N个1点DFT和M级蝶形运算，而1点DFT就是时域序列本身。仔细观察上图，还可以归纳出一些对编程有用的运算规律：第L级中，每个蝶形的两个输入数据相距B=2L－1个点；每级有B个不同的旋转因子；同一旋转因子对应着间隔为2L点的2M－L个蝶形。　　总结上述运算规律，便可采用下述运算方法。先从输入端(第1级)开始，逐级进行，共进行M级运算。在进行第L级运算时，依次求出B个不同的旋

3、转因子，每求出一个旋转因子，就计算完它对应的所有2M－L个蝶形。这样，我们可用三重循环程序实现DIT-FFT运算，程序框图如下图所示。其中，倒序部分的程序框图如下图所示：4．实验内容及步骤按照实验原理中的算法，用MATLAB编写实现算法的程序。5．实验程序及结果：程序代码：xn=[0,1,2,3,4,5,6,7]; N=length(xn); A=xn; %DIT_FFT NI=N/2; for I=1:N-1     if I

4、 end    T=N/2;    while NI>=T       NI= NI-T;       T=T/2;    end NI= NI+T; end disp('逆序x[n]:'),disp(A); %butterfly WN=exp(-i*2*pi/N); v=floor(log2(N)); for m=1:v     for k=0:2^m:N-1        for K=0:2^(m-1)-1            p=k+K;            q=p+2^(m-1);            r=2^(v-m)*mod(p,2^

5、m);           B(p+1)=A(p+1)+A(q+1)*WN^r;           B(q+1)=A(p+1)-A(q+1)*WN^r;        end    end A=B;  end disp('FFT_X[k]:'),disp(A);运行结果：