实验3 利用FFT计算线性卷积.doc

《实验3 利用FFT计算线性卷积.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验3利用FFT计算线性卷积一、实验目的1.掌握利用FFT计算线性卷积的原理及具体实现方法。2.加深理解重叠相加法和重叠保留法。3.考察利用FFT计算线性卷积各种方法的适用围。二、实验设备与环境计算机、matlab软件环境。三、实验基础理论1.线型卷积和圆周卷积设x(n)为L点序列，h(n)为M点序列，x(n)和h(n)的线性卷积为的长度为L+M-1。x(n)和h(n)的N点圆周卷积为圆周卷积与线性卷积相等而不产生交叠的必要条件为圆周卷积定理：根据DFT的性质，x(n)和h(n)的N点圆周卷积的DFT等于它们DFT的乘积2.快速卷积快速卷积算法用圆周卷积实现线性卷积，

2、根据圆周卷积定理利用FFT算法实现圆周卷积。可以将快速卷积的步骤归纳如下：(1)为了使线性卷积可以用圆周卷积来计算，必须选择;同时为了能使用基-2FFT完成卷积运算，要求。采用补零的办法使x(n)和h(n)的长度均为N。(2)计算x(n)和h(n)的N点FFT(3)组成乘积(4)利用IFFT计算Y(K)的IDFT，得到线性卷积y(n)3.分段卷积我们考察单位取样响应为h(n)的线性系统，输入为x(n),输出为y(n)，则当输入序列x(n)极长时，如果要等x(n)全部集齐时再开始进行卷积，会使输出相对输入有较大的延时，再者如果序列太长，需要大量存贮单元。为此我们把x(n

3、)分段，分别求出每段的卷积，合在一起得到最后总的输出。这种方法称为分段卷积分段卷积可细分为重叠保留法和重叠相加法。重叠保留法：设x(n)的长度为，h(n)的长度为M。我们把序列x(n)分成多段N点序列(n),每段与前一段重叠M-1个样本。由于第一段没有前一段保留信号，为了修正，我们在第一个输入端前面填充M-1个零。计算每一段与h(n)的圆周卷积，则其每段卷积结果的前M-1个样本不等于线性卷积值，不是正确的样本值。所以我们将每段卷积结果的前M-1个样本社区，只保留后面的N-M+1个正确输出样本，把这些输出样本合起来，得到总输出。利用FFT实现重叠保留发的步骤如下：(1)

4、在x(n)前面填充M-1个零，扩大以后的序列为(1)将x(n)分为若干N点子段，设L=N-M+1为每一段的有效数据长度，则第i段(n)()的数据为(2)计算每一段与h(n)的N点圆周卷积，利用FFT计算圆周卷积：(3)舍去每一段卷积结果的前M-1个样本，连接剩下样本，得到卷积结果y(n)。重叠相加法：设h(n)长度为M，将信号x(n)分解成长为L的子段，建议L选择与的M数量级相同，以(n)表示没每段信号，则每一段卷积的长度为L+M-1,所以在做求和时，相邻两段序列有M-1个样本重叠，即前一段的最后M-1个样本喝下一段的前M-1个序列重叠，这个重叠部分相加，再与不重叠部

5、分共同组成输出y(n)。利用FFT实现重叠保留法的步骤如下：(1)将x(n)分为若干L点子段(n)。(2)计算每一段与h(n)的卷积，根据快速卷积算法利用FFT计算卷积。(3)将各段相加，得到输出y(n)四、实验容假设要计算序列x（n）=u（n）-u（n-L），0<=n<=L和h(n)=cos(0.2n),0<=n<=M的线性卷积，完成以下实验容1.设L=M，根据线性卷积的表达式和快速卷积的原理，分别编程实现计算两个序列线性卷积的方法，比较当序列长度分别为8,16,32,64,256,512,1024时，两种方法计算线性卷积所需时间。实验代码及结果：程序Exp3_1代

6、码L=input('L=');M=input('M=');xn=linspace(1,1,L);hn=cos(0.2*pi*[0:M-1]);yn1=zeros(1,L+M-1);ticfork=0:L+M-1forn=max([0k-M+1]):min([kL-1])yn1(k+1)=yn1(k+1)+xn(n+1)*hn(k-n+1);endendtocticXk=fft(xn,L+M-1);Hk=fft(hn,L+M-1);Yk=Xk.*Hk;yn2=ifft(Yk);toc>>Exp3_1L=8M=8Elapsedtimeis0.000136seconds.E

7、lapsedtimeis0.000033seconds.>>Exp3_1L=16M=16Elapsedtimeis0.000205seconds.Elapsedtimeis0.000030seconds.>>Exp3_1L=32M=32Elapsedtimeis0.000419seconds.Elapsedtimeis0.000056seconds.>>Exp3_1L=64M=64Elapsedtimeis0.000911seconds.Elapsedtimeis0.000117seconds.>>Exp3_1L=256M=256Elapsedtim