title: Linear and circular convolution in Python
body: <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>