Skip to content

Instantly share code, notes, and snippets.

@binary10

binary10/convolution-theorem.py

Last active November 5, 2022 17:34
Show Gist options
  • Save binary10/941db9d7bae3ecf1ae40c5104babf8b8 to your computer and use it in GitHub Desktop.
Save binary10/941db9d7bae3ecf1ae40c5104babf8b8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. binary10 revised this gist Nov 5, 2022. 1 changed file with 23 additions and 14 deletions.
    37 changes: 23 additions & 14 deletions convolution-theorem.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,24 +1,33 @@
    # Compute the convolution of a signal with itself,
    # then use the fft of the signal to arrive at the same convolution.
    # Initialize two signals with arbitrary length
    n, m = 5, 7
    convolution_length = n+m-1

    import numpy as np
    import scipy as sp
    u = np.random.randint(0, 255, n)
    v = np.random.randint(0, 255, m)

    # Initialize a signal
    v = np.random.randint(0,255, 2**5)

    # Convolve with self
    cv = sp.convolve(v,v)
    # Convolve the two signals
    cv = sp.signal.convolve(u, v)
    assert cv.shape[0] == convolution_length

    # Copy and pad signal


    # Now, apply the Convolution Theorem.
    ## Copy and pad signal. Padding is necessary to match the convolution length.
    vv = v.copy()
    vv.resize(len(cv), refcheck=False)
    vv.resize(n+m-1, refcheck=False)


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

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

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


    # Compare
    abs(fcv - cv) < .0001
    # Does the inverse transform of the product of the Fourier transforms of the signals equal the convolution of the two signals?
    assert np.allclose(fcv, cv)
  2. binary10 revised this gist Apr 27, 2022. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions convolution-theorem.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,6 @@
    # 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

  3. binary10 renamed this gist Nov 4, 2016. 1 changed file with 0 additions and 0 deletions.
    0 convolution-theorem → convolution-theorem.py
    View file
    File renamed without changes.
  4. binary10 created this gist Nov 4, 2016.
    21 changes: 21 additions & 0 deletions convolution-theorem
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,21 @@
    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