CODEWITHSUNDEEP
pythonnumpyfftconvolution
phan
phan

Reputation: 109

Covolution of two Discrete Fourier transforms

Given two finite sequences x(i) and y(i), i = 1...n. I known that the Discrete Fourier Transform (DFT) of the pointwise product x.y is equal to convolution between two DFT of x and y:

DFT(x.y) = (DFT(x) * DFT(y))/n

Now I test in python this simple code:

import numpy as np
x = np.array([1,2,3])
y = np.array([0.1, 1, 0.5])

Dftxy = np.fft.fft(x*y) # DFT(x.y)

Dftx = np.fft.fft(x)
Dfty = np.fft.fft(y)
CDftxy = np.convolve(Dftx,Dfty,'same') / 3 # (DFT(x)*DFT(y))/n

The result is:

Dftxy = [3.60+0.j, -1.65-0.4330127j, -1.65+0.4330127j]
CDftxy = [-2.10-0.40414519j, -1.65+0.4330127j, 0.40+0.j]

The values of Dftxy and CDftxy are different. Is there any error in my code?

Upvotes: 0

Views: 1029

Answers (2)

Mohammed Li
Mohammed Li

Reputation: 901

You have to transform it back:

recovered_vector = np.fft.ifft(CDftxy)

but yeah, periodic boundary conditions .. you will not see anything reasonable for three membered vector

Upvotes: 0

hotpaw2
hotpaw2

Reputation: 70673

You have to zero-pad your FFTs if you want your fast convolution results to produce a linear convolution result. Otherwise, if you don't zero pad, you will get a circular convolution (end convolution results wrap around and sum with the front) from the element-wise multiplication of 2 FFTs.

Upvotes: 1

Related Questions