《数字信号处理》实验4.docVIP

《数字信号处理》实验四 FFT与DFT计算时间的比较及圆周卷积代替线性卷积的有效性实验 一 实验目的： 1：掌握FFT基2时间（或基2频率）抽选法，理解其提高减少乘法运算次数提高运算速度的原理。 2：掌握FFT圆周卷积实现线性卷积的原理， (1)、线性卷积的长度及运算量 设一离散线性移不变系统的冲激响应为,其输入信号为.其输出为.并且的长度为L点,的长度为M点,则： （ 。 线性卷积的乘法运算量为LM次，又由于FIR滤波器的特性是对称序列即，因而，乘法运算次数减半，即为LM/2。 （2）用FFT算的步骤： 流程图： 1． 2． 3． 4． 总运算量：次乘法。 （三）比较两者乘法运算量 ，当和长度相当时，若M较短时，e.g.为8，16，32时，圆周卷积的时间大于直接线性卷积的结果；当M=64时，两者的运算速度相当，当M超过64以后，M越长圆周卷积的速度越快。当输入序列对长度太长时，圆周卷积的优势也表现不出来，此时可用重叠相加法和重叠保留法，进行分段卷积，保障圆周卷积的优势。 二 实验内容及要求： 1; 对N=2048或4096点的离散时间信号x(n)，试用Matlab语言编程分别以DFT和FFT计算N个频率样值X(k), 比较两者所用时间的大小。 2对N/2点长的x(n)和N/2点长的h(n)，试用Matlab语言编程实现以圆周卷积代替线性卷积，并比较圆周卷积法和直接计算线性卷积两者的运算速度。 三 实验报告： 1：阐述FFT提高运算速度的原理，并以实验数据加以分析论证。 2：简述FFT圆周卷积实现线性卷积的原理，并比较直接计算线性卷积所需的乘法运算次数与以圆周卷积实现线性卷积所需的运算次数的定量关系式，以数据印证该方法的有效性。 3：要求实验报告字体工整和条理，论证说理应层次分明，数据和图形应用得当。 附：本实验用到的MATLAB指令 1 .N=1024; % DFT计算时长度不要超过4096点，否则耗时太长。 x=rand(N); %随机产生[0，1]间的随机数 2. t0=clock; %执行该指令时的时间赋予变量t0。 y1=conv(x,h); % conv(x,h)函数用来计算线性卷积。 direct_convolution_time=etime(clock,t0) ; % 计算[t0,当前指令结束时] 之间的时间 direct_convolution_time是一个变量，由用户定义它的名字。 3. x_zero=[x zeros(1,N/2)]; %在数组X的尾部补零N/2个后放在变量x_zero中。 4. figure(1); stem(y1); % figure(1)表示画第一个图，画图函数为stem（）函数 5. clear; %良好的编程习惯，一般在开始第一条语句放置该函数，将以前的变量置为inactive. 6. title(direct convolution result);%给一个图启名字。 7 . X=fft(x_zero);%用FFT的方法，计算信号x_zero的DFT。 8. Y2=X.*H; %两个序列相乘，结果也为同长度的序列 y2=ifft(Y2); %用IFFT的方法，计算信号的IDFT。 y2_real=real(y2); %real（）函数来求其实部。 9. A=dftmtx(N); X=x*A; %以上两种语句用来求解DFT，A为w矩阵。 通过比较直接计算线性卷积所需的乘法运算次数与以圆周卷积实现线性卷积所需的运算次数的定量关系式，分析FFT圆周卷积运算速度比直接计算线性卷积快，从而体现了FFT的应用价值。 FFT FFT IFFT