Skip to content

Instantly share code, notes, and snippets.

@binary10

binary10/convolution-theorem.py

Last active November 5, 2022 17:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save binary10/941db9d7bae3ecf1ae40c5104babf8b8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save binary10/941db9d7bae3ecf1ae40c5104babf8b8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
convolution-theorem.py
# Compute the convolution of a signal with itself,
# then use the fft of the signal to arrive at the same convolution.
import numpy as np
import scipy as sp
# Initialize a signal
v = np.random.randint(0,255, 2**5)
# Convolve with self
cv = sp.convolve(v,v)
# Copy and pad signal
vv = v.copy()
vv.resize(len(cv), refcheck=False)
# Compute FFT
fv = sp.fft(vv)
# Inverse FFT of frequency signal
fcv = sp.ifft(fv * fv)
# Compare
abs(fcv - cv) < .0001
@timvieira
Copy link

timvieira commented Apr 27, 2022

this was helpful - thanks!

I tweaked it to support the convolution of any two vectors (of possibly different lengths).

# Initialize a signal
n, m = 5, 7
u = np.random.randint(0, 255, n)
v = np.random.randint(0, 255, m)

# Convolve u and v
cv = sp.signal.convolve(u, v)

assert cv.shape[0] == n+m-1

# Copy and pad signal
vv = v.copy()
vv.resize(n+m-1, refcheck=False)

uu = u.copy()
uu.resize(n+m-1, refcheck=False)

# Compute FFT
fu = fft(uu)
fv = fft(vv)

# Inverse FFT of frequency signal
fcv = ifft(fu * fv)

assert np.allclose(fcv, cv)

@binary10
Copy link
Author

binary10 commented Apr 27, 2022 •
edited
Loading

@timviera I'm glad it helped you -- thanks for sharing back. I especially enjoyed learning about np.allclose()

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment