为什么我的卷积结果在使用 FFT 时发生偏移

Question

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

我的解决方案是将输入大小和内核大小都零填充到 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  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 列），但我可能是错的。我使用 this link 的在线计算器执行了相同的计算！并得到相同的结果，所以可能是我缺少一些基础知识。我可用的文献没有帮助。所以我的问题是，为什么会这样？

Answer 1

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

Answer 2

所以我最终找到了答案为什么这会发生在我自己身上。答案是通过卷积的定义和在那里发生的索引给出的。所以根据定义 s 和 k 的卷积由

给出

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

内核的中心是不是"known"这个公式，所以我们做一个抽象。定义c作为卷积的中心。当x-k = c求和时，s(k)就是s(x-c)。因此，包含有趣乘积 s(x-c)k(c) 的总和最终位于索引 x。换句话说，向右移动 c.

为什么我的卷积结果在使用 FFT 时发生偏移

Why is my convolution result shifted when using FFT

signal-processing

fft

shift

convolution