1
$\begingroup$

To my understanding, multiplying a signal in the frequency-domain is equal to a convolution in the time-domain.

I wrote a small python program, but i always end up with a shift in the time domain. where does this come from? An hints how to get the correct convolution, where the convolved output signal is in place corresponding to the input signals?

import numpy as np
from matplotlib import pyplot as plt


# make simple rectangular signals
r1 = np.zeros(100, dtype=float)
r2 = np.zeros(100, dtype=float)
r1[1:20] = 1.
r2[20:40] = 1.

# fftransform the signals
fft_r1 = np.fft.rfft(r1)
fft_r2 = np.fft.rfft(r2)

# multiply the frequence-spectra of the signals
fft_p = np.multiply(fft_r1, fft_r2)
# ifftransform back to time-domain
conv = np.fft.irfft(fft_p)

f, axarr = plt.subplots(3, 3)
f.tight_layout()
axarr[0, 0].plot(r1)
axarr[0, 0].set_title("r1")
axarr[0, 1].plot(np.abs(fft_r1), '.')
axarr[0, 1].set_title("fft_r1")

axarr[1, 0].plot(r2)
axarr[1, 0].set_title("r2")
axarr[1, 1].plot(np.abs(fft_r2), '.')
axarr[1, 1].set_title("fft_r2")

axarr[2, 0].plot(np.abs(fft_p), '.')
axarr[2, 0].set_title("fft product")

axarr[2, 1].plot(conv)
axarr[2, 1].set_title("conv (ifft of fft_product)")
axarr[2, 2].plot(np.convolve(r1, r2, 'same'))
axarr[2, 2].set_title("conv, np")

Here is an image of the plots that the above code generates:

enter image description here

$\endgroup$
7
  • $\begingroup$ in r2, make [21:40]=0; $\endgroup$
    – phanitej
    Apr 20, 2015 at 8:24
  • $\begingroup$ What is the shift? The resulting signal should be a triangle between indices 20 and 60. What do you get? Maybe you can add a link to a plot. $\endgroup$
    – Matt L.
    Apr 20, 2015 at 8:52
  • $\begingroup$ @MattL. I this is what i expect, too. But it is a triangle between the indices 0 and 40. The question raised, because my output differs from the numpy-convolve-output. I updated the script to show the differences. Here is a link to the ploted output: picload.org/view/idgaglw/cap.png.html $\endgroup$
    – rikisa
    Apr 20, 2015 at 12:34
  • $\begingroup$ I don't have numpy installed so I can't run your script. You could post links to figures comparing your output and the output of the convolve output. What's the difference between the two. Don't you get a triangle as I described it in my first comment? $\endgroup$
    – Matt L.
    Apr 20, 2015 at 12:35
  • $\begingroup$ @MattL. you where faster answering than me editing the link in ;) Her is the output: picload.org/view/idgaglw/cap.png.html $\endgroup$
    – rikisa
    Apr 20, 2015 at 12:40

1 Answer 1

2
$\begingroup$

Note that multiplying the FFTs and taking an IFFT is equivalent to cyclic/circular convolution. This is not the same as linear convolution. However, your signals have sufficient zero-padding for the two types of convolution to be equivalent. The correct result of the linear (and cyclic) convolution is what you obtained via FFT and IFFT, a triangle between indices $20$ and $60$, as shown in the figure. This result is easy to predict using graphical convolution, as explained in this animation (from Wikipedia).

The strange result of np.convolve with the option same can be explained as follows: the result is the center part of length $100$ of the linear convolution of the two signals. Since the linear convolution is a signal of length $199$ ($=N_1+N_2-1$) with $99$ trailing zeros, the same option cuts out the center part between indices $50$ and $149$. So the result is the right half of the cyclic convolution with $49$ zeros added at the end, as shown in the bottom right figure.

$\endgroup$
2
  • $\begingroup$ thanks, this helps a lot. What do you mean by "shifting and multiplying it with the other signal"? That I'll see a shift in the time domain according to the 'shift' due to flipping a input-signal? Thanks again! $\endgroup$
    – user15552
    Apr 21, 2015 at 21:06
  • $\begingroup$ @rikisa: I was referring to the concept of graphical convolution, which works well for visualizing the convolution of simple functions. From this you can see immediately that the result must be a triangle starting at index 20. $\endgroup$
    – Matt L.
    Apr 22, 2015 at 7:42

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.