1
$\begingroup$

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!!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Moti Apr 1 '15 at 4:48
  • $\begingroup$ 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! $\endgroup$ – Alan Wolfe Apr 1 '15 at 5:10
  • $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Apr 1 '15 at 7:41
  • $\begingroup$ @robertbristow-johnson hi rbj, funny seeing you outside the music dsp list. Thanks for the info (: $\endgroup$ – Alan Wolfe Apr 1 '15 at 14:27
  • $\begingroup$ 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. $\endgroup$ – Moti Apr 2 '15 at 11:52
1
$\begingroup$

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.

In your case, you should append 44099 zeros to each signal before transforming it to the frequency domain. The result will then be 88199 samples long.

If the available FFT is shorter than 88199 you have to divide the signal into shorter blocks and apply the overlap add method.

$\endgroup$
  • $\begingroup$ Hey Deve, what if I don't have the time domain information of the signals to zero pad, what if I'm just generating IFFT bucket data and then creating time information... is there a way i can "zero pad" in the frequency domain to make it come out to be the correct length when using ifft to generate the time domain samples? $\endgroup$ – Alan Wolfe Apr 10 '15 at 23:08
  • $\begingroup$ @AlanWolfe Not sure if I understand you question. Just append zeros to the frequency domain vector so that it has the length of the IFFT. $\endgroup$ – Deve Apr 23 '15 at 8:30

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.