# Convolution in frequency space with fft and ifft -> num output samples?

Let's say you had two 1 second sound samples at 44.1khz, and you wanted to convolve them in frequency space.

You FFT each one to get two arrays of complex numbers that each have 44100 items in them.

You then multiply each bin... for i = 0 to 44099 c[i] = A[i] * B[i]

Then it's time to turn it back into time domain samples. If you do an ifft you'll get 44100 time samples out, but when you convolve these two audio samples in time space, it'll give you 88199 samples out (44100+44100-1).

Obviously getting 44100 samples out is incorrect. At what part in the process did I go wrong? (:

Thank you!!

• What size of FFT you use? Doing it on all the 44,100 samples is usually not an FFT. You may try for the full 44,100 samples convolution a very long FFT of 128K (it really depends how much interest you have in the tails) or 64 K. If you really want to run sections of 128 or 256 samples, you should do it in parts. – Moti Apr 1 '15 at 4:48
• That makes sense. For the sake of argument though, lets say i had two sets of data in the frequency domain that were each 256 samples long. I multiply them to do time domain convolution, then converting back to time domain with ifft, i'd get 256 samples, not 511, so doesn't seem like the real convolution. Also, do you happen to know of info on how to do fft in smaller sections? ive heard you need to use window functions but am not real sure why that is or how to apply that. Thanks! – Alan Wolfe Apr 1 '15 at 5:10
• need to zero pad. remember that using the FFT does circular convolution. to make your circular convolution look like linear convolution, you will need to zero-pad both sequences to twice the length, then FFT both, then multiply and then iFFT. – robert bristow-johnson Apr 1 '15 at 7:41
• @robertbristow-johnson hi rbj, funny seeing you outside the music dsp list. Thanks for the info (: – Alan Wolfe Apr 1 '15 at 14:27
• You need to know what were the samples of the data in the time domain. Remember that the FFT assumes repeated signal so the simple convolution uses some samples not exactly as you may expect. – Moti Apr 2 '15 at 11:52

What you do is called circular convolution but you want "linear" convolution: Say you have two signals of length $N$ and $M$. Append zeros to both time-domain signals, so that their length is $L=N+M-1$, then calculate the $L$-DFT of both signals, multiply them in frequency-domain and convert the result back to time-domain.