Convolution in the frequency domain

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.

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.

• ...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. Feb 27 '14 at 14:03
• 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). Feb 27 '14 at 22:08
• i did put it into an answer. you just want me to spell it out to you. Feb 28 '14 at 18:31
• So the convolution in the frequency domain of two $N$ length vectors should give me another $N$ length vector since its circular? Feb 27 '14 at 20:02