区块折积

区块折积，又称区块卷积、分段折积、分段卷积、分块卷积等，是一种计算线性离散卷积的方法，在信号处理以及线性非时变系统领域的应用层面上有相当高的价值。

区块卷积主要常使用于计算一固定离散信号与另一非固定离散讯号间的线性卷积，且非固定讯号的长度通常较固定方长上许多，一个很具体的例子就是计算一讯号经有限长度滤波器后的输出。 其主要具有两个优点，第一，其计算复杂度较低，在输入讯号长度为 $N$时，区块卷积的计算复杂度为$\mathrm {O} (N)\!$，而直接对整段输入讯号进行卷积计算的复杂度为$\mathrm {O} (N\log N)\!$。 第二，当我们要以硬件进行实作时，区块卷积仅需要单一固定的硬件架构，即可处理不同长度（甚至是无穷长）的输入，可以像工厂的流水生产线一般连续的接受输入并同时连续的吐出结果， 而如果要直接对整段输入讯号进行卷积，则需要对不同的输入长度设计不同的硬件运算架构，在应用上是不切实际并且没有必要的。

目前对于区块卷积，主流使用的英文专有词汇为sectioned convolution，但在一些中文圈作者所撰写的文章中，也可能会采用取“块”字翻英后的block convolution。

计算

区块卷积的计算核心概念，便是将较长的讯号进行分段，将原先的求卷积问题分解为规模较小的问题，再将结果进行整合，以得到原先问题的结果。

但根据将讯号分段以及将结果整合的方式，可以再将区块卷积细分为两个类别，可见下文说明。

卷积的性质观察

首先，在对区块卷积的计算法进行细分之前，我们需要先了解一些关于卷积的性质，以及关于切分后子问题的结果与母问题结果的关联。

假设有一长度为$N$的离散讯号（通常很长）：

$x[n](n=0,1,\dots ,(N-1))$

与一长度为$M$的离散讯号（通常很短）：

$h[n](n=0,1,\dots ,(M-1))$

将两者进行卷积后的结果$y[n]=x[n]*h[n]$，我们可以知道其长度应该为$(N+M-1)$：

$y[n](n=0,1,\dots ,(N+M-2))$

根据卷积的定义，我们可以知道其中$y$的第$n'$点输出$y[n']$， 会受到相对应位置的$x[n']$，以及其向前$(M-1)$点的影响：

$y[n']=\sum _{m=0}^{M-1}x[n'-m]h[m]=x[n'-(M-1)]h[M-1]+x[n'-(M-2)]h[M-2]+\dots +x[n']h[0]$

这时如果我们将$x[n]$切出长度为$L$的小段，并假设起始位置为$n_{0}$：

$x_{L}[n]=x[n](n=n_{0},n_{0}+1,\dots ,n_{0}+(L-1))$

我们可以发现，其与$h[n]$进行卷积后的结果$y_{L}[n]=x_{L}[n]*h[n]$，和原先母问题在对应区段的结果$y[n]$存在差异， 具体来说，$y_{L}[n]$的前段部分少考量了$x[n]$中$n<n_{0}$部分的影响，例如在$y_{L}[n]$第一点$y_{L}[n_{0}]$ 就仅考量一项$x$的影响，和$y[n_{0}]$相差许多：

$y_{L}[n_{0}]=x[n_{0}]h[0]\neq y[n_{0}]=x[n_{0}-(M-1)]h[M-1]+\dots +x[n_{0}]h[0]$

同理，在$y_{L}$的后段部分也会有类似的问题，少考量了$x$在段落之后的影响，而只有计算到部分残留影响的结果。 只有在$y_{L}$的中段部分，会与母问题结果$y$完全相同。 而要如何处理这个差异，并透过多段的$y_{L}$还原出$y$，便是以下两种方法的最主要区别。

重叠-储存之折积法

重叠-储存算法，便是舍弃子结果$y_{L}$的前后段，只取中段与母结果$y$相同的部分并进行拼接的算法。

具体来说，重叠-储存算法切分问题的主要考量为母结果$y$， 在实作这个算法的时候必须先决定将母结果$y$切分的长度。

假设决定将母结果切分为长度$L_{y}$的区间， 根据前面的讨论，我们可以得知：

1.$x_{L}$的长度需要为$(L_{y}+(M-1))$才能够确保$L_{y}$长度的有效区段

2.在每次长度为$(L_{y}+2(M-1))$的计算结果$y_{L}$中，需要舍去前后各$(M-1)$长度的部分

3.在第一个区段，因为$x[n]$在$n<0$的区域是没有资讯的，所以$x_{L0}$的长度只需要$L_{y}$即可

综合以上三点，我们可以写出所需要的切分区段描述：

$x_{L0}[n]=x[n](n\in 0\sim (L_{y}-1))$

$x_{Lk}[n]=x[n](n\in (kL_{y}-(M-1))\sim ((k+1)L_{y}-1),k\in 1\sim (\left\lceil {\frac {M+N-1}{L_{y}}}\right\rceil -1))$

以及结果的描述：

$y[n]=y_{Lk}[n](n\in kL_{y}\sim ((k+1)L_{y}-1),k\in 0\sim (\left\lceil {\frac {M+N-1}{L_{y}}}\right\rceil -1))$

而重叠-储存算法便是得名于其在输入区段的切分上会有重叠的部分，须将前一个子问题的输入后半先行储存再作为下一个子问题的输入前半。

这个算法的好处在于不需要额外的加法，并且如果在子问题求解时是采取直接计算卷积的方式，可以不用在讯号后面补零。

但缺点为同样的分段数量下，每个子问题会需要处理较长的讯号，子问题计算量可能会较大一些。

重叠-相加之折积法

重叠-相加算法，则是将子结果$y_{L}$的后段， 与下一段子结果$y_{L}$的前段， 像拼图一样根据对应的编号进行相加， 重建出完整母结果$y$的算法。

具体来说，重叠-储存算法切分问题的主要考量为输入$x$， 在实作这个算法的时候必须先决定将输入$x$切分的长度。

假设决定将输入切分为长度$L$的区间， 我们可以直接写出所需要的切分区段描述：

$x_{Lk}[n]=x[n](n\in kL\sim ((k+1)L-1),k\in 0\sim (\left\lceil {\frac {N}{L}}\right\rceil -1))$

以及结果的描述：

$y[n]=x[n]*h[n]=\sum _{k=0}^{(\left\lceil {\frac {N}{L}}\right\rceil -1)}x_{Lk}[n]*h[n]=\sum _{k=0}^{(\left\lceil {\frac {N}{L}}\right\rceil -1)}y_{Lk}[n]$

这个算法特别需要注意的便是，重建出的母结果$y$牵涉到子结果对应项目的相加，要正确地对上才会是正确的结果，例如$y[L+1]$就会是两个子结果的相加： $y[L+1]=\underbrace {x[(L+1)-(M-1)]h[M+1]+\dots +x[(L+1)-2]h[2]} _{y_{L}0[L+1]}+\underbrace {x[(L+1)-1]h[1]+x[(L+1)-0]h[0]} _{y_{L}1[L+1]}$

而重叠-相加算法便是得名于其在输出的子结果上会有项目编号重叠的部分，须将其进行相加才能得到母结果。

这个算法的好处在于切分的方式相当直觉，而且在同样的分段数量下，每个子问题需要处理的讯号长度较短，子问题计算量较小。

但缺点为可能需要一些额外的加法，而且就算采取直接计算卷积的方式来计算子问题，也仍需要补零在讯号后方。

复杂度与比较

虽然区块卷积具有两种差异不小的算法，但总体来说，对于每个固定架构的子问题，所需要的计算量都是常数， 而子问题的数量则正比于输入讯号长度$N$，所以计算复杂度对两个算法来说都是$\mathrm {O} (N)\!$， 相较于使用快速傅里叶变换技巧进行整个问题的计算复杂度$\mathrm {O} (N\log N)\!$要来的低。

所以一般来说在$N$很大时，显然的使用区块卷积会较处理整个问题来的有效率。

不过，有时候输入讯号$x$并不具有足够的长度可以保证区块卷积较有效率， 又或者在一些极端情况下，直接按定义进行计算卷积可能会更有效率， 所以接着便是要稍微谈论一下不同主流计算卷积方法的计算量， 以及如何根据输入讯号长度$N$与固定讯号长度$M$间的关系选择算法。

直接计算卷积

如果是根据卷积的定义，直接以乘法及加法计算卷积的话， 我们可以知道，每一个$x[n]$都需要轮流和每一个$h[n]$进行相乘， 所以总共需要的乘法数量为

$N\times M$

又因为讯号可能是复数，所以上述的乘法为复数乘法，将其统一以时数乘法进行实作后可以得到需要的实数乘法数为

$3N\times M$

可以发现，其实直接计算卷积对于输入长度$N$来说，其复杂度也是$\mathrm {O} (N)\!$， 但其常数为$3M$，当$M$增大时，运算量会增加很快，运算效率会不及区块卷积， 但相对的当$M$落在很小的值时，直接计算卷积可能会是较高效率的计算方法。

使用快速傅立叶变换技巧计算卷积

除了直接计算卷积之外，另外一种主流的卷积计算方法，便是透过卷积定理， 将卷积的计算化为两次傅立叶变换相乘后再进行反傅立叶变换的问题， 实作如下：

$y[n]=x[n]*h[n]=IFFT_{P}(FFT_{P}(x[n])\times FFT_{P}(h[n]))$

其中$FFT_{P}$为$P$点快速傅立叶变换， $IFFT_{P}$为逆变换（形式与快速傅立叶变换相同），$P$根据圆周卷积定理必须大于$(M+N-1)$， 而$x[n]$及$h[n]$需透过补零来补齐长度。

如果采用这个方法，并且假设$h[n]$为固定不变，可以将$FFT_{P}(h[n])$计算一次后储存备用， 那可以得到所需乘法数为：

$2MUL_{P}+3P$

其中$MUL_{P}$为$P$点快速傅立叶变换所需的乘法数， 估计为${\frac {3}{2}}P\log _{2}P$， 乘两倍是因为需计算$FFT_{P}(x[n])$与最后的逆变换， $3P$则是因为$FFT_{P}(x[n])\times FFT_{P}(h[n])$含有$P$个复数的乘法，统一转换为实数乘法则是$3P$。

将$P=(M+N-1)\approx (M+N)$与$MUL_{P}$的估计值带入上面的所需乘法数进行估计，可以得到所需乘法数为：

$3(M+N)(\log _{2}(M+N)+1)\approx 3(M+N)\log _{2}(M+N)$

可以发现，使用快速傅立叶变换技巧计算卷积对于输入长度$N$来说，其复杂度是$\mathrm {O} (N\log N)\!$， 但当$M$大约与$N$落在接近的数量级时，运算量会较其他方法低上许多。

使用区块卷积搭配快速傅立叶算法计算卷积

最后，另外一种主流的卷积计算法便是先利用区块卷积将问题拆分，再将拆分后的问题透过快速傅立叶算法来处理， 而之所以通常不是搭配直接计算的方式， 是因为我们通常会假设拆分过后的问题中，要进行卷积的两讯号长度会差不多长， 而根据前面的讨论，我们已经知道使用快速傅立叶转换来进行计算会有效率的多。

而使用区块卷积搭配快速傅立叶算法计算卷积的复杂度， 和前面两种方法的计算复杂度只与$M,N$有关不同， 分段所使用的段落长度$L$也会很大程度的影响这个方法的计算量。

以重叠-相加算法作为代表， 假设采用的分段长度为$L$， 可以得到分段的段数$S$为：

$S=\left\lceil {\frac {N}{L}}\right\rceil \approx {\frac {N}{L}}$

而每个子问题的实际计算量根据上面可得：

$2MUL_{P}+3P$

乘上需要解的子问题数可得实际总计算量：

$2S\times MUL_{P}+3S\times P$

同样根据上面可再进一步估计得：

${\frac {N}{L}}3(M+L-1)(\log _{2}(M+L-1)+1)\approx {\frac {N}{L}}3(M+L)\log _{2}(M+L)$

可以发现这个计算法的复杂度为$\mathrm {O} (N)\!$， 并且常数约为${\frac {3(M+L)}{L}}\log _{2}(M+L)$， 在$M$的数值略大时会较采取直接计算会较有效率， 但在$M$与$N$的数量级接近时， 因为$M$的大小被迫推升， 导致比起直接对整段讯号进行快速傅立叶算法的表现还要差。

所以根据上述可以估计这个方法可以展现优势的区段， 大概是界在前面两种方法的$M,N$比例之间。

而在实际应用时，因为快速傅立叶转换的计算量在局部会有不小的波动，并不如理论值估计那般平滑，所以为了得到较好的计算效率， 除了须将上面的计算量视作$L$的函数，透过数值绘图的方法或微分，求得在理论估计上最适合的$L$值之外， 还需在求得的最适合子问题大小附近进行找寻， 挑选数个可能的合适子问题傅立叶转换大小， 再将反求得的分段长度带回计算运算量， 以求得真正的最佳分段长度$L$。

例如：在

$N=2000,M=17$

的情况下，求得的理论最适合分段长度为

$L_{0}=85$

理论最适合子问题傅立叶转换大小为

$P_{0}=L_{0}+M-1=101$点

但在$72$点傅立叶转换的计算量有一个明显的低谷，将由此逆推得到的可能分段长度

$L=72-M+1=56$

与其他可能值都带回去计算实际计算量后，可以确认$56$才是最佳的问题分段长度。

最后，同样是基于快速傅立叶转换的计算量在局部的波动，在极为特殊的情况下，如果$M\leq 4$， 我们便有可能使子问题仅需使用$4$点傅立叶转换，而在这样的情况下虽会使用大量的加法， 但可不必在傅立叶转换上使用任何乘法，可能会较直接计算卷积有效率。

参考资料

Jian-Jiun Ding, advanced digital signal processing lecture note （页面存档备份，存于互联网档案馆）, the Department of Electrical Engineering, National Taiwan University （NTU）, Taipei, Taiwan, 2022.

外部链接

重叠-储存之折积法

重叠-相加之折积法