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

[实验目的]

熟悉FFT、DFT、MYDITFFT函数的编写与使用，继而了解它们的计算速度。 [实验原理]

用MATLAB实现时间抽选的基2－FFT算法，编写函数，并验证。

function y=myditfft(x) ％本程序对输入序列x实现时间抽选的基2－FFT，

点数取大于等于x长度的2的幂次

m=nextpow2(x);N=2^m; ％求x的长度对应的2的最低幂次m if length(x)x=[x,zeros(1,N-length(x))]; end

nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; ％1：2^m数列的倒位序 y=x(nxd); ％将x倒位序排列作为y的初始值 for mm=1:m ％将DFT作m次基2分解，从左到右 Nmr=2^mm;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 ％当前次蝶形运算的跨越间隔为Nmr＝2^mm kp=k+Nmr/2; ％确定蝶形运算的对应单元下标 t=y(kp)*u; ％蝶形运算的乘积项 y(kp)=y(k)-t; ％蝶形运算的减法项 y(k)=y(k)+t; ％蝶形运算的加法项 end

u=u*WN; ％修改旋转因子，多乘一个基本DFT因子wN end

end

[实验内容]

输入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=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程序： function y=myditfft(y)

%本程序对输入序列X实现DIT-FFT基2算法，点数取大于等于x长度的2的幂次 %------------------------------------------------------------- %y=myditfft(x) %

m=nextpow2(z);N=2^m; %求x的长度对应的2的最低幂次m if length(x)x=[x,zeros(1,N-length(x))]; %若x的长度不是2的幂，补零到2的整数幂 end

nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; %求1：2^m数列的倒序 y=x(nxd); %将x倒序排列作为y的初始值

for mm=1:m %将DFT作m次基2分解，从左到右，对每次分解作DFT运算 Nmr=2^mm;u=1; %旋转因子u初始化为WN^0=1

WN=exp(-i*2*pi/Nmr); %本次分解的基本DFT因子WN=exp(-i*2*pi/Nmr) for j=1:Nmr/2; %本次跨越间隔内的各次蝶形运算

for k=j:Nmr:N %本次蝶形运算的跨越间隔为Nmr=2^mm kp=k+Nmr/2; %确定蝶形运算的对应单元下标 t=y(kp)*u; %蝶形运算的乘积项 y(kp)=y(k)-t; %蝶形运算的加法项 y(k)=y(k)+t; %蝶形运算的加法项 end

u=u*WN; %修改旋转因子，多乘一个基本DFT因子WN end end

时间测试函数：

K=input('K='); x=randn(1,2^K); 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运算速度快得多。