5
$\begingroup$

I'm a little confused... I always thought the DFT of a convolution was equal to a product of DFTs, but when I tried this in Python:

from scipy import *

a = [1+0j, 2+0j]
b = [4+0j, 5+0j]

print list(ifft(fft(a) * fft(b)))
print list(convolve(a, b))

I got back:

[(14+0j), (13+0j)]
[(4+0j), (13+0j), (10+0j)]

Why are they not the same thing?

Improve this question
$\endgroup$
5
  • $\begingroup$ You could just use fftconvolve $\endgroup$
    – endolith
    Commented Sep 24, 2012 at 16:35
  • $\begingroup$ @endolith: That returns the same thing as convolve. $\endgroup$
    – user541686
    Commented Sep 24, 2012 at 17:26
  • $\begingroup$ Isn't that what you want? You're trying to use FFTs to calculate the same output as convolve, which is exactly what fftconvolve does. $\endgroup$
    – endolith
    Commented Sep 24, 2012 at 17:28
  • $\begingroup$ possible duplicate of Efficiently calculating autocorrelation using FFTs $\endgroup$
    – endolith
    Commented Sep 24, 2012 at 17:29
  • $\begingroup$ @endolith: I'm not asking how to calculate anything; did you read the question? $\endgroup$
    – user541686
    Commented Sep 25, 2012 at 8:14

1 Answer 1

Reset to default
16
$\begingroup$

ifft(fft(a) * fft(b)) performs a cyclic convolution, convolve apparently zero-pads the inputs. If you pad both arrays with zeros, the result should be the same:

a = [0,0,0,1+0j, 2+0j,0,0,0]
b = [0,0,0,4+0j, 5+0j,0,0,0]

print list(ifft(fft(a) * fft(b)))
print list(convolve(a, b))
Improve this answer
$\endgroup$
1
  • $\begingroup$ numpy.core.numeric.convolve uses numpy.core.numeric.multiarray.correlate (correlation via shifted dot products) with the 2nd array time reversed. It doesn't use the FFT, so it preserves the array type according to the highest priority of the two arrays, as long as the type has a dot function defined. $\endgroup$
    – Eryk Sun
    Commented Sep 27, 2012 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.