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

数字信号处理实验报告1实验二利用DFT计算线性卷积一、实验目的1.掌握利用FFT计算线性卷积的原理及具体实现方法。2.加深理解重叠相加法和重叠保留法。3.考察利用FFT计算线性卷积各种方法的适用范围。二、实验设备与环境计算机、MATLAB软件环境三、实验基础理论1、线性卷积与圆周卷积设)(nx为L点序列，)(nh为M点序列，)(nx和)(nh的线性卷积为：mmnhmxnhnxny)()()(*)()()(ny的长度为：L+M-1，)(nx和)(nh的N点圆周卷积为：)())(()()(10nRmnhmxnyNNmN其中：1LMN此时圆周卷积等于线性卷积，而圆周卷积可利用FFT计算。2、快速卷积利用FFT计算线性卷积步骤如下：（1）为了使线性卷积可以利用圆周卷积来计算，必须选择；同时为了能使用基2-FFT完成卷积运算，要求2N。采用补零的办法是)(nx和)(nh的长度均为N。（2）计算)(nx和)(nh的N点FFT)()()()(kHnhkXnxFFTFFT（3）组成卷积)()()(kHkXkY（4）利用IFFT计算IDFT，得到线性卷积y(n)(k)()IFFTYyn3、分段卷积我们考察单位取样响应为)(nh的线性系统，输入为)(nx，输出为)(ny，则)(*)()(nhnxny数字信号处理实验报告2当输入序列时再开始进行卷积，会使输出相对输入有较大的延时，再者如果序列太长，需要大量的存储单元。为此，我们把，分别求出每段的卷积，合在一起其到最后的总输出。这种方法称为分段卷积。分段卷积可细分为重叠相加法和重叠保留法。重叠保留法：设)(nx的长度为XN，)(nh的长度为M。我们把序列)(nx分成多段N点序列)(nxi，每段与前一段重叠M-1个样本。由于第一段没有前一段保留信号，为了修正，我们在第一个输入段前面填充M-1个零。计算每一段)(nh的圆周卷积，则其每段卷积结果的前M-1个样本不等于线性卷积值，不是正确的样本值。所以我们将每段卷积结果的前M-1个样本舍去，只保留后面的N-M+1个正确输出样本，把这些输出样本合起来得到总的输出。利用FFT实现重叠保留法的步骤如下：（1）在)(nx前面填充M-1个零，扩大以后的序列为1ˆ(){0,0,0,()}Mxnxn个（2）将)(nx分为若干N点子段，设L=N-M+1为每一段的有效数据长度，则第i段)10)((nnnxi的数据为：)}(,0,...0,0{)()(nxxnmxi（3）计算每一段与)(nh的N点圆周卷积，利用FFT计算圆周卷积：)()()()()()()()()(nykYkHkXkYkHnhiFFTnxiIFFTiiiFFTikX（4）舍去每一段卷积结果的前M-1个样本，连接剩下样本，得到卷积结果)(ny。重叠相加法：设长度为M，将信号)(nx分解成长为L的子段，建议L选择与M数量级相同。以)(nxi表示每段信号，则0()()iixnxn数字信号处理实验报告3(),01()0,ixniLnLxn其它0()()()()iixnynxnhn每一段卷积)(nyi的长度为L+M-1，所以在做求和时，相邻两段序列有M-1个样本重叠，即前一段的最后M-1个样本和下一段的前M-1个序列重叠，这个重叠部分相加，再与不重叠部分共同组成输出)(ny。利用FFT实现重叠保留法的步骤如下：（1）将)(nx分为若干L点子段)(nxi。（2）计算每一段与)(nh的卷积)(nyi，根据快速卷积算法利用FFT计算卷积。（3）将各段)(nyi（包括重叠部分）相加，得到输出)(ny。0()()iiynyniL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),0nL和h(n)=cos(0.2n),0nM的线性卷积，完成以下实验内容。1、设L=M，根据线性卷积的表达式和快速卷积的原理，分别编程实现计算两个序列线性卷积的方法，比较当序列长度分别为8,16,32，64,256,512,1024时，两种方法计算线性卷积所需时间。（1）、线性卷积实验代码：forn0=3:10L=2^n0;x=ones(1,L);h=cos(0.2*pi.*x);数字信号处理实验报告4ticy=conv(x,h);tocendElapsedtimeis0.000511seconds.Elapsedtimeis0.000686seconds.Elapsedtimeis0.000091seconds.Elapsedtimeis0.000075seconds.Elapsedtimeis0.000098seconds.Elapsedtimeis0.000154seconds.Elapsedtimeis0.000289seconds.Elapsedtimeis0.000744seconds.（2）、快速卷积实验代码：forn0=3:10L=2^n0;M=2^n0;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);tocendElapsedtimeis0.000040seconds.Elapsedtimeis0.000020seconds.Elapsedtimeis0.000021seconds.Elapsedtimeis0.000039seconds.Elapsedtimeis0.000046seconds.Elapsedtimeis0.000079seconds.Elapsedtimeis0.000163seconds.Elapsedtimeis0.000426seconds.数据分别为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));tic数字信号处理实验报告5y=conv(x,h);tocticX=fft(x,2048);H=fft(h,2048);Y=X.*H;y=ifft(Y);tocElapsedtimeis0.003870seconds.Elapsedtimeis0.016573seconds.(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);tocElapsedtimeis0.002199seconds.Elapsedtimeis0.008531seconds.结论：快速卷积比线性卷积计算速度更快，计算所需要时间更短。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);forcount=1:subNumx_temp=x(((count-1)*subLen+1):(count*subLen));X=fft(x_temp,2*M-1);Y=X.*H;数字信号处理实验报告6y_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;endtocElapsedtimeis0.006253seconds.比较可知：线性卷积：Elapsedtimeis0.003870seconds.快速卷积：Elapsedtimeis0.016573seconds.重叠相加法：Elapsedtimeis0.006253seconds.结论：与第二问的结果进行比较，发现运用重叠相加法计算的结果较直接线性卷积或者快速卷积算法都慢。但此结果没有实际意义，其一，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);forcount=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);tocElapsedtimeis0.016953seconds.线性卷积：Elapsedtimeis0.003870seconds.数字信号处理实验报告7快速卷积：Elapsedtimeis0.016573seconds.重叠保留法：Elapsedtimeis0.016953seconds.结论：实验结果分析和上题一样，实验结果无实际意义。五、实验心得和实验体会此次实验，学习了如何利用FFT计算线性卷积和利用重叠相加法和重叠保留法计算长序列的线性卷积。通过比较直接计算线性卷积和利用FFT计算线性卷积，验证了FFT算法的高效率性，同时在统计重叠相加法和重叠保留法运算时间时，其中有许多循环环节，导致实际时间和理论运算时间出现了很大的偏差，从而无法得出正确结论。