Linear and circular convolution in Python
<p>I'm trying to perform linear convolutions in Python by comparing the results from FFTs and convolution functions.</p>

<p>Python's <a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.fftconvolve.html" rel="nofollow noreferrer"><code>scipy.signal.fftconvolve</code></a> automatically does the necessary zero padding. If we do the calculation using only FFTs, we add a length of zeros after our input signal. Is there a way to trim the output array of the FFT result? (The <code>fftconvolve</code> has a <code>mode='same'</code> option where the output array is the same size as the input.)</p>

<pre><code>import numpy as np
from numpy.fft import fft,ifft
from scipy.signal import fftconvolve
import matplotlib.pyplot as plt

tf = 50
ti = -tf
N = 2**10
t = np.linspace(ti,tf,N)
T = (tf-ti)/N

x = np.exp(-4*t**2)*np.cos(t)
y = (t-2)/((t-2)**2+3**2)

z1 = ifft(fft(x,len(x)+len(y)-1)*fft(y,len(x)+len(y)-1)) # need zero-padding
z2 = fftconvolve(x,y,mode='same') # automatic zero-padding

plt.figure(0)
plt.plot(t,z2)
#plt.figure(1)
#plt.plot(t,z1)
</code></pre>

<p><strong>Note:</strong> Another issue is if we change the outputs to:</p>

<pre><code>z1 = ifft(fft(x,len(x)+len(y)-1)*fft(y,len(x)+len(y)-1))*T
z2 = fftconvolve(x,y)*T
</code></pre>

<p>(where <code>T</code> is a normalisation constant) then plot either <code>z1</code> or <code>z2</code>, we get strange boundary effects:</p>

<p><a href="https://i.stack.imgur.com/zGWKP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zGWKP.png" alt="enter image description here"></a></p>

<p>This effect is explained in <a href="https://dsp.stackexchange.com/questions/1933/how-to-remove-the-boundary-effects-arising-due-to-zero-padding-in-scipy-numpy-ff">this DSP post</a>, but I'm not sure how to apply the solutions to my system.</p>