2
$\begingroup$

I'm surveying for feasibility techniques for a potential future project that's rather out of my past areas of expertise, and I have a fairly basic question. Of course if it looks feasible I will have to learn a whole lot more on the topic.

What is the equation to compute the number of FFTs/IFFTs per sample required, given the number of samples in the FFT n, the number of samples in the FIR m, and the number of samples of audio data this is applied to at a time x?

Improve this question
$\endgroup$
2
$\begingroup$

Depends on your algorithm. Assuming overlap add/save and a filter length of N we would get:

  1. Zero pad to 2*N and forward FFT: 4*N*log2(2*N) multiplies
  2. Spectrum multiply: 8*N multiplies (4*N if input and filter are real)
  3. Inverse FFT: same as 1
  4. Overhead for padding, overlap handling, house keeping etc.

There are between 1 and 1.5 times the number of adds. There are also various ways to optimize this.

In general, convolution is not always the best way to create reverb. It is computationally expensive, it adds a lot of latency, and it is very difficult to update or modify in real time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Are there any high-quality reverb algorithms that are faster than FFT? I should also note that the chip I'm looking at has an FFT/IFFT accelerator that is ~4x the speed of a software implementation (yet tragically is not asynchronous). $\endgroup$ – Justin Olbrantz Oct 6 '13 at 0:48
  • $\begingroup$ Oh yes. If I'm not mistaken the answer you gave was for how many multiplies it takes to do a convolution when the FIR is N or less? What is the complexity when the FIR > N? $\endgroup$ – Justin Olbrantz Oct 6 '13 at 0:54
  • 1
    $\begingroup$ Pretty much every commercial reverb algorithm is faster than FFT. Also FFT is for most application prohibitive because of the excessive latency. The complexity is for any number N. N is the length of the filter. If your filter is longer, than just adjust N accordingly $\endgroup$ – Hilmar Oct 6 '13 at 16:40

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.