如何使用DFT实现卷积？

Question

因此，根据我的理解，可以通过离散傅里叶变换进行卷积。从我所读到的过程中，简单地涉及到对内核和输入的DFT进行修改。然而，我无法理解如何实现光谱的实际乘法，因为两个不同大小的阵列的DFT是不同的。

所以在psuedocode中，假设我有一个长度为1024的数组arr和长度为8的内核kern。

为了得到arr和kern的卷积，我执行：

IDFT(DFT(arr)*DFT(kern))

然而，DFT(arr)是一个长度为1024的数组，而DFT(kern)是一个长度为8的数组。那么它们是如何乘以的呢？

Answer 1

要与DFT进行卷积，DFT的大小必须至少与卷积结果一样大--您的内核大小加上输入大小。你把它们都调到这个尺寸，然后对IDFT和IDFT使用相同的大小。

请注意，如果您的内核比输入小得多，这是完全没有效率的。在这种情况下(通常)，您可以使用重叠-添加或重叠-保存方法将输入分成与内核大小大致相同的块。

参见，例如：https://www.youtube.com/watch?v=FPzZj30hPY4

对于非常小的内核来说，这仍然是不有效的。如果您的内核实际上只有8个样本，那么您就不应该对这些东西感到烦恼了。简单的实现将更快。