如果您提前知道您的滤波器脉冲响应交替为零，那么您可以使用不同的FFT 例程来加速卷积。另一方面，如果您只是将滤波器输入和脉冲响应传递给一个通用计算子程序，该子程序将在给定和的情况下吐出滤波器输出，那么是的，零的处理方式与任何其他输入，根本不会节省任何计算。$x[n]$$h[n]$

示例：
假设 (FIR) 滤波器脉冲响应为。那么滤波器的输出为$\mathbf h = 1 \quad 0 \quad 1 \quad 0 \quad 1$

$$y[n] = x[n] + x[n-2] + x[n-4]$$

因此，滤波器输出交替地 是三个连续的偶数输入的总和和三个连续的奇数输入的总和。因此，知道 \有交替的零，我们可以进行如下操作。$\mathbf h$

1. 创建一个过滤器通过抽取 （或下采样）因子。因此，。$\hat{\mathbf h}$$\mathbf h$$2$$\hat{\mathbf h} = 1 \quad 1 \quad 1$
2. 抽取以创建两个输入流 $\mathbf x$ $$\mathbf x_e = x[0]\quad x[2]\quad x[4] \quad \cdots ~~\text{and}~~ x_o = x[1]\quad x[3]\quad x[5] \quad \cdots$$
3. 将应用于两个流以得到和。$\hat{\mathbf h}$$\mathbf y_e$$\mathbf y_o$
4. 重组和得到。$\mathbf y_e$$\mathbf y_o$$\mathbf y$

如果在进行所需卷积的任何地方都使用 FFT，请注意的 FFT只需计算一次，并且必须将重叠和相加等各种技巧分别应用于两者数据流。还要注意 FFT 可以更短（尽管我们必须做其中两个），粗略的比较表明 与实际数字进行更精确的比较可能会发现不同的权衡。$\hat{\mathbf h}$

$$2\left[\frac{N}{2}\log_2\left(\frac{N}{2}\right)\right] = N\log_2\left(\frac{N}{2}\right) < N\log_2 N.$$

这是一个正确的评估吗？如果是这样，那么是否存在时域中良好的老式卷积实际上比 FFT 快得多的情况？

你是对的。N 小的时域卷积总是比 FFT 卷积快。我为英特尔 IPP 库研究了这个问题。我以 3 模式运行卷积计算：

• auto - 自动选择最优算法。
• 直接- 使用直接算法
• FFT - 使用基于 FFT 的算法实现。

在“自动”模式下，IPP 对小 N 使用时域卷积，对大 N 使用 FFT 卷积。在下表中：N - 滤波器大小，M - 数据数组大小。数据类型为 float32。处理器 - 英特尔 i5-2500。

+------+------+------+--------+------+  
|   M  |   N  |         time         |   
|      |      | auto | direct |  FFT |  
|------+------+------+--------+------|  
| 1024 |  15  |  6.2 |   6.2  |  8.4 |  
| 1024 |  65  |  9.9 |  10.2  | 10.2 |  
| 1024 | 319  | 24.5 |  28.8  | 25.1 |  
| 8192 |  15  | 48.4 |  48.1  | 62.0 |  
| 8192 |  65  | 60.5 |  77.8  | 60.8 |  
| 8192 | 319  | 82.2 | 257.   | 82.8 |  
+------+------+------+--------+------+  

因此，如果 N 很小，则使用时域计算。如果您的过滤器具有一些可以在时域中使用的附加属性（对称性、大量零点等），您可以获得额外的提升。

编辑

我写了上面的实验数据。有一个简单而众所周知的理论解释。时域卷积的操作数为 O (M * N)。FFT 卷积的操作数为 O ((M + N) * log (M + N))。很容易检查 FFT 卷积仅对足够大的 M, N 更好。对于 IPP 库，此边界位于 N ~ 50 for M=1024

编辑 2

为时域卷积添加时序

如果是这样，那么是否存在时域中良好的老式卷积实际上比 FFT快得多的情况？

是的。当 N 较小时，直接卷积总是更快。

如果您可以将半个零的计算时间减半，那么这会改变 N 变为“小”的点，但无论有多少个零，FFT 方法对于“大 N”总是更快，而对于“小 N”则更慢您可以采取其他捷径，因为 FFT 需要 O(N log N)（实际上是 8N log 2N？）时间，而直接卷积需要 O(N ² ) 时间（实际上是 2N ²时间，或者在您的情况下为 N ²时间？）。

这是操作数与 N 的关系图。这些数字是任意的，但它们可以正确缩放：

所以在 N = 40 时，FFT 卷积比直接卷积快，但由于零点而时间减半的直接卷积比 FFT 快。但是，在某个 N 处，FFT 总是获胜。

似乎我会撤销我本可以拥有的任何收益

听起来您认为 FFT 将计算时间减半。它没有。它比减半要好得多。举个粗略的例子，在 N = 10000 时，你的需要大约 100,000,000 次操作，而原来的需要 200,000,000 次操作，节省了一半的时间。同时，FFT 需要大约 344,082 次操作，数量级要少。

在某个 N 处，FFT 总是会变得更快，但肯定有直接更快的情况。