2
$\begingroup$

We often hear that "convolution in time is the same as multiplication in frequency", and vice versa, that "convolution in frequency is the same as multiplication in time".

So in a typical windowing operation, we do a point-wise multiplication of a signal $x[n]$, with a window $w[n]$. This means that in the frequency domain, we are performing $X(f) * W(f)$.

My question is the following: I wish to illustrate this for myself, but I am not sure what lengths FFTs to take, and what type of convolution to do. (Circular? Linear? etc). Those details seem to be missing from all sources I look at.

So, if you want to do convolution in the frequency domain, what lengths FFT do I pick to compute $X(f)$ and $W(f)$, and what type of convolution am I doing? Thank you.

$\endgroup$
2
$\begingroup$

the FFT is a fast method of doing the DFT. yes, multiplication in one domain corresponds to convolution in the reciprocal domain. and since the DFT is a totally circular operation, any consequential convolution done in one domain by the DFT by multiplication in the other domain is circular convolution. you don't have a choice about it. to make a circular convolution look like linear convolution, you must zero-pad sufficiently.

how many zeros to pad? need to consider how fast convolution (overlap-add or overlap-save) works. if $N$ is the DFT length, the non-zero lengths of the two sequences being convolved, must not add to more than $N+1$ otherwise there will be overlapping and aliasing of non-zero components.

$\endgroup$
  • $\begingroup$ ...I have a signal $x[n]$ of length $M$. I have a window $w[n]$ of length $N$. I would like to convolve the spectrum of this window with the spectrum of the signal. So what lengths should I pick to FFT them by, and do I do a circular or linear convolution? Thanks. $\endgroup$ – TheGrapeBeyond Feb 27 '14 at 14:03
  • $\begingroup$ that's easy. from what i wrote and now, given your definitions of $M$ and $N$, your FFT would have to be of size at least $M+N-1$. your $x[n]$ would be padded with at least $N-1$ zeros and your window $w[n]$ would have to be padded with $M-1$ zeros. you do circular convolution by FFTing the zero-padded $x[n]$ and $w[n]$, complex multiplying the resulting $X[k]$ to $W[k]$, then inverse FFTing $X[k]\dot W[k]$. linear convolution will be equivalent to the circular convolution if you zero-pad sufficiently (as specified above). $\endgroup$ – robert bristow-johnson Feb 27 '14 at 22:08
  • $\begingroup$ Put your comments in the answer is better since the comments arent working. $\endgroup$ – TheGrapeBeyond Feb 28 '14 at 17:19
  • $\begingroup$ i did put it into an answer. you just want me to spell it out to you. $\endgroup$ – robert bristow-johnson Feb 28 '14 at 18:31
  • $\begingroup$ What? No I asked you to put it into the answer because the comments are unreadable. $\endgroup$ – TheGrapeBeyond Feb 28 '14 at 19:33
1
$\begingroup$

For pointwise multiplication of two signals, they should have the same length, say N. Do the fft() with N, then circular convolution with N, then ifft(). There is a difference of a factor of N probably because of the 1/N difference between the definition of fft and ifft.

a=[1 2 3 4 5];
b=[4 5 6 7 8];
ifft( cconv(fft(a), fft(b), 5))
a.*b

You can deduce that you need circular conv in freq domain because, were it linear convolution, the result would be longer than N, but the pointwise multiplication is of length N.

$\endgroup$
  • $\begingroup$ So the convolution in the frequency domain of two $N$ length vectors should give me another $N$ length vector since its circular? $\endgroup$ – TheGrapeBeyond Feb 27 '14 at 20:02
  • $\begingroup$ Yes. Of course, in general, you can specify a larger number of points for the circular convolution, but there's no need here. $\endgroup$ – nikcleju Feb 28 '14 at 9:25

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.