两个fft函数的卷积 [英] Convolution of two fft function

问题描述

对于卷积定理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)的另一种方法.我只想知道为什么不能用这种方式完成.

解决方案

时域乘法实际上是根据频域中的 circular 卷积进行的，如阿米·塔沃里(Ami tavory)的 解决方案

The time-domain multiplication is actually in terms of a circular convolution in the frequency domain, as given on wikipedia:

Following @Ami tavory's trick to compute the circular convolution, you could implement this using:

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

such that

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

(without any more zero padding than is necessary to have both arrays the same size) would yield the expected:

xy

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

inverse_fft_xy

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

这篇关于两个fft函数的卷积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！