利用 DFT 计算线性卷积
1、线性卷积原理
线性卷积如下：
一个离散序列通过一个离散的线性时不变系统，它的输出就是上面这样一个表达式。也就是说在时域，输出信号等于输入信号和系统的单位脉冲响应 h[K] 的卷积。
2、DFT 计算线性卷积原理
利用 DFT 的循环卷积特性，可由 DFT 计算线性卷积：
3、乘法运算次数比较
第一种情况：
第二种情况
从上面两种情况可以看出：当两个序列长度相当的时候，我们通过循环卷积和DFT计算的时候效率会提高；而一个长序列和短序列线性卷积的时候，我们通过循环卷积和DFT计算效率反而会降低，或者提高有限。
4、示例
利用DFT计算线性卷积：
上面主要介绍了如何使用循环卷积计算线性卷积，循环卷积可以通过DFT来实现，DFT又存在相应的快速算法FFT。从原理上解释了利用 DFT 可以快速提高线性卷积效率，当然，这个也需要一定的前提和方法。