案例十——线性卷积这样算会快

内容概要案例设置目的相关基础理论情境任务及步骤磨刀不误砍柴工探寻圆周卷积与线性卷积的等价关系挑战经典思考题总结报告要求

案例设置目的编制程序验证圆周卷积和线性卷积的等价条件，理解线性卷积与圆周卷积的关系，掌握用圆周卷积计算线性卷积的快速实现方法；理解MATLAB函数conv的算法基础；了解程序效率测试的基本方法。

相关基础理论设输入序列x(n)仅在0≤n≤N1-1范围内有非零值，系统单位脉冲?响应h(n)仅在0≤n≤N2-1范围内有非零值，二者的线性卷积yl(n)和N点圆周卷积yc(n)可分别表示为(10.1)(10.2)当圆周卷积计算点数N≥N1+N2-1时，在0≤n≤N-1范围内yl(n)和yc(n)完全相同，即yl(n)可以用计算yc(n)的方法进行计算。利用DFT的性质，圆周卷积可以这样计算：(10.3)其中Yc(k)=X(k)?H(k)。而根据序列DFT的定义，有限长序列x(n)的N（NN1）点DFT可表示为(10.4)

相关基础理论若将序列x(n)写成一个列向量x=[x(0),x(1),…,x(N-1)]T，当N≥M时x(M),…,x(N-1)取值为零，将N个X(k)值写成一个列向量X=[X(0),X(1),…,X(N-1)]T，此时式（10.4）可改写为：(10.5)h(n)的DFT结果H(k)也可用式（10.5）计算。综上，利用圆周卷积计算线性卷积的过程可以概括为如下五步（1）确定循环卷积长度N，其中N≥N1+N2-1。若采用基2-FFT实现DFT的快速运算，还要求N=2m（m为整数）。（2）用补零方法使x(n)和h(n)变成列长为N的序列，即(10.6)

相关基础理论（3）计算x(n)和h(n)的N点离散傅里叶变换?（H(k)只需计算一次）。（4）计算X(k)和H(k)乘积H(k)X(k)=Y(k)。（5）计算Y(k)的离散傅里叶反变换得?(10.7)从式（10.7）可以看出，序列的IFFT可以通过调用FFT的算法程序实现，因而线性卷积的计算过程仅需编制一个FFT程序，而不用再单独编写IFFT程序。利用圆周卷积计算线性卷积的流程如图10.1所示。图10.1利用FFT的快速卷积实现框图

情境任务及步骤一、磨刀不误砍柴工已知序列x1(n)={1,1,1,1}和x2(n)={1,2,3,4}。1.DFT怎么算、有何用（1）根据离散时间傅里叶变换的定义计算X1(ejω)，其中X1