实验十fft实现快速卷积补充内容

《实验十fft实现快速卷积补充内容》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验十FFT实现快速卷积补充实验[实验目的]熟悉FFT、DFT、MYDITFFT函数的编写与使用，继而了解它们的计算速度。[实验原理]用MATLAB实现时间抽选的基2－FFT算法，编写函数，并验证。functiony=myditfft(x)％本程序对输入序列x实现时间抽选的基2－FFT，点数取大于等于x长度的2的幂次m=nextpow2(x);N=2^m;％求x的长度对应的2的最低幂次miflength(x)

2、r(dec2bin([1:N]-1,m)))+1;％1：2^m数列的倒位序y=x(nxd);％将x倒位序排列作为y的初始值formm=1:m％将DFT作m次基2分解，从左到右Nmr=2^mm;u=1;％旋转因子u初始化wN=1WN=exp(-i*2*pi/Nmr);％当前次分解的基本DFT因子wN=exp(-i*2*pi/Nmr)forj=1:Nmr/2％当前次跨越间隔内的各次蝶形运算fork=j:Nmr:N％当前次蝶形运算的跨越间隔为Nmr＝2^mmkp=k+Nmr/2;％确定蝶形运算的对应单元下标t=

3、y(kp)*u;％蝶形运算的乘积项y(kp)=y(k)-t;％蝶形运算的减法项y(k)=y(k)+t;％蝶形运算的加法项endu=u*WN;％修改旋转因子，多乘一个基本DFT因子wNendend[实验内容]输入x=[13579];得：ans=Columns1through425.0000-10.8284-12.0711i5.0000+4.0000i-5.1716-2.0711iColumns5through85.0000-5.1716+2.0711i5.0000-4.0000i-10.8284+12.07

4、11i编程执行FFT、DFT、MYDITFFT比较各个程序的执行速度：FFT为MATLAB内置函数，只需要编写DFT、MYDITFFT即可，程序编写如下：DFT程序：functiony=mydft(x)N=length(x);n=0:N-1;k=n;WN=exp(-j*2*pi/N);nk=n'*k;WNnk=WN.^nk;Xk=x*WNnk;y=Xk;MYDITFFT程序：functiony=myditfft(y)%本程序对输入序列X实现DIT-FFT基2算法，点数取大于等于x长度的2的幂次%-----

5、--------------------------------------------------------%y=myditfft(x)%m=nextpow2(z);N=2^m;%求x的长度对应的2的最低幂次miflength(x)

6、m%将DFT作m次基2分解，从左到右，对每次分解作DFT运算Nmr=2^mm;u=1;%旋转因子u初始化为WN^0=1WN=exp(-i*2*pi/Nmr);%本次分解的基本DFT因子WN=exp(-i*2*pi/Nmr)forj=1:Nmr/2;%本次跨越间隔内的各次蝶形运算fork=j:Nmr:N%本次蝶形运算的跨越间隔为Nmr=2^mmkp=k+Nmr/2;%确定蝶形运算的对应单元下标t=y(kp)*u;%蝶形运算的乘积项y(kp)=y(k)-t;%蝶形运算的加法项y(k)=y(k)+t;%蝶形运算

7、的加法项endu=u*WN;%修改旋转因子，多乘一个基本DFT因子WNendend时间测试函数：K=input('K=');x=randn(1,2^K);tic,X=fft(x),toctic,X=myditfft(x),toctic,X=mydft(x),toc将时间测试函数运行：FFT的计算耗时为：Elapsedtimeis0.027777seconds.MYDITFFT计算耗时为：Elapsedtimeis0.021956seconds.DFT计算耗时为：Elapsedtimeis2.813184s

8、econds总结：由计算结果可知，三种运算方法说明了，FFT运算速度明显比DFT运算速度快得多。