为什么使用 FFT 时我的卷积结果会发生变化

Question

我正在使用 Radix-2 Cooley-Tukey FFT/FFT-逆实现卷积，我的输出是正确的，但在完成后发生了偏移。

我的解决方案是将输入大小和内核大小归零填充为 2^m，以获得尽可能小的 m，使用 FFT 转换输入和内核，然后将两者逐个元素相乘并使用 FFT 逆转换结果。

作为由此产生的问题的示例：

 0  1  2  3  0  0  0  0
 4  5  6  7  0  0  0  0
 8  9 10 11  0  0  0  0
12 13 14 15  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

使用身份内核

0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

成为

 0  0  0  0  0  0  0  0
 0  0  1  2  3  0  0  0
 0  4  5  6  7  0  0  0
 0  8  9 10 11  0  0  0
 0 12 13 14 15  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

似乎任何大小的输入和内核都会产生相同的偏移（1 行和 1 列），但我可能是错的。我使用此链接中的在线计算器执行了相同的计算！并获得相同的结果，所以可能是我缺少一些基础知识。我可用的垃圾没有帮助。所以我的问题，为什么会这样？

Answer 1

所以我最终找到了为什么会发生这种情况的答案。答案是通过卷积的定义和那里发生的索引给出的。所以根据定义，s和k的卷积由下式给出

(s*k)(x) = sum(s(k)k(x-k),k=-inf,inf)

内核的中心不是这个公式"已知的"，因此我们做了一个抽象。将 c 定义为卷积的中心。当 x-k = c 在总和中时，s（k） 是 s（x-c）。因此，包含相关乘积 s（x-c）k（c） 的总和最终位于索引 x。换句话说，向右移动了 c。

Answer 2

FFT快速卷积进行循环卷积。 如果将零点填充，以便数据和内核在相同大小的 NxN 数组中以 （0，0） 为中心，则结果也将保持居中。 否则，将添加任何偏移量。