分段卷积

发表于   |   分类于   |  

概念

在长序列与短序列进行卷积时(特别是输入序列变长或无限长)， 常采用分段卷积的方法处理。即将长序列分段为多个子段，对每个子段分别计算线性卷积后，再将每段计算输出按照一定的关系组合在一起，即可得到与原序列计算卷积相同的结果。

这样可降低运算量并提高实时性，特别是对子段的计算采用FFT方法，进一步提高速度。
开始提到分段卷积应用于两序列的长度相差较大时，而对于何时用分段卷积何时用FFT计算，维基上有详细比较的示例。

而分段卷积根据方式不同，有重叠相加法和重叠保留法两种，我在一篇文章中看到过介绍说，两种方法的计算效率相同，所以要实际应用时分情况选择。

重叠相加法

假设x[n]长度为N，h[n]长度为M，则x[n]*h[n]长度为N+M-1。
将x[n]分为k个子段，每个子段长度为L，即$x_k[n]=x[n]$，其中$kL \leq n \leq (k+1)L-1$，即每个子段相互之间无重叠。

计算$y_k[n] = x_k[n] * h[n]$$后，对各$y_k[n]$重叠相加后即可得到y[n]。而重叠相加的关系如下：$y_k[n]$长度为L+M-1，其中$yk[n]$的后M-1个点与紧邻下一子段$y{k+1}[n]$的前M+1个点相互重叠，因此每次计算出一个$yk[n]$后，与$y{k-1}[n]$按刚才的关系叠加后，可得到前L个点为最终实际输出，而后M-1个点还需用于下一次计算。
可知每次子段计算有效输入输出L点。

刚才的关系按照冲击响应法去画图很容易理解，并且注意，每个子段卷积计算结果为L+M-1点，即可用L+M-1点FFT对应的循环卷积得到线性卷积结果。

重叠保留法

假设x[n]长度为N，h[n]长度为M，则x[n]*h[n]长度为N+M-1。
将x[n]按重叠分段分成k个子段，每个子段的前M-1点与上一子段的后M-1点相同，即$x_k[n] = x[n+k(L-M+1)]$，其中$0 \leq n \leq L-1$。

需要注意必须满足子段的长度$M \leq L$，并且$x_k[n]$与h[n]采用的是L点循环卷积。这样循环卷积的结果$y_k[n]$为L点，而原线性卷积的长度为L+M-1，分析可知$y_k[n]$前M-1点是混叠的应该舍去，而后L-M+1点无混叠为实际输出。

因此每次做L点循环卷积后，取后L-M+1点作为实际输出，即每次子段计算有效输入输出L+M-1点。

实际运算时常采用50%重叠，即取L=2M做L点循环卷积(用FFT实现)。并且对序列开头补0以得到线性卷积输出。

思考

上述方法目的都是为了减少计算量，而我在实际运用时遇到的场景是，输入序列不定长，需要分段，而h[n]不定长的同时长度很常，一次性长序列的FFT计算带来的延迟过大，因此我也想对h[n]分段。
这个时候就需要将输入x[n]分割为长度小于h[n]的子段，再在$x_k[n]$子段计算时将h[n]分子段计算。

重叠保留法要求子段长度满足$M \leq L$，因此对x[n]分段时不可取，我验证了下重叠相加法，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x = randi(10,1,1024);
h = randi(10,1,2048);
L=length(x);
M=length(h);
k = 4;          %分段数量
Nseg= L/k;      %每段长度
x = [x, zeros(1,k*Nseg-L)];
y = zeros(1, L+M-1);
for i=0:1:k-1
    ix = i*Nseg;
    xseg = x(ix+1 : ix+Nseg);
    yseg = cconv(xseg, h, Nseg+M-1);    %DFT对应的循环卷积实现线性卷积
%     yseg = conv(xseg, h);
    y(ix+1:ix+Nseg+M-1)=y(ix+1:ix+Nseg+M-1)+yseg(1:Nseg+M-1);
end
yori = conv(x,h);   %原线性卷积序列

比较y和yori结果相同，也就是说重叠相加法对子段长度L和卷积序列长度M之间的关系大小要求。

因此可采取的方法举例，将输入序列按照重叠相加分段为512点子段，子段与4096点h[n]做线性卷积后的输出结果按照重叠关系相加后得到实际输出序列。
而h[n]按照重叠保留法（也可重叠相加法）分为1024点子段，做1024点循环卷积，取后512点为线性卷积结果。
这样FFT计算单位定为了1024点，当然这样是以资源换取速度的策略。而且各子段结果之间的衔接也是很重要的一点。