精华内容
下载资源
问答
  • 主要讲解长度列与短序列卷积算法(或相关算法),重叠保留法和重叠相加法,通过公式推导其计算原理
  • MATLAB中的fft的重叠相加法和重叠保留法的实现
  • Matlab 实验一 重叠相加法和重叠保留法的实现 学院信息与通信工程学院 班级 学号 班内序号 姓名 一 实验原理 为了实现线性卷积的快速计算方法重叠相加法和重叠保留 法的实质都是以逐段地方式通过循环卷积来完成线性...
  • 重叠相加法和重叠保留法的原理

    万次阅读 2017-11-09 22:31:58
    重叠相加法和重叠保留法的原理

    重叠相加法和重叠保留法的原理

    DFT(FFT)的一个应用,就是计算线性卷积。

    h(n)x(n)长度分别为NM,对于L点循环卷积,若满足L>=N+M1,则有yc(n)=yl(n)

    对于两个序列长度相差很大的情况,例如M>>N,为了节省存储空间并实现实时处理,则需要采取将长序列分段的方法。因为可以通过求循环卷积来得到线性卷积,所以以下先讨论循环卷积的情况。

    仍然对于上述的h(n)x(n),当M>>N时,计算每一个yc(n)最多只需要N次(较短序列的长度)计算,即从x(nN+1)~x(n)之间的N个值。所以即便将x(n)分解也可以得到卷积结果。

    现将x(n)分解为许多长度为KKN的短序列x0(n),x1(n),x2(n)...。例如对于

    x2(n),0nK1
    N1nK1时,求得y2(n)所需的x(nN+1)~x(n)之间的N个值可完全由x2(n)提供,但是当0nN2时则无法只由x2(n)提供全部所需的x(n),为了解决这个问题便提出了重叠相加法和重叠保留法。
    1. 重叠相加法
      根据

      y(n)=h(n)x(n)=h(n)m=0xk(n)=m=0h(n)xk(n)=m=0yk(n)
      yk(n)求和即可得到原本的y(n),其本质就是对不完全的yk(n)进行补全,而原本就满足N1nK1yk(n)则实际上不改变其值。
    2. 重叠保留法
      此方法需x(n)分段时每两段之间需要重叠N1个值(实际上大于该值都可以,但取N1时最节省运算量),然后对所求的yk(n)去除前N1个点。本质就是直接删去0nN2yk(n),只保留N1nK1yk(n),因此在对分段时需要对x(n)重叠分段,保证对于每个n都有满足N1nK1xk(n)

    综上,对于两种方法,都是为了解决相同的问题,即x(n)分段后每段内前N1yk(n)不完全的问题。

    展开全文
  • 两个有限长的序列,当一个序列的长度远大于另外一个序列的时候,如果仍采用常规的处理方法,效率会很低,所以引入了重叠相加法和重叠保留法。下面我们就利用MATLAB来实现这两种方法。在下面的代码中,我使用了一个新...

    两个有限长的序列,当一个序列的长度远大于另外一个序列的时候,如果仍采用常规的处理方法,效率会很低,所以引入了重叠相加法和重叠保留法。下面我们就利用MATLAB来实现这两种方法。

    在下面的代码中,我使用了一个新的函数:tic和toc

    其中tic是标记起始位置,toc是返回从tic到toc运行的时间,这个函数在对程序的运行时间的测量中很有用处。

    下面进入代码阶段

    重叠相加法:

    MATLAB代码如下:

    %重叠相加法

    clear

    clc

    %NDFT的长度,Length为输入序列的长度,L为分块的长度,Mhn的长度

    N=16;

    Length=2000;

    L=10;

    M=7;

    %FIR滤波器的冲激响应设为hn

    hn=[4 5 2 6 3 8 1];

    Hk=fft(hn,N);

    %输入序列设置为xn

    n=0:Length-1;

    xn=sin(n*0.5)+0.8*cos(0.3*n);

    %下面的Length/L是特意设置成整数的,这样可以免去再补零的麻烦

    %设置变量s为循环的次数

    %设置变量s1用来表示数据块的始末位置

    s1=L+1;

    %由于第一次不需要进行相加操作,所以将第一次操作单独拿出来

    tic

    Xk=fft(xn(1:L),N);

    Yk=Xk.*Hk;

    yn=ifft(Yk);

    for s=2:Length/L

        Xk=fft(xn(s1:s1+L-1),N);

        Yk1=Xk.*Hk;

        yn1=ifft(Yk1)

        s1=s1+L;

        %下面进行相加操作,其中leyn的长度

        le=N*(s-1)-(s-2)*(M-1);

        for ss=1:M-1

            yn(le-(M-1-ss))=yn(le-(M-1-ss))+yn1(ss);

        end

        yn=[yn yn1(M:N)];

    end

    toc

    nn=0:Length+M-2;

    subplot(211)

    stem(nn,abs(yn))

    title('重叠相加法');

    %下面直接利用卷积运算来求解

    Hk2=fft(hn,Length+M-1);

    Xk2=fft(xn,Length+M-1);

    Yk2=Xk2.*Hk2;

    yn2=ifft(Yk2);

    subplot(212)

    stem(nn,abs(yn2))

    title('直接进行卷积运算');

    我得出的图像为:

    3cf490f7f70ee26ec81536d8446f0c4b.png

    这两张图像是一样的,也就说明重叠相加法代码的正确性。

    仿照着重叠相加法的代码,我又写了重叠保留法的代码。

    代码如下:

    %重叠保留法

    clear

    clc

    %NDFT的长度,Length为输入序列的长度,L为分块的长度,Mhn的长度

    N=16;

    Length=2000;

    L=10;

    M=7;

    %FIR滤波器的冲激响应设为hn

    hn=[4 5 2 6 3 8 1];

    Hk=fft(hn,N);

    %输入序列设为xn

    n=0:Length-1;

    xn=sin(n*0.5)+0.8*cos(0.3*n);

    %下面的Length/L为设置好的整数,设置变量s用来表示循环次数

    %设置变量s1用来代表数据块的始末位置

    s1=L+1;

    %由于第一次操作是在前面补0,所以将其单独拿出来

    tic

    zzero=zeros(1,M-1);

    Xk=fft([zzero xn(1:L)],N);

    Yk=Xk.*Hk;

    ynn=ifft(Yk);

    yn=ynn(M:N);

    for s=2:Length/L-1

        Xk=fft(xn(s1-M+1:s1+L-1),N);

        Yk1=Xk.*Hk;

        yn1=ifft(Yk1);

    s1=s1+L;

    %这一步是进行删除后保留操作

        yn=[yn yn1(M:N)];

    end

    %下面这部分很重要,是用来补全圆周卷积加上删去M-1个点带来的卷积结果最后缺失的M-1个点

    Xk=fft([xn(s1-M+1:s1+L-1)zzero],N+M-1);

    Hk1=fft(hn,N+M-1);

    Yk1=Xk.*Hk1;

    yn1=ifft(Yk1);

    yn=[yn yn1(M:N+M-1)];

    toc

    t1=end1-start1

    nn=0:Length+M-2;

    subplot(211)

    stem(nn,abs(yn))

    title('重叠保留法');

    %下面直接利用fft来求解

    tic

    Hk2=fft(hn,Length+M-1);

    Xk2=fft(xn,Length+M-1);

    Yk2=Xk2.*Hk2;

    yn2=ifft(Yk2);

    end2=cputime;

    toc

    subplot(212)

    stem(nn,abs(yn2))

    title('直接进行卷积运算');

    利用重叠保留法得出的图像为:

    b56216e00f071ae157fc84500d8a21a2.png

    验证两种方法的正确性之后,接着就要进行两种方法的比较了。

    先说一说我自己的猜测,重叠相加法和重叠保留法一样需要计算N点的DFT然后再做相乘运算,但是重叠相加法需要进行一部分的加法运算,而重叠保留法只需要进行舍弃,所以在运行的速度上,重叠保留法应该比重叠相加法快,下面用MATLAB来进行验证。

    首先对于重叠相加法

    这里分块长度设置为10

    序列长度\用时

    第一次/s

    第二次/s

    第三次/s

    平均/s

    100

    0.000054

    0.000078

    0.000069

    0.000067

    1000

    0.000491

    0.000574

    0.000339

    0.000468

    10000

    0.006452

    0.007675

    0.007388

    0.007171

    100000

    0.293490

    0.290030

    0.296175

    0.293232

    300000

    12.154479

    12.203386

    12.273594

    12.210486

    1000000

    172.542271

    177.408818

    174.062988

    174.671359

    对于重叠保留法

    分块长度设置为10

    序列长度\用时

    第一次/s

    第二次/s

    第三次/s

    平均/s

    100

    0.000082

    0.000086

    0.000073

    0.000080

    1000

    0.000370

    0.000363

    0.000380

    0.000371

    10000

    0.006206

    0.005914

    0.006031

    0.006050

    100000

    0.286666

    0.293388

    0.296384

    0.292146

    300000

    12.082273

    12.160706

    12.169543

    12.137507

    1000000

    171.820478

    171.657088

    172.928444

    172.135337

    可以看出在序列长度很大时,重叠保留法有略微的时间优势。

    由于增加分块长度等同于减小序列长度,所以说就不做增加分块长度的实验了。

    展开全文
  • Mlab 重叠保留法计算循环卷积 Mlab 重叠保留法计算循环卷积
  • 《重叠相加法和重叠保留法的原理与实现》由会员分享,可在线阅读,更多相关《重叠相加法和重叠保留法的原理与实现(4页珍藏版)》请在人人文库网上搜索。1、重叠相加法与重叠保存法的原理实现侯凯(吉林大学 通信工程...

    《重叠相加法和重叠保留法的原理与实现》由会员分享,可在线阅读,更多相关《重叠相加法和重叠保留法的原理与实现(4页珍藏版)》请在人人文库网上搜索。

    1、重叠相加法与重叠保存法的原理实现侯凯(吉林大学 通信工程学院 吉林 长春 )0概述线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。用圆周卷积计算线性卷积的方法归纳如下: 将长为N2的序列x(n)延长到L,补L-N2个零,将长为N1的序列h(n)延长到L,补L-N1个零。如果LN1+N2-1,则圆周卷积与线性卷积相等,此时,可有FFT计算线性卷积,方法如下: a.计算X(k)=FFTx(n) b.求H(k)=FFTh(n) c.求Y(k)=H(k)Y(k) k=0L-1 d.求y(n)=IFFTY(k) n=0L-1 可见,只要进行二次FFT,一次IFF。

    2、T就可完成线性卷积计算。上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况,如果x(n)、h(n)长度相差较多。例如,h(n)为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号x(n),或者处理一个连续不断的信号,按上述方法,h(n)要补许多零再进行计算,计算量有很大的浪费,或者根本不能实现。为了保持快速卷积法的优越性,可将x(n)分为许多段后处理,每小段的长与h(n)接近,其处理方法有两种:重叠相加法和重叠保留法。1重叠相加法由分段卷积的各段相加构成总的卷积输出假定xi(n)表示图中第i段x(n)序列如下图:则输入序列可表为: 图1 长序列分段滤波于是输出可分解为: 。

    3、其中 由此表明,只要将x(n)的每一段分别与h(n)卷积,然后再将这些卷积结果相加起来就可得到输出序列,这样,每一段的卷积都可用上面讨论的快速卷积来计算。先对h(n)及xi(n)补零,补到具有N点长度,N=N1+N2-1。 一般选择N=2M,然后用基2 FFT算法通过正反变换计算 由于yi(n)长度为N,而xi(n)的长度为N2,因此相邻两yi(n)序列必然有N-N2=N1-1点发生重叠,这个重叠部分应该相加起来才能构成最后的输出序列。 计算步骤: a. 事先准备好滤波器参数,N点 b.用N点FFT计算c.d.用N点IFFT求e.将重叠部分相加 图2 重叠相加法示意图2重叠保存法这种方法和第一。

    4、种方法稍有不同,即将上面分图序列中补零的部分不是补零,而是保留原来的输入序列值,且保留在各段的前端,这时,如利用DFT实现h(n)和xi(n)的圆周卷积,则每段卷积结果的前N1-1个点不等于线性卷积值需舍去。 为了清楚地看出这点,研究一下x(n)中一段长为N的序列xi(n)与h(n)(长为N1)的圆周卷积情况: 由于h(n)的长度为N1,当0nN1-2时,h(n-m)N将在xi(m)的尾部出现有非零值,所以0nN1-2这部分yi(n)值中将混入xi(m)尾部与h(n-m)N的卷积值,从而使yi(n)不同于线性卷积结果,但当n=N1-1N-1时,则有h(n-m)N =h(n-m),因此从n=N1。

    5、-1点开始圆周圈卷积值完全与线性卷积值一样,yi(n)的后面N2点才是正确的卷积值,而每一段卷积运算结果的前N1-1点个值需去掉。图2 重叠保留过程为了不造成输出信号遗漏,对x(n)分段时,需使相邻两段有N1-1个点的重叠(对于第一段,x(n)由于没有前一段保留信号,在其前填补N1-1点个零点)。为此将xi(n)定义为 每段和h(n)的圆周卷积以yi(n)表示, ,由FFT算出,去掉yi(n)的前N1-1点,再把相邻各段输出顺次连接起来就构成了最终的输出序列y(n)。 重叠保留法每一输入段均由N-N1+1=N2个新点和前一段保留下来的N1-1个点所组成。值得注意的是,对于有限长时间序列x(n)。

    6、(长度为L=MN2),在结束段(i=M-1)做完后,我们所得到的只是L点的线性卷积,还少了N1-1点,实际上就是h(-n)移出x(n)尾部时的不完全重合点,或者说是最后一段的重叠部分N1-1少做了一次卷积,为此,因再补做这一段N1-1点,在其后填补N2点个零点保证长度仍为N点,一样舍去前取N1-1点,并从N1-1点开始,保留N1-1点。 重叠保留法与重叠相加法的计算量差不多,但省去了重叠相加法最后的相加运算。一般来说,用FFT作信号滤波,只用于FIR滤波器阶数h(n)大于32的情况下,且取N2=(510)N1,这样可接近于最高效的运算。3应用举例例:已知有长序列X=1,2,3,4,5,6,7,。

    7、8,9,1,2,3,4,5,6,7,8,9,0,0,1,2,3,4,5,6,7,8,9,0, h=3,2,1,4,5,求线性卷积。解:重叠相加法得:Y=3,8,14,24,39,54,69,84,99,87,84,90,69,39,54,69,84,99,84,76,79,53,14,24,39,54,69,84,99,84,76,76,45,0程序:function Y=overpl(x,h,N) %N为分段段长度;x为长序列;h为短序列Lx=length(x);M=length(h);x=x,zeros(1,N);t=zeros(1,M-1);Y=zeros(1,Lx+M-1);a=flo。

    8、or(Lx/N);y2=fft(h,N+M-1);for K=0:a %循环a+1次A=x(K*N+1:K*N+N);y1=fft(A,N+M-1);y3=y1.*y2;q=ifft(y3,N+M-1);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=Y(1:Lx+M-1);重叠保留法:结果与上述相同,程序如下:function Y=overlpsav(x,h,N)%N为分段长度;x为输入长序列;h为短序列Lx=length(x);M=length(h);L=M+N-1; %分段后的总长度x=zeros(1,M-1),x,zeros(1,N);a=floor(Lx+M-1)/N);c=fft(h,L);for K=0:axk=x(K*N+1:K*N+L);b=fft(xk,L);H=ifft(b.*c,L);Y(K*N+1:K*N+N)=H(M:L);endY=Y(1:Lx+M-1。

    展开全文
  • %重叠保留法 clc;close all;clear all; xk=[1 2 3 4 5];%子序列 h=[1 2 1];%短序列 N=5;M=3;%长度 for k=1:6 x((k-1)N+1:kN)=xk;%长序列 end Hk=fft(h,N+M-1);%短序列的DFT y=zeros(1,M+N*6-1);%规定线性...

    %重叠保留法
    clc;close all;clear all;
    xk=[1 2 3 4 5];%子序列
    h=[1 2 1];%短序列
    N=5;M=3;%长度
    for k=1:6
    x((k-1)N+1:kN)=xk;%长序列
    end
    Hk=fft(h,N+M-1);%短序列的DFT
    y=zeros(1,M+N*6-1);%规定线性卷积序列的总长度
    overlap=zeros(1,M-1);
    y(1:N+M-1)=ifft(fft([overlap x(1:N)],N+M-1).*Hk);
    y(1:N)=y(M:N+M-1);%舍弃前M-1点
    for k=2:6
    overlap=x((k-1)*N-M+2:(k-1)*N);%向前重复取的数据
    yk=ifft(fft([overlap x((k-1)N+1:kN)],N+M-1).*Hk);
    y((k-1)N+1:kN)=yk(M:N+M-1);%舍弃前M-1点
    end
    k=k+1;
    overlap=x((k-1)*N-M+2:(k-1)*N);
    yk=ifft(fft([overlap zeros(1,N)],N+M-1).*Hk);
    y((k-1)N+1:kN)=yk(M:N+M-1);%舍弃前M-1点
    figure;
    stem(0:length(y)-1,y,‘bp’,‘linewidth’,1);
    xlabel(‘n’,‘fontsize’,15);ylabel(‘y(n)’,‘fontsize’,15);

    %重叠相加法
    clc;close all;clear all;
    xk=[1 2 3 4 5];%子序列
    h=[1 2 1];%短序列
    N=5;M=3;%长度
    for k=1:6
    x((k-1)N+1:kN)=xk;%长序列
    end
    Hk=fft(h,N+M-1);
    y=zeros(1,M+N*6-1);%规定线性卷积序列的总长度
    y(1:N+M-1)=ifft(fft(x(1:N),N+M-1).*Hk);%求前(N+M-1)点的线性卷积
    for k=2:6
    yk=ifft(fft(x((k-1)N+1:kN),N+M-1).*Hk);
    y((k-1)*N+1:(k-1)*N+M-1)=yk(1:M-1)+y((k-1)*N+1:(k-1)*N+M-1);%重叠相加
    y((k-1)N+M:kN+M-1)=yk(M:N+M-1);
    end
    figure;
    stem(0:length(y)-1,y,‘bp’,‘linewidth’,1);
    xlabel(‘n’,‘fontsize’,15);ylabel(‘y(n)’,‘fontsize’,15);

    展开全文
  • 用Mat实现重叠保留法计算循环卷积 来回。print find see
  • 重叠保留法实现长短相差很大的序列的线性卷积
  • 重叠相加法&重叠保留法

    万次阅读 多人点赞 2017-09-07 15:28:29
    重叠保留法(OLS) 将 x ( n ) x ( n ) x(n) 分段,每段长为 M M M ,保证 M M M 接近 N N N 即可,然后 将每段 x k ( n ) x k ( n ) x_{k}(n) 向前多取 N − 1 N − 1 N-1 个点,第一段前面补 N − 1 N − 1 N...
  • 两个有限长的序列,当一个序列的长度远大于另外一个序列的时候,如果仍采用常规的处理方法,效率会很低,所以引入了重叠相加法和重叠保留法。下面我们就利用MATLAB来实现这两种方法。 在下面的代码中,我使用了一个...
  • y3(1:2),y3(3:6)] 上面代码为了看的更清楚,循环都不用了,可以对比看看结果直接计算的y_conv与y_ola是不是相等的 重叠保留法(OLS) 将x(n) x ( n )分段,每段长为M M,保证M M接近N N即可,然后 将每段xk(n) x k ( ...
  • 相比于十分“直接”的重叠相加法,重叠保留法显得有点绕。那些字母加来减去的,各段和总输出的表达式让人眼花缭乱。花了些力气捋了捋清楚,记录于斯。 看字母太抽象太烦可以滑到后面例子对照理解。 设h(n)序列长M...
  • 利用matlab中的fft函数和重叠保留法思想计算快速卷积,注释非常全面,代码清晰明了,可以通用,要将函数改一下就可以了
  • 文章目录 重叠相加法 重叠保留法 重叠相加法 %-------------------------------------------------------------------------- % 清空一切 clc;clear all;close all; %---------------------------------------------...
  • 时域中的循环卷积对应于其离散傅里叶变换的乘积 线性卷积 通常所说的卷积就是指线性卷积,设x(n)、h(n)长度分别为M和N,则它们的线性卷积结果为 重叠保留法(OLS) 将x(n)分段,每段长为M,保证M接近N即可,然后 将...
  • DFT计算线性卷积——重叠保留法

    万次阅读 2016-09-25 23:07:45
    DFT计算线性卷积——重叠保留法引入设h(n)和x(n)都是有限长序列,长度分别为N和M。它们的线性卷积和循环卷积分别表示如下: yc(n)=h(n)∗x(n)=∑m=0N−1h(m)x(n−m)y_c(n)=h(n)*x(n)=\sum_{m=0}^{N-1}h(m)x(n-m) ...
  • matlab重叠保留法

    千次阅读 2012-12-20 16:50:46
    考试的时候急着交卷给人传答案,没好好做, 唉,现在发现这个题目很有价值 clear clc load mtlb ws=2000/Fs;...%保留前一段的24个点 L=103;%除去首末两段,中间38段每段103个点 P=103;%每段要
  • 空间 function [y] = hsolpsave(x,h,N) % High-speed Overlap-Save method of block convolutions using FFT % -------------------------------------------------------------- % [y] = hsolpsav(x,h,N) ...
  • 要点: 以分段5,\(h(n)\)长度为3举例 重叠保留法,输出的每一段都是长3和长5的5点圆周卷积,重叠的是最左边(3-1=2)个,这2个扔掉 重叠相加法,输出的每一段都是长3和长5的线性卷积 分段一般是有讲究的: 每段多长,...
  • Dsp-matlab 实验 实验一重叠相加法和重叠保留法的实现 设 计 报 告 课题名称 学生姓名 班 级 班内序号 学 号 日 期 2015/06/15 目录 Word 资料 . 一实验原理 二 Matlab 源代码 三 Matlab 运行结果 四 Matlab 结果...
  • 电路学:卷积的原理是根据线性定常电路的性质(齐次性、叠加性、时不变性、积分性等),借助电路的单位冲激响应h(t),求解系统响应的工具,系统的激励一般都可以表示为冲击函数和激励的函数的卷积,而卷积为高等数学...

空空如也

空空如也

1 2 3 4 5
收藏数 95
精华内容 38
关键字:

重叠保留法