# Do FFT-based filtering methods add intrinsic latency to a real time algorithm?

In a current audio processing application, I am working entirely in the time domain using IIR filters. This is so I can use an audio buffer of just 3 or 4 samples and can guarantee that there will be some form of audio output within that frame.

If I were to switch to FIR based filters (to reduce filter ringing time as outlined in this question), I would probably need to use an FFT-based overlap-add technique to maintain processing efficiency. As I see it, I would have to fill an FFT frame buffer with samples before I would be able to do the transforms. This would add an intrinsic latency to the algorithm proportional to the number of samples used to calculate the FFT. Am I missing a trick?

## 1 Answer

You are correct. FFT based processing adds inherent latency to your system. However there are ways to tweak this.

Let's assume you have an FIR filter of length "N". This can be implement FFT-based using the standard overlap add or overlap save method, where the FFT length would be 2*N. Overall system latency will also be roughly 2*N: you need to accumulate a frame of N samples and then while you are accumulating the next input frame, do the math on the current frame. By the time the second frame has been accumulated (time offset 2*N), the first frame is ready to go out. If you have a fast CPU you can speed this up somewhat by using different alignment for input and output frames but that's typically more bother than it's worth.

You can also break down the filter into K smaller blocks of length M, i.e. N = K*M. The FFT only needs to be done over M input samples and the delay and accumulation over the multiple filter sections is done in the frequency domain. Bill Gardner described a few flavors of that here: http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/Ga95.PDF It's often referred to as a "Block Convolver".

This allows to basically trade-off latency against efficiency and it provides a continuum between the direct FIR and the full-sized overlap add method. A nice side-effect of the Block Convolver is that the total filter length doesn't have to be a power of 2. For example you can implement a filter of 768 tabs as 6 blocks of 128 without any significant loss of efficiency.

• Nice tip about the block convolver! Thanks – learnvst Jun 1 '12 at 16:37