Shift in Time Domain After DFT Based Convolution

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:

• in r2, make [21:40]=0; – phanitej Apr 20 '15 at 8:24
• 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. – Matt L. Apr 20 '15 at 8:52
• @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 – rikisa Apr 20 '15 at 12:34
• 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? – Matt L. Apr 20 '15 at 12:35
• @MattL. you where faster answering than me editing the link in ;) Her is the output: picload.org/view/idgaglw/cap.png.html – rikisa Apr 20 '15 at 12:40

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.