《实验十FFT实现快速卷积补充内容.doc》由会员分享，可在线阅读，更多相关《实验十FFT实现快速卷积补充内容.doc（3页珍藏版）》请在金锄头文库上搜索。
1、实验十 FFT实现快速卷积补充实验实验目的熟悉FFT、DFT、MYDITFFT函数的编写与使用，继而了解它们的计算速度。实验原理用MATLAB实现时间抽选的基2FFT算法，编写函数，并验证。function y=myditfft(x) 本程序对输入序列x实现时间抽选的基2FFT，点数取大于等于x长度的2的幂次m=nextpow2(x);N=2m; 求x的长度对应的2的最低幂次mif length(x)N x=x,zeros(1,N-length(x); endnxd=bin2dec(fliplr(dec2bin(1:N-1,m)+1; 1：2m数列的倒位序y=x(nxd); 将x倒位序排列作为
2、y的初始值for mm=1:m 将DFT作m次基2分解，从左到右 Nmr=2mm;u=1; 旋转因子u初始化wN=1 WN=exp(-i*2*pi/Nmr); 当前次分解的基本DFT因子wN=exp(-i*2*pi/Nmr) for j=1:Nmr/2 当前次跨越间隔内的各次蝶形运算 for k=j:Nmr:N 当前次蝶形运算的跨越间隔为Nmr2mm kp=k+Nmr/2; 确定蝶形运算的对应单元下标 t=y(kp)*u; 蝶形运算的乘积项 y(kp)=y(k)-t; 蝶形运算的减法项 y(k)=y(k)+t; 蝶形运算的加法项 end u=u*WN; 修改旋转因子，多乘一个基本DFT因子wN
3、 endend实验内容输入x=1 3 5 7 9;得：ans = Columns 1 through 4 25.0000 -10.8284 -12.0711i 5.0000 + 4.0000i -5.1716 - 2.0711i Columns 5 through 8 5.0000 -5.1716 + 2.0711i 5.0000 - 4.0000i -10.8284 +12.0711i编程执行FFT、DFT、MYDITFFT比较各个程序的执行速度：FFT为MATLAB内置函数，只需要编写DFT、MYDITFFT即可，程序编写如下：DFT程序：function y=mydft(x)N=leng
4、th(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程序：function y=myditfft(y)%本程序对输入序列X实现DIT-FFT基2算法，点数取大于等于x长度的2的幂次%-%y=myditfft(x)%m=nextpow2(z);N=2m; %求x的长度对应的2的最低幂次mif length(x)N x=x,zeros(1,N-length(x); %若x的长度不是2的幂，补零到2的整数幂endnxd=bin2dec(fliplr(dec2bin(1:N-1,m)+1; %求1：2
5、m数列的倒序y=x(nxd); %将x倒序排列作为y的初始值for mm=1:m %将DFT作m次基2分解，从左到右，对每次分解作DFT运算Nmr=2mm;u=1; %旋转因子u初始化为WN0=1WN=exp(-i*2*pi/Nmr); %本次分解的基本DFT因子WN=exp(-i*2*pi/Nmr) for j=1:Nmr/2; %本次跨越间隔内的各次蝶形运算 for k=j:Nmr:N %本次蝶形运算的跨越间隔为Nmr=2mm kp=k+Nmr/2; %确定蝶形运算的对应单元下标 t=y(kp)*u; %蝶形运算的乘积项 y(kp)=y(k)-t; %蝶形运算的加法项 y(k)=y(k)+
6、t; %蝶形运算的加法项 end u=u*WN; %修改旋转因子，多乘一个基本DFT因子WN endend时间测试函数：K=input(K=); x=randn(1,2K); tic,X=fft(x),toc tic,X=myditfft(x),toc tic,X=mydft(x),toc 将时间测试函数运行：FFT的计算耗时为：Elapsed time is 0.027777 seconds.MYDITFFT计算耗时为：Elapsed time is 0.021956 seconds.DFT计算耗时为：Elapsed time is 2.813184 seconds总结：由计算结果可知，三种运算方法说明了，FFT运算速度明显比DFT运算速度快得多。
