# Fast convolution with very high order FIR

I am investigating the overlap-add and overlap-save methods for processing an audio signal with a FIR. The FIR is a measured impulse response of a reverberant space and may be of order greater than 100,000. It appears that in order for O-A to work, the signal block length must be at least this length to keep the amount of overlap less than one block length. For example, if the signal block length is 100 ms of audio (L = 4410) and the IR is 3 s of reverb (M = 132300) then each block convolution produces 127890 outputs that must be added to subsequent block convolutions. Am I missing something?

you can split up your long impulse response into smaller segments and use multiple concurrent fast-convolutions that convolve each segment against your audio, align the delays correctly, and add up the result.

what must be the case for each segment (or one big segment if you don't split it up) is that if the FFT length is $N$ and the impulse response (or segment) length is $L$, the number of output samples you get for each frame is $N-L+1$. that's the case whether it's overlap-add or overlap-save. in either case, you pad your impulse response (or segment) with $N-L$ zeros (to bring it to length $N$) and FFT that.

• Note that you will still end up with at least 132300 samples to add to subsequent block convolutions, but chopped up into a sequence of many block operations. – hotpaw2 Mar 25 '15 at 0:55
• but @hotpaw2, you can do it with smaller FFTs. while i don't think a 256K FFT is normally too big to do with double-precision floats and a modern processor, it might be a numerical problem for smaller words. – robert bristow-johnson Mar 25 '15 at 3:16
• Yes. I am agreeing with you. You can build that long result with a large bunch of smaller block fast convolution operations, and also add it to the next data block result in a large bunch of smaller vector summings. Doing without thrashing the data caches is an interesting problem though. – hotpaw2 Mar 25 '15 at 4:27

Thanks for the responses. I have since found that my concerns were needless - you just need a long enough buffer. I wrote the following MATLAB function to process one block of input and tested it with a separate script on a large input stream. It worked just fine.

function [y,outBuffer]=overlapAdd(x,h,inBuffer)
L=length(x);
% M=length(h); add for error check
N=length(inBuffer); %N >= L+M-1
inBuffer=inBuffer+ifft(fft(h,N).*fft(x,N));
y=inBuffer(1:L);
outBuffer=[inBuffer(L+1:N); zeros(L,1)];


In my test case the block size L was 4800, the impulse response length M was 240000 and the total signal length was 352257. The buffer size was L + M + 1 = 244799.