基二算法设计FFT函数

《基二算法设计FFT函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四FFT一实验目的掌握FFT基2时间抽选法，理解其提高减少乘法运算次数提高运算速度的原理。二实验原理FFT算法将长序列的DFT分解为短序列的DFT。N点的DFT先分解为2个N/2点的DFT，每个N/2点的DFT又分解为N/4点的DFT，等等。最小变换的点数即所谓的“基数”。因此，基数为2的FFT算法的最小变换（或称蝶型）是2点的DFT。一般地，对N点FFT，对应于N个输入样值，有N个频域样值与之对应。以基2时间按抽选法为例，分解递推公式为：X1(K)和X2（K）分别对应时间序列x(n)的的偶、奇序列N/2点长的DFT，以此方法分解下去，得到两点长N/2为组的离散时间

2、分组结果。在一次由两点DFT复合产生4、8、16……到N点的最后结果。运算量由N*N次降为次乘法。三实验内容1.编写一函数实现按时间抽取的FFT算法。2.对N=16以及N=2048的离散时间信号RN(n)，分别用自己编写的FFT函数及DFT函数来计算其DFT结果，比较所用时间。四，实验程序及结果；（1）基二算法：functionX=jes_fft(xn)N=length(xn);W=exp(-j*2*pi/N);X=zeros(1,N);ifN>2forr=1:N/2a(r)=xn(2*r-1);b(r)=xn(2*r);endA=jes_fft(a);B=jes_ff

3、t(b);fork=1:N/2X(k)=A(k)+B(k)*W^(k-1);X(k+N/2)=A(k)-B(k)*W^(k-1);endelseA=xn(1)+xn(2);B=xn(1)-xn(2);X=[A,B];endk=0:N-1;stem(k,X,'filled')title('基二算法图像')ylabel('fft')xlabel('n')运行如下：A>>jes_fft([11111111])ans=80000000B>>jes_fft(ones(1,2048));（2）fft函数调用：functionX=tft(xn)N=length(xn);X=fft(x

4、n,N);k=0:N-1;title('基二算法图像')ylabel('fft')xlabel('n')stem(k,X,'filled')运行如下：tft([1111111111111111]);tft(ones(1,2048));五，结果分析：通过两个函数的运行比较，可知：运用基二算法所用时间比调用FFT函数所用时间长得多，说明不同算法所用时间不同。