【含源代码】北邮dsp-MATLAB实验一重叠相加和重叠保留

1、标准Dsp-matlab 头验实验一：重叠相加法和重叠保留法的实现设计报告课题名称：学生姓名：班 级：班内序号：学 号：日 期：2015/06/15目录一、实验原理 二、Matlab源代码三、Matlab运行结果四、Matlab结果分析五、遇到的难题与解决方法 参考文献文案一、实验原理1、算法来源DFT是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端(时域和频域上)的序列是有限长的。DFT具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。 对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即

2、x(n)*h(n)=y(n)通常采用循环卷积降低运算量， 但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性卷积，成为了 DFT的一个重要应用。2、两种算法基本思想1)重叠相加法重叠相加法和重叠保留法的实质都是以逐段地方式通过循环卷积来完成线性卷积的计算。将输入序列x (n)进行分段，每段长为N,且N> M (M为有限长因果序列 h (n)的长度)，x (n) 逐段与h (n)进行循环卷积，在重叠保留法中需在x (n)序列首部加入长度为 M-1的0序列。在算法中，在获得 N个点的输入后，进行 N+M-1点循环卷积计算，之后输出N

3、个点。通过for循环逐段进行循环卷积， 使用fft和ifft计算两个有限长序列的 N点循环卷积结果。 重叠相加法是将待过滤的信号分割成长为N的若干段，如图1所示，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。每次输入N点序列，通过计算x(n)和h(n)的循环卷积实现线性卷积运算，将缓存的M-1点序列和卷积结果相加，并输出前 N点作为计算结果，同时缓存后M-1点，如此循环，直至所有分段计算完毕，则输出序列 y(n)为最终计算结果。询->l意循环卷积L-N+M-1h(n)M-1点缰.有前N点y(n)18 2.童老相加法算法示意国2)重叠保留法重叠保留法相当于将 x?和h

4、(?作循环卷积，然后找出循环卷积中相当于线性卷积的部分。在这种情况下，将序列y(n)分为长为N的若干段(如图3所示)，每个输入段和前一段有 M-1 个重叠点。此时只需要将发生重叠的前 M-1个点舍去，保留重叠的部分并输出，则可获得序 列y(n),算法如图4所示。G «-1 A号N点捺入后N点M+N-1 点循环卷快 v J修M3.重兽侬留法的分段示意图国人篁总箧町法示意图:、MatlabW代码1）重叠相加法重叠相加法源代码function Y=overplxqy(x,h,N)%利用循环卷积计算线性卷积%循环卷积采用频域计算方法，已FFT弋替DFT降低运算量Lx=length(x); %

5、序列长度M=length(h); %h(n)长度x=x,zeros(1,N-1);t=zeros(1,M-1);Y=zeros(1,Lx+M-1);a=floor(Lx/N);for k=0:aA=x(k*N+1:k*N+N);y1=fft(A,Lx+M-1); %利用 FFT 进行运算y2=fft(h,Lx+M-1);y3=y1.*y2;%频域相乘q=ifft(y3,Lx+M-1);%FFT反变换得循环卷积结果Y(k*N+1:k*N+M-1)=q(1:M-1)+t(1:M-1);Y(k*N+M:k*N+N尸q(M:N);t(1:M-1)=q(N+1:N+M-1);endY(1:Lx+M-1)

6、;%取出最终的输出序列1）重叠保留法重叠保留法源代码function Y=overlpsav(x,h,N)Lx=length(x);M=length(h);M1=M -1;L=N-M1;h=h,zeros(1,N-M);x=zeros(1,M1),x,zeros(1,N-1);a=floor (Lx+M1-1)/(L)+1;Y=zeros(1,N);for k=0:a-1xk=x(k*L+1:k*L+N);b=fft(xk,N);C=fft(h,N);Z=b.*C;Y(k+1,:)=ifft(Z,N);%FFT反变换得循环卷积结果endY=Y(:,M:N)'Y=(Y(:)%取出最终的输

7、出序列、Matlabl行结果ConirnfZ WindowNew to MATiAB? See看gyfor» 户口户，口！：Eli+1-口；m&；I x gy (kb h, K)acusi LODOd 乱 OQOO006a-3. (JMO -肌 MOO -L MM L GDOd I.OdM -L MM -9. ODOO» “CL%内比 AJMeeclpsavsqy 人工忖1. HOM机00Mt. OOdOi-3MM0TMMD-l.MOOI.MM4 I丸。M。75M作T龟巾也OMW«H1 =.KM>». om观。DOG-X0W5TEM。-I.

8、WOQl乐 QM-1. 0M-LS- OWWTJX。 MOM。由此可见，两种算法运行正常，计算正确。更多的测试也正确。算法正确。四、Matlabl吉果分析重叠相加算法具有可行性和实用性。 再从算法的空间复杂度来看，由空间复杂度为 0(1)。是重量相加法长度 序列由4101W10001000Q100.013151O.CM»2660.0189630.027J780.0748341000.0011750.0006050.0003190.0009170.01000710000.009-936O.OO2S240.000920.DO07460.0139271DOOO0.0741»10.

9、D271210.0066820.004060.00992210000G0.606933ON6s4760.0528520.0301060.0482451000CW6.0335282.48352603962060-2460520333871000000059,9377625.104663.B9744423281223.231499可以看出，同重叠相加法类似，随着数据规模的增大，运算耗时呈线性增长，算法的时 间复杂度为0(n),其中n为数据规模。同样由于分配的缓存空间只由分段长度确定，空 间复杂度为0(1)。综合考察，重叠保留法也具有较好的时间和空间复杂度。x(n)长度为N, y (n)长度为 M;

10、计算线性卷积y (n), y (n)可视为N个序列的叠加结果，序列长度为M,所以每生成一个序列需完成M次乘法，共需完成MN次乘法运算。这N个序列依次向右移动一位故需(N-1)(M-1 )次加法运算。按照fft和ifft计算线性卷积时， 设L=N=M-1,整个运算过程包含了 2个fft、一个ifft和L次 乘法运算，所以，按基 2频域抽选算法实现 fft或ifft ,共需完成(3Llog2L/2+L)次乘法和(3Llog2L )次加法运算。B-重叠保图法1g长度 杼叫潴、,A10100100010000100.0005120.0002250.0012490.0008810.008454100O.DOW140,0005140.0002720.000836SOOBSOZ10000.0092970.0024020.0002870.0006870.0111070,05674QOhlXO.OO&1220.0039410.0110531000000.5S88650.2168180.03917S0.0260440,042643100000052218792,1440890357280,23627703275391000000052.246422,022153.S9328223357253,251762五、遇到的难题