重叠相加法与重叠保存法的原理实现

侯凯

（吉林大学 通信工程学院吉林 长春 130012）

0概述

线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等。

用圆周卷积计算线性卷积的方法归纳如下:

将长为N₂的序列x(n)延长到L,补L-N₂个零，将长为N₁的序列h(n)延长到L,补L-N₁个零。如果L≥N1+N2-1,则圆周卷积与线性卷积相等，此时,可有FFT计算线性卷积，方法如下：

        a.计算X(k)=FFT[x(n)]

        b.求H(k)=FFT[h(n)]

        c.求Y(k)=H(k)Y(k)         k=0～L-1

        d.求y(n)=IFFT[Y(k)]       n=0～L-1

 可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。

上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况，如果x(n)、h(n)长度相差较多。例如，h(n)为某滤波器的单位脉冲响应,长度有限，用来处理一个很长的输入信号x(n)，或者处理一个连续不断的信号，按上述方法，h(n)要补许多零再进行计算，计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性，可将x(n)分为许多段后处理，每小段的长与h(n)接近，其处理方法有两种：重叠相加法和重叠保留法。

1重叠相加法——由分段卷积的各段相加构成总的卷积输出

假定x_i(n)表示图中第i段x(n)序列如下图：

http://s11/mw690/002su48Cgy6HOHuwYb01a&690

http://s3/mw690/002su48Cgy6HOHBKeRQc2&690

图2  重叠相加法示意图

2重叠保存法

http://s15/mw690/002su48Cgy6HOHKBB6u7e&690

http://s2/mw690/002su48Cgy6HOHL5JLPb1&690

http://s2/mw690/002su48Cgy6HOHLjOhz01&690

3应用举例

       例：已知有长序列X=[1,2,3,4,5,6,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=floor(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);

end

Y=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:a

    xk=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);

end

Y=Y(1:Lx+M-1);