# How to verify the convolution theorem in Julia?
**URL:** https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185
**Category:** General Usage
**Tags:** fftw, dsp
**Created:** [April 28, 2021, 5:42pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185 "2021-04-28T17:42:15Z")
**Posts on this page:** 16
**Page:** 1
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 28, 2021, 5:42pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/1 "2021-04-28T17:42:15Z")
I’ve trying to prove [convolution theorem](https://en.wikipedia.org/wiki/Convolution_theorem) in Julia but without success. Say I have two function f1 = sin(30πt) & f2 = sin(10πt). Then, I have the following code
```julia
fconv_fda = ifft(fft(f1).*fft(f2))
fconv_tda = DSP.conv(f1,f2)[1:length(f1)]
plot(fconv_tda)
plot!(real.(fconv_fda))
```
But both the plots turn out to be different. What am I doing wrong here?
---
### Author:  [@jling](https://discourse.julialang.org/u/jling)
#### Post date: [April 28, 2021, 6:02pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/2 "2021-04-28T18:02:16Z")
you can’t prove theorem with numerical calculation
---
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 28, 2021, 6:05pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/3 "2021-04-28T18:05:02Z")
Okay, wrong choice of word. I just want to say that both values come out to be same, which is what I expected. Is there something I’m missing here?
---
### Author:  [@Pbellive](https://discourse.julialang.org/u/Pbellive)
#### Post date: [April 28, 2021, 6:46pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/4 "2021-04-28T18:46:54Z")
Welcome to the julia discourse @Minimum-Pollution-96!
I don’t know exactly what’s going on with your example above but I would guess it’s some kind of mismatch between the conventions being used by the DSP and FFTW packages (I’m assuming you’re using FFTW for your Fourier transforms. One thing I noticed is that if you do
```julia
t = 0:0.0001:0.5;
fconv_fda = ifft(fft(f1).*fft(f2)) ./ 2
```
then you get
```julia
julia> norm(fconv_fda - fconv_tda)/norm(fconv_tda)
0.00021074444869044446
```
so things are starting to match up well. One handy resource is to start digging into the conventions is: [API · AbstractFFTs.jl](https://juliamath.github.io/AbstractFFTs.jl/stable/api/)
Another good read, from the docs of the underlying FFTW C code:
> **[What FFTW Really Computes (FFTW 3.3.10)](http://www.fftw.org/doc/What-FFTW-Really-Computes.html)**
>
> What FFTW Really Computes (FFTW 3.3.10)
---
### Author:  [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)
#### Post date: [April 28, 2021, 6:57pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/5 "2021-04-28T18:57:11Z")
A good explanation is provided in the following lecture, in particular see chapter [4.2.6 Convolution of two finite-duration signals using the DFT](http://web.mit.edu/~gari/teaching/6.555/lectures/ch_DFT.pdf)
It basically boils down to pad the input signals with enough zeros:
```julia
using FFTW, DSP, Plots; gr()
Δt = 0.004; # sampling period (s)
t = collect(0:Δt:1.0)[1:end-1]
N = length(t)
f1, f2 = sin.(2π*15*t), sin.(2π*5*t)
f1p, f2p = [f1;zeros(N)], [f2;zeros(N)]
fconv_tda = DSP.conv(f1p, f2p)[1:N]
fconv_fda = ifft(fft(f1p).*fft(f2p))[1:N]
plot(t, fconv_tda,lw=3,lc=:red, xlabel="time /s",ylabel="Amplitude")
plot!(t, real.(fconv_fda),ls=:dash,lc=:black,lw=2)
```
---
### Author:  [@Datseris](https://discourse.julialang.org/u/Datseris)
#### Post date: [April 28, 2021, 8:56pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/6 "2021-04-28T20:56:47Z")
> [@jling](#):
>
> you can’t prove theorem with numerical calculation
Sorry, totally off topic here, but @jling I think the people that proved the four color theorem would disagree with you 😉
---
### Author:  [@apo383](https://discourse.julialang.org/u/apo383)
#### Post date: [April 28, 2021, 9:33pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/7 "2021-04-28T21:33:32Z")
I know you’re joking, but I believe that four-color proof was more about combinatorics than numerics. I doubt if there was any floating point arithmetic there 🙂
---
### Author:  [@jling](https://discourse.julialang.org/u/jling)
#### Post date: [April 28, 2021, 10:05pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/8 "2021-04-28T22:05:18Z")
that was not a “numerical calculation”.
I didn’t mean “computation done by computer can’t prove theorem”, we even have languages dedicated for writing formal proof.
---
### Author:  [@dpsanders](https://discourse.julialang.org/u/dpsanders)
#### Post date: [April 28, 2021, 11:33pm UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/9 "2021-04-28T23:33:54Z")
The whole point of interval arithmetic methods is to do rigorous computations using floating-point arithmetic. Various important theorems have been proved using these methods, including the Kepler conjecture on sphere packings.
---
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 29, 2021, 6:03am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/10 "2021-04-29T06:03:57Z")
Thank you so much! If its not too much, can I ask you regarding the corollary as well?
```julia
fmult_tda = f2.*f3
# fmult_fda = real.(bfft(conv(fft(f2p),fft(f3p)))/(2N)^2)[1:N]
fmult_fda = real.(ifft(conv(fft(f2p),fft(f3p)))/(N))[1:N]
plot(fmult_tda, size=(1000, 400))
plot!(fmult_fda)
```
I read in [FFTW Website](http://www.fftw.org/doc/The-1d-Discrete-Fourier-Transform-_0028DFT_0029.html#The-1d-Discrete-Fourier-Transform-_0028DFT_0029) that fft is unnormalised and hence I divided by N. But still, the plots generated is weird and seem to have lower frequency (with normalised amplitude?).
On a side note, [AbstractFFT.jl](https://juliamath.github.io/AbstractFFTs.jl/latest/api/#AbstractFFTs.bfft) seems to have separate function `bfft` which is unnormalised but it needs me to divide by `(2N)^2` instead. Is AbstractFFT not FFTW’s julia implementation?
Sorry for posting too many questions in single post. Also, thank you for the link. I’m trying to read through it. I tried to find the videos for lecture but those seem unavailable. This is my first time doing any kind of Fourier transform beyond basic math. So, if there’s any further suggestion, kindly let me know 🙂
---
### Author:  [@liuyxpp](https://discourse.julialang.org/u/liuyxpp)
#### Post date: [April 29, 2021, 6:09am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/11 "2021-04-29T06:09:26Z")
Can you share a link or any available reference for this proof? I am very interesting.
---
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 29, 2021, 6:31am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/12 "2021-04-29T06:31:34Z")
Thank you @Pbellive !
---
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 29, 2021, 6:38am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/13 "2021-04-29T06:38:07Z")
Now, if I consider only [1:N] portion of each after fft, I get the frequencies matched up but the amplitude is different.
```julia
Δt = 0.001; # sampling period (s)
t = collect(-1:Δt:1.0)[1:end-1]
N = length(t)
f1, f2 = sin.(2π*15*t), sin.(2π*5*t)
f1p, f2p = [f1;zeros(N)], [f2;zeros(N)]
fmult_tda = f1.*f2
fmult_fda = real.(ifft(conv(fft(f1p)[1:N],fft(f2p)[1:N])/0.5N))[1:N]
plot(fmult_tda, size=(1000, 400))
plot!(fmult_fda)
```
---
### Author:  [@dpsanders](https://discourse.julialang.org/u/dpsanders)
#### Post date: [April 29, 2021, 6:48am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/14 "2021-04-29T06:48:13Z")
The code and reference links are here:
> **[Academic references](https://github.com/flyspeck/flyspeck/wiki/Academic-references)**
>
> The formal proof of the Kepler conjecture. Contribute to flyspeck/flyspeck development by creating an account on GitHub.
Here are a couple of references. Unfortunately they’re not exactly light reading:
[https://annals.math.princeton.edu/wp-content/uploads/annals-v162-n3-p01.pdf](https://annals.math.princeton.edu/wp-content/uploads/annals-v162-n3-p01.pdf)
> **[A FORMAL PROOF OF THE KEPLER CONJECTURE | Forum of Mathematics, Pi |...](https://www.cambridge.org/core/journals/forum-of-mathematics-pi/article/formal-proof-of-the-kepler-conjecture/78FBD5E1A3D1BCCB8E0D5B0C463C9FBC)**
>
> A FORMAL PROOF OF THE KEPLER CONJECTURE - Volume 5
> **[revkepler.pdf](https://www.cl.cam.ac.uk/~jrh13/papers/revkepler.pdf)**
>
> 456.17 KB
---
### Author:  [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)
#### Post date: [April 29, 2021, 8:10am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/15 "2021-04-29T08:10:37Z")
@Minimum-Pollution-96, for the corollary one needs to take care of the negative frequencies with `fftshift`:
```julia
# "Corollary":
using FFTW, DSP, Plots; gr()
Δt = 0.004; # sampling period (s)
t = collect(-1:Δt:1.0)[1:end-1]
N = length(t)
f1, f2 = sin.(2π*15*t), sin.(2π*5*t)
fmult_tda = f1 .* f2
F1, F2 = fftshift(fft(f1)), fftshift(fft(f2))
F1p, F2p = [F1;zeros(N)], [F2;zeros(N)]
fmult_fda = real.(ifft(DSP.conv(F1p,F2p)[1:N]))
plot(t,fmult_tda, lw=3,lc=:red, xlabel="time /s",ylabel="Amplitude")
plot!(t,fmult_fda/(0.5N), ls=:dash,lc=:black,lw=2)
```
---
### Author:  [@Minimum-Pollution-96](https://discourse.julialang.org/u/Minimum-Pollution-96)
#### Post date: [April 29, 2021, 8:32am UTC](https://discourse.julialang.org/t/how-to-verify-the-convolution-theorem-in-julia/60185/16 "2021-04-29T08:32:30Z")
Thank you!