实验二 利用DFT计算线性卷积.doc

数字信号处理实验报告实验二 利用DFT计算线性卷积一、实验目的1.掌握利用FFT计算线性卷积的原理及具体实现方法。2.加深理解重叠相加法和重叠保留法。3.考察利用FFT计算线性卷积各种方法的适用范围。二、实验设备与环境计算机、MATLAB软件环境3、 实验基础理论1、线性卷积与圆周卷积设为L点序列，为M点序列，和的线性卷积为： 的长度为：L+M-1，和的N点圆周卷积为：其中：此时圆周卷积等于线性卷积，而圆周卷积可利用FFT计算。2、快速卷积利用FFT计算线性卷积步骤如下：（1）为了使线性卷积可以利用圆周卷积来计算，必须选择；同时为了能使用基2-FFT完成卷积运算，要求。采用补零的办法是和的长度均为N。（2）计算和的N点FFT（3）组成卷积（4）利用IFFT计算IDFT，得到线性卷积y(n)3、分段卷积我们考察单位取样响应为的线性系统，输入为，输出为，则当输入序列时再开始进行卷积，会使输出相对输入有较大的延时，再者如果序列太长，需要大量的存储单元。为此，我们把，分别求出每段的卷积，合在一起其到最后的总输出。这种方法称为分段卷积。分段卷积可细分为重叠相加法和重叠保留法。重叠保留法：设的长度为，的长度为M。我们把序列分成多段N点序列，每段与前一段重叠M-1个样本。由于第一段没有前一段保留信号，为了修正，我们在第一个输入段前面填充M-1个零。计算每一段的圆周卷积，则其每段卷积结果的前M-1个样本不等于线性卷积值，不是正确的样本值。所以我们将每段卷积结果的前M-1个样本舍去，只保留后面的N-M+1个正确输出样本，把这些输出样本合起来得到总的输出。利用FFT实现重叠保留法的步骤如下：（1）在前面填充M-1个零，扩大以后的序列为（2）将分为若干N点子段，设L=N-M+1为每一段的有效数据长度，则第i段的数据为：（3）计算每一段与的N点圆周卷积，利用FFT计算圆周卷积： （4）舍去每一段卷积结果的前M-1个样本，连接剩下样本，得到卷积结果。重叠相加法：设长度为M，将信号分解成长为L的子段，建议L选择与M数量级相同。以表示每段信号，则 每一段卷积的长度为L+M-1，所以在做求和时，相邻两段序列有M-1个样本重叠，即前一段的最后M-1个样本和下一段的前M-1个序列重叠，这个重叠部分相加，再与不重叠部分共同组成输出。 利用FFT实现重叠保留法的步骤如下： （1）将分为若干L点子段。 （2）计算每一段与的卷积，根据快速卷积算法利用FFT计算卷积。 （3）将各段（包括重叠部分）相加，得到输出。4、可能用到的MATLAB函数实验中FFT运算可采用MATLAB中提供的函数fft来实现。MATLAB提供了函数conv来计算线性卷积，实验中可以将编程计算的结果和conv函数的计算结果相比较，以验证结果的正确性，conv函数用法如下：y=conv(x,h), x和h为要进行卷积运算的两个序列，y为卷积结果统计程序运行时间可以利用MATLAB提供的tic和toc两个命令，具体用法如下：tic需要运行的程序代码toc即，在需要统计运行时间的程序代码前加上tic命令，之后加上toc命令，此时会在命令窗口中显示该程序的运行时间。四、实验内容假设要计算序列x(n)=u(n)-u(n-L),0nL和h(n)=cos(0.2pn),0nM的线性卷积，完成以下实验内容。1、设L=M，根据线性卷积的表达式和快速卷积的原理，分别编程实现计算两个序列线性卷积的方法，比较当序列长度分别为8,16,32，64,256,512,1024时，两种方法计算线性卷积所需时间。（1）、线性卷积实验代码：for n0=3:10L=2n0;x=ones(1,L);h=cos(0.2*pi.*x);ticy=conv(x,h);tocendElapsed time is 0.000511 seconds.Elapsed time is 0.000686 seconds.Elapsed time is 0.000091 seconds.Elapsed time is 0.000075 seconds.Elapsed time is 0.000098 seconds.Elapsed time is 0.000154 seconds.Elapsed time is 0.000289 seconds.Elapsed time is 0.000744 seconds.（2）、快速卷积实验代码：for n0=3:10L=2n0;M=2n0;x=ones(1,L),zeros(1,M-1);n2=0:M-1;h=cos(0.2*pi*n2),zeros(1,L-1);ticX=fft(x);H=fft(h);Y=X.*H;y=ifft(Y);tocendElapsed time is 0.000040 seconds.Elapsed time is 0.000020 seconds.Elapsed time is 0.000021 seconds.Elapsed time is 0.000039 seconds.Elapsed time is 0.000046 seconds.Elapsed time is 0.000079 seconds.Elapsed time is 0.000163 seconds.Elapsed time is 0.000426 seconds.数据分别为m=8,16,32,64,128,256,512,1024 的线性卷积和快速卷积用时，比较可知，快速卷积比线性卷积用时短。2、当L=2048且M=256时，比较直接计算线性卷积和快速卷积所需的时间，进一步考察当L=4096且M=256时两种算法所需的时间。实验代码：（1）l=2048,m=256x=ones(1,2048);h=cos(0.2*pi.*ones(1,256);ticy=conv(x,h);tocticX=fft(x,2048);H=fft(h,2048);Y=X.*H;y=ifft(Y);tocElapsed time is 0.003870 seconds.Elapsed time is 0.016573 seconds.(2) l=4096,m=256x=ones(1,4096);h=cos(0.2*pi.*ones(1,256);ticy=conv(x,h);tocticX=fft(x,4096);H=fft(h,4096);Y=X.*H;y=ifft(Y);tocElapsed time is 0.002199 seconds.Elapsed time is 0.008531 seconds.结论：快速卷积比线性卷积计算速度更快，计算所需要时间更短。3、编程实现利用重叠相加法计算两个序列的线性卷积，考察L=2048且M=256时计算线性卷积的时间，与2题的结果进行比较。实验代码和结果：M=256;L=2048;x=ones(1,L);n=0:M-1;h=cos(0.2*pi*n);N=L+M-1;y=zeros(1,N);subLen=M;subNum=L/M;subLenY=2*M-1;ticH=fft(h,2*M-1);for count=1:subNumx_temp=x(count-1)*subLen+1):(count*subLen);X=fft(x_temp,2*M-1);Y=X.*H;y_temp=ifft(Y,2*M-1);y(count-1)*subLen+1):(count*subLen+M-1)=y(count-1)*subLen+1):(count*subLen+M-1)+y_temp;endtocElapsed time is 0.006253 seconds.比较可知：线性卷积：Elapsed time is 0.003870 seconds.快速卷积：Elapsed time is 0.016573 seconds.重叠相加法：Elapsed time is 0.006253 seconds.结论：与第二问的结果进行比较，发现运用重叠相加法计算的结果较直接线性卷积或者快速卷积算法都慢。但此结果没有实际意义，其一，matlab中tic、toc函数测量出的时间本身不够准确，只能给出一个大概值；其二，重叠相加法的程序采用了多个循环结构，导致程序运行时间偏长。4、编程实现利用重叠保留法计算两个序列的线性卷积，考察L=2048且M=256时计算线性卷积的时间，与2题的结果进行比较。实验代码和实验结果如下：M=256;L=2048;x=ones(1,L);n=0:M-1;h=cos(0.2*pi*n);totalLenY=L+M-1;useLen=M;subLen=useLen+M-1;subNum=round(L/useLen);x_bar=zeros(1,M-1),x;ticH=fft(h,subLen);for count=1:subNumx_temp=x_bar(count-1)*useLen+1):(count-1)*useLen+subLen);X=fft(x_temp,subLen);Y=X.*H;y_temp=ifft(Y,subLen);y(count-1)*useLen+1):(count*useLen)=y_temp(M:subLen);endx_temp=x_bar(count*useLen+1):totalLenY);X=fft(x_temp,subLen);Y=X.*H;y_temp=ifft(Y,subLen);y(count*useLen+1):totalLenY)=y_temp(M:2*M-2);tocElapsed time is 0.016953 seconds.线性卷积：Elapsed time is 0.003870 seconds.快速卷积：Elapsed time is 0.016573 seconds.重叠保留法：Ela