Using Fast Convolution to apply HRIR to soundwave

Question

I have a dozen source sound waves; each is about one second duration. I want to put each one through a digital filter (I'm truncating it to 128 taps).

Currently I'm doing this with a bog standard convolution. It is chewing up a lot of CPU.

I would like to switch to fast convolution.

Could someone outline the steps?

I'm aware that the basic technique is iFFT ( FFT(src) * FFT(filter) ), but the source and the filter are different lengths.

So what I'm imagining doing is this:

For each (source, filter) pair:

• Truncate each filter at 512 taps and FFT it to give 256 frequency bins.

• Now step through the source at 128-sample increments using a window size of 512.

  For each step,
  * multiply by a (Hanning?) window,
  * FFT
  * multiply FFT with FFT of filter (complex multiplication on each bin)
  * add to destination buffer

• Divide amplitude of destination buffer by 4, as we did 4 x overlap

Questions I have at this point are: 1. Is the basic method right? 2. Do I need to zero-pad my filter? 3. Is 4x overlap appropriate / optimal? 4. is that windowing correct? Is there any way to optimise out the windowing step? 5. how good will this output be compared with standard convolution?

π

EDIT: I've just noticed that dividing by 4 at the end is probably wrong, shouldn't it be using the area under the windowing function A_w? So multiplying everything by A_w / 4. Would that be correct?

Answer 1

Google "overlap add". Quick outline

1. zero pad filter to 256 taps, do an FFT
2. Initialize and "overlap" buffer of length 128 taps to all zeros
3. Initialize an input pointer to 0
4. Loop starts here
5. Take 128 samples from your input starting at input pointer. Zero pad to 256, FFT
6. Multiply the FFTs
7. Inverse FFT, add overlap buffer to the first 128 samples, output these samples. Put the second 128 samples into the overlap buffer
8. Advance your input pointer by 128 samples and go back to step 5. Repeat until the input is all done

Some quick tips:

1. Overlap save is slightly faster but a little less intuitive.
2. If filters and signals are all real valued you can speed things up further by either implementing a real valued FFT that's based on an N/2 complex FFT or by combining filters and/or signals in pairs
3. 128 is probably close to the break even point between FFT based and direct FIR filtering. I wouldn't expect huge gains. Depending hardware and level of code optimization it may actually be slower.