1
$\begingroup$

I am trying to understand where does the convolution fit in Discrete Fourier Transform. I know that convolution is producing a third signal from two other signals. I also know that DFT transforms one signal from time to frequency domain.

So, what is the relationship between the two (if any)?

Improve this question
$\endgroup$
  • $\begingroup$ In Fourier space convolution is a simple multiplication, so to make convolution of two signals with equal length you should make their FFT, multiply them, make inverse FFT of product. Absolutely correlated signals will give you a large peak in zero shift value of convolution. $\endgroup$ – Eddy_Em Apr 3 '13 at 7:28
4
$\begingroup$

FFT and DFT are a faster way to implement convolution. Since convolution in time domain corresponds to multiplication in the Fourier domain, you replace the sliding-window based implementation of convolution (in time domain) by a pointwise multiplication (in Fourier domain). This avoids you an extra inner loop over the input data and saves time.

With respect to boundary conditions, there is a minor difference with finite-length signals. Using the convolution theorem to compute a convolution product in the Fourier domain implicitely assumes that the input data is periodic, i.e., when you reach the right end of the signal you re-enter by its leftmost part. This is also known as circular convolution. If you need to have a convolution of explicitely non-periodic signals, you can add zeros at the beginning and end of your signal to avoid these border effects.

Improve this answer
$\endgroup$
  • $\begingroup$ It should be mentioned that DFT implements the circular convolution unless zero padding is applied. $\endgroup$ – Deve Apr 3 '13 at 12:07
  • $\begingroup$ @Deve you're right. I have edited my answer, thanks. $\endgroup$ – sansuiso Apr 3 '13 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.