对于定义在整数 上的函数 ,卷积定义为
-
-
这里一样把函数定义域以外的值当成零,所以可以扩展函数到所有整数上(如果本来不是的话)。
当 的支撑集(support)为有限长度 ,上式会变成有限和:
-
计算离散卷积的方法
计算卷积 有三种主要的方法,分别为
- 直接计算(Direct Method)
- 快速傅里叶变换(FFT)
- 分段卷积(sectioned convolution)
方法1是直接利用定义来计算卷积,而方法2和3都是用到了FFT来快速计算卷积。也有不需要用到FFT的作法,如使用数论变换。
方法1:直接计算
-
- 若 和 皆为实数信号,则需要 个乘法。
- 若 和 皆为更一般性的复数信号,不使用复数乘法的快速算法,会需要 个乘法;但若使用复数乘法的快速算法,则可简化至 个乘法。
- 因此,使用定义直接计算卷积的复杂度为 。
方法2:快速傅里叶变换(FFT)
- 概念:由于两个离散信号在时域(time domain)做卷积相当于这两个信号的离散傅里叶变换在频域(frequency domain)做相乘:
-
- ,可以看出在频域的计算较简单。
-
- ,于是
-
- ,最后再将频域信号转回时域,就完成了卷积的计算:
-
- 总共做了2次DFT和1次IDFT。
- 特别注意DFT和IDFT的点数 要满足 。
- 由于DFT有快速算法FFT,所以运算量为
- 假设 点DFT的乘法量为 , 和 为一般性的复数信号,并使用复数乘法的快速算法,则共需要 个乘法。
方法3:分段卷积(sectioned convolution)
- 概念:将 切成好几段,每一段分别和 做卷积后,再将结果相加。
- 作法:先将 切成每段长度为 的区段( ),假设共切成S段:
-
- Section 1:
- Section 2:
-
- Section r:
-
- Section S:
- , 为各个section的和
- 。
- 因此,
- ,
- 每一小段作卷积则是采用方法2,先将时域信号转到频域相乘,再转回时域:
- 。
- 总共只需要做 点FFT 次,因为 只需要做一次FFT。
- 假设 点DFT的乘法量为 , 和 为一般性的复数信号,并使用复数乘法的快速算法,则共需要 个乘法。
- 运算量:
- 运算复杂度: ,和 呈线性,较方法2小。
- 分为 Overlap-Add 和 Overlap-Save 两种方法。
分段卷积: Overlap-Add
欲做 的分段卷积分, 长度为 , 长度为 ,
Step 1: 将 每 分成一段
Step 2: 再每段 点后面添加 个零,变成长度
Step 3: 把 添加 个零,变成长度 的
Step 4: 把每个 的小段和 做快速卷积,也就是 ,每小段会得到长度 的时域信号
Step 5: 放置第 个小段的起点在位置 上,
Step 6: 会发现在每一段的后面 点有重叠,将所有点都相加起来,顾名思义 Overlap-Add,最后得到结果
举例来说:
, 长度
, 长度
令
令 切成三段,分别为 , 每段填 个零,并将 填零至长度
将每一段做
若将每小段摆在一起,可以注意到第一段的范围是 ,第二段的范围是 ,第三段的范围是 ,三段的范围是有重叠的
最后将三小段加在一起,并将结果和未分段的卷积做比较,上图是分段的结果,下图是没有分段并利用快速卷积所算出的结果,验证两者运算结果相同。
分段卷积: Overlap-Save
欲做 的分段卷积分, 长度为 , 长度为 ,
Step 1: 将 前面填 个零
Step 2: 第一段 , 从新的 中 取到 总共 点当做一段,因此每小段会重复取到前一小段的 点,取到新的一段全为零为止
Step 3: 把 添加 个零,变成长度 的
Step 4: 把每个 的小段和 做快速卷积,也就是 ,每小段会得到长度 的时域信号
Step 5: 对于每个 小段,只会保留末端的 点,因此得名 Overlap-Save
Step 6: 将所有保留的点合再一起,得到最后结果
举例来说:
, 长度
, 长度
令
将 前面填 个零以后,按照 Step 2 的方式分段,可以看到每一段都重复上一段的 点
再将每一段做 以后可以得到
保留每一段末端的 点,摆在一起以后,可以注意到第一段的范围是 ,第二段的范围是 ,第三段的范围是 ,第四段的范围是 ,四段的范围是没有重叠的
将结果和未分段的卷积做比较,下图是分段的结果,上图是没有分段并利用快速卷积所算出的结果,验证两者运算结果相同。
至于为什么要把前面 丢掉?
以下以一例子来阐述:
, 长度 ,
, 长度 ,
第一条蓝线代表 轴,而两条蓝线之间代表长度 ,是在做快速卷积时的周期
当在做快速卷积时 ,是把信号视为周期 ,在时域上为循环卷积分,
而在一开始前 点所得到的值,是 和 内积的值,
然而 这 个值应该要为零,以往在做快速卷积时长度为 时不会遇到这些问题,
而今天因为在做快速卷积时长度为 才会把这 点算进来,因此我们要丢弃这 点内积的结果
为了要丢弃这 点内积的结果,位移 点,并把位移以后内积合的值才算有效。
应用时机
以上三种方法皆可用来计算卷积,其差别在于所需总体乘法量不同。基于运算量以及效率的考量,在计算卷积时,通常会选择所需总体乘法量较少的方法。
以下根据 和 的长度( )分成5类,并列出适合使用的方法:
- 为一非常小的整数 - 直接计算
- - 分段卷积
- - 快速傅里叶变换
- - 分段卷积
- 为一非常小的整数 - 直接计算
基本上,以上只是粗略的分类。在实际应用时,最好还是算出三种方法所需的总乘法量,再选择其中最有效率的方法来计算卷积。
例子
Q1:当 ,适合用哪种方法计算卷积?
Ans:
- 方法1:所需乘法量为
- 方法2: ,而2016点的DFT最少乘法数 ,所以总乘法量为
- 方法3:
- 若切成8块( ),则 。选 ,则总乘法量为 ,比方法1和2少了很多。
- 但是若要找到最少的乘法量,必须依照以下步骤
- (1)先找出 :解 :
- (2)由 算出点数在 附近的DFT所需最少的乘法量,选择DFT的点数
- (3)最后由 算出
- 因此,
- (1)由运算量对 的偏微分为0而求出
- (2) ,所以选择101点DFT附近点数乘法量最少的点数 或 。
- (3-1)当 ,总乘法量为 。
- (3-2)当 ,总乘法量为 。
- 由此可知,切成20块会有较好的效率,而所需总乘法量为21480。
- 因此,当 ,所需总乘法量:分段卷积<快速傅里叶变换<直接计算。故,此时选择使用分段卷积来计算卷积最适合。
Q2:当 ,适合用哪种方法计算卷积?
Ans:
- 方法1:所需乘法量为
- 方法2: ,选择1026点DFT附近点数乘法量最少的点数, 。
- 因此,所需乘法量为
- 方法3:
- (1)由运算量对 的偏微分为0而求出
- (2) ,所以选择7点DFT附近点数乘法量最少的点数 或 或 。
- (3-1)当 ,总乘法量为 。
- (3-2)当 ,总乘法量为 。
- (3-3)当 ,总乘法量为 。
- 由此可知,切成171块会有较好的效率,而所需总乘法量为5476。
- 因此,当 ,所需总乘法量:分段卷积<直接计算<快速傅里叶变换。故,此时选择使用分段卷积来计算卷积最适合。
- 虽然当 是个很小的正整数时,大致上适合使用直接计算。但实际上还是将3个方法所需的乘法量都算出来,才能知道用哪种方法可以达到最高的效率。
Q3:当 ,适合用哪种方法计算卷积?
Ans:
- 方法1:所需乘法量为
- 方法2: ,选择1026点DFT附近点数乘法量最少的点数, 。
- 因此,所需乘法量为
- 方法3:
- (1)由运算量对 的偏微分为0而求出
- (2) ,所以选择1623点DFT附近点数乘法量最少的点数 。
- (3)当 ,总乘法量为 。
- 由此可知,此时切成一段,就跟方法2一样,所需总乘法量为44232。
- 因此,当 ,所需总乘法量:快速傅里叶变换 = 分段卷积<直接计算。故,此时选择使用分段卷积来计算卷积最适合。