两个fft函数的卷积

Question

对于卷积定理F(x.y) = F(x)*F(y)

但是在 python

上实施后

x = np.array([0,0,0,0,1, 2, 3, 4, 0 ,0,0,0])
y = np.array([0,0,0,0,-3, 5, -4, 0, 0, 0,0,0])

xy = x*y
inverse_fft_xy = np.fft.ifft(np.convolve(np.fft.fft(x),np.fft.fft(y)))

会产生

xy

array([  0,   0,   0,   0,  -3,  10, -12,   0,   0,   0,   0,   0])

inverse_fft_xy

array([  0.00000000e+00,  -8.70383905e-01,   1.65925305e-02,
    -8.90888514e-01,   7.07822398e-02,  -8.80447879e-01,
     1.19687210e-01,   3.09247006e+00,  -9.54481834e+00,
    -5.81203213e+00,   2.15726342e+01,  -1.47366137e+01,
    -1.03012447e+01,   2.76823117e+00,  -1.42560168e+00,
     4.98000293e-01,  -1.18537317e+00,   2.02675981e-01,
    -9.98770784e-01,   7.43392335e-02,  -9.11516399e-01,
     1.67799168e-02,  -8.74501632e-01])

matlab也一样

我知道应该补零以避免线性卷积。此外，定理 F(x*y) = F(x).F(y) 的另一种方式可以完成。我只是想知道为什么不能这样做。

Answer 1

时域乘法实际上是在频域中循环卷积，如wikipedia:

按照@Ami tavory's 计算循环卷积，您可以使用以下方法实现：

Xf = np.fft.fft(x)
Yf = np.fft.fft(y)
N = Xf.size    # or Yf.size since they must have the same size
conv = np.convolve(Xf, np.concatenate((Yf,Yf)))
conv = conv[N:2*N]
inverse_fft_xy = np.fft.ifft(conv) / N

这样

x = np.array([1, 2, 3, 4])
y = np.array([-3, 5, -4, 0])

（除了使两个数组具有相同大小所需的零填充之外）将产生预期的结果：

xy

array([  -3,  10, -12,   0  ])

inverse_fft_xy

array([ -3.+0.j, 10.+0.j, -12.+0.j, 0.+0.j])

两个fft函数的卷积

Convolution of two fft function

python

numpy

fft