循环卷积与线性卷积

循环卷积

针对的是两个长度都为N的序列，对两个序列做FFT，然后再做IFFT得到的结果就是循环卷积，结果的长度也是N。

直接计算步骤：

序列A与序列B，长度都是N，新的序列C

1、把B倒过来。[翻转]

2、把B向右平移一个元素。最右侧的元素补到左边。

3、计算此时A和B对应元素的积的和。将其加到C的末尾。

4、如果C中还不足N个元素，重复步骤2和3。

线性卷积

针对的是两个长度为L和M的序列，将两个序列都补0pad到N，做FFT，再做IFFT。得到的结果长度为L+M-1

直接计算步骤：

序列A与序列B，长度分别数L和M，都补0到N，新的序列C

1、把B倒过来。[翻转]

2、将B翻转之后的数组第一位与A的第一位对齐

3、计算此时A和B对应元素的积的和。

4、将B数组向右移动一位，继续计算。

5、直到B数组与A数组没有重叠为止。

两者的关系：

如果想要计算循环卷积，可以将线性卷积进行周期化，然后计算。

如果想要计算线性卷积，可以将循环卷积pad0，进行计算。