利用 DFT 计算线性卷积

1、线性卷积原理

线性卷积如下：

一个离散序列通过一个离散的线性时不变系统，它的输出就是上面这样一个表达式。也就是说在时域，输出信号等于输入信号和系统的单位脉冲响应 h[K] 的卷积。

2、DFT 计算线性卷积原理

利用 DFT 的循环卷积特性，可由 DFT 计算线性卷积：

3、乘法运算次数比较

第一种情况：

第二种情况

从上面两种情况可以看出：当两个序列长度相当的时候，我们通过循环卷积和DFT计算的时候效率会提高；而一个长序列和短序列线性卷积的时候，我们通过循环卷积和DFT计算效率反而会降低，或者提高有限。

4、示例

利用DFT计算线性卷积：

上面主要介绍了如何使用循环卷积计算线性卷积，循环卷积可以通过DFT来实现，DFT又存在相应的快速算法FFT。从原理上解释了利用 DFT 可以快速提高线性卷积效率，当然，这个也需要一定的前提和方法。

5、长序列与短序列的线性卷积

直接利用DFT计算长序列与短序列的卷积，存在缺点：

（1）信号要全部输入后才能进行计算，延迟太多；
（2）内存要求较大；
（3）算法效率不高。

解决办法：

采用分段卷积：

（1）重叠相加法

（2） 重叠保留法

具体实现方法参照博客：https://blog.csdn.net/u010592995/article/details/77882183