FFT-based fast convolution vs IIR filtering

Question

I'm doing an multichannel audio equalizer system on a chip, which is parametric EQ, usually implemented in cascaded biquad IIR filters.

My problem is that I use a lot of IIR filters due to multiple frequency bands (such as 10 bands), and I'm wondering if I should truncate the impulse response of IIR filters as an FIR and use FFT-based fast convolution for speed.

Let's say if I need $L$ bands equalizer. So EQ filters are $2L$-th order IIR filters for each channel. We know that an IIR filter of order $K$ roughly requires $2K+1$ multiply-accumulate (or MAC) instructions per sample. So I totally need $4L+1$ MACs per sample and specifically $41$ MACs per sample for 10 bands.

Now if I use the truncated IIR of each channel as an FIR filter of a length $N$, and let the signal frame length equal to $N$. By Applying the overlap-save method to calculate the linear convolution, we take an FFT of length $B=2N$, do complex multiplications for $N+1$ FFT bins, and then take an IFFT of length $B$. Assume that a $B$-point FFT has a complexity of $\frac{1}{2}B\log_2B$, the total complexity of each channel is around $$ \frac{1}{N}\left[\frac{1}{2}B\log_2B + 4(N+1) + \frac{1}{2}B\log_2B\right] = 2\log_22N + 4 + \frac{4}{N} $$ for most popular frame size it is smaller than $41$, indicating that FFT-based FIR filtering is more efficient if the order of IIR filter is higher than a specific threshold.

I understand there is a precondition that the FIR should have a similar frequency response as the IIR. Low frequency usually needs a longer FIR, but in my case there is an active crossover network so I will decimate the low frequency channel and equalize it at a lower sample rate. For the other channels above 300 Hz, I think 1024 or 512 tap is enough to approximate an IIR filter.

I think that testing on the target chip is the ultimate way to check which one is faster, but I still want to verify it theoretically. I'm not sure if I'm on the correct way. Any suggestions will be welcome.

Answer 1

For a simple 10-band equalizer, it would be very hard to beat the IIR implementation. For most HW architectures the break-even point between direct FIR convolution and Overlap Add/Save (OLA) is somewhere between 64 and 128 taps and you seem to be still below this threshold.

The exact number of the break even point is hard to calculate. You can certainly tally up the number of operations, but these days execution is often gated by other constraints: memory bandwidth, pipeline stalls, cache misses, ability to use vectorization and/or SIMD, hardware support for bit-reverse and circular addressing, etc.

There are many other advantages to the IIR implementation:

1. Simple algorithm structure: much easier to implement, debug and test
2. Much, much smaller memory footprint for both data and code
3. Easy to recalculate the filter in real time. If the user only adjusts one band, you only need to update one band filter (and maybe the total gain). For the OLA, you need to recalculate the band filter, figure out the truncation, cascade all band filters, zero-pad and FFT the whole thing every time someone touches a dial.
4. Low latency. IIR has virtually no latency. OLA has an inherent latency of two frames. At a frame size of 1024 samples @44.1kHz that's almost 50ms. There are ways to work around this, but that adds complexity and is less efficient.
5. Cross over and down-sampling the low frequency requires careful phase management in the cross over region. 300 Hz is an important region, you probably want to keep this clean.

Answer 2

For medium-sized convolutions, the fastest algorithm is usually Karatsuba convolution.

This is essentially the same algorithm as Karatsuba multiplication, but with elementwise operations (add, subtract, shift) on vectors rather than normal operations on multi-digit numbers. Karatsuba convolution works with real numbers and produces a linear convolution right away, which means the constant factor is 8-16 times lower than with FFT convolution. Asymptotic complexity is worse, n^log₂3 compared to n log₂n, so for larger problems FFT convolutions win. For a real-valued linear convolution, break-even is roughly at n=10000. Break-even between naive and Karatsuba convolution can be as low as n=10.

Karatsuba convolution is also much easier to implement than FFT convolution, it is much less code and works with fixed-point or integers if desired. For a typical overlap-add signal processing application, Karatsuba is best. FFT convolution is worthwhile for huge problems or if you're working with complex numbers anyway, where Karatsuba loses much of its advantage in terms of constant factor. Here is a simple example in Matlab:

% naive convolution
result = conv([1,2,3,4], [6,7,8,9])

% Karatsuba convolution
z1 = conv([1,2], [6,7])
z3 = conv([3,4], [8,9])
z2 = conv([1,2]+[3,4], [6,7]+[8,9]) - z1 - z3
result = [z1,0,0,0,0] + [0,0,z2,0,0] + [0,0,0,0,z3]

(result is [6,19,40,70,70,59,36] in both cases)