# Overlap Add - which length to use?

I am doing realtime audio. Let's say I have a signal $$x(n)$$ which is passed in blocks of 512 (siobuffer) to the program filter/FFT method. Within this block I want to convolve the signal with the filter $$u(n)$$ (impulse response) of length 8192K. So I zero pad the asio block from 513 to 8192K, do FFT of both arrays and multiply the results. After IFFT, I get the convolved signal $$y(n)$$ of length 8192K which I want to pass to the output asio buffer (lets say of length 512, too).

Now comes my problem: how much overlap-add to use? From my understanding, I must overlapp add the whole 8192K to the last byte, no? This means I divide $$y(n)$$ of 8192 by 512 into 16 blocks and subsequently overlapp-add all those 512 blocks to the next processed input blocks. When I read about overlap add in general, there are always examples where people have outputs $$y(n)$$ just a little longer than the input, so they normally overlap add approximately 1.5 of a imputblock.

Is there a mistake in my thoughts? Do I just need to overlapp add parts of $$y(n)$$, or must I overlap add all my 16 blocks each time?

You have a bunch of options here

1. You can zero pad both impulse response and signal to 16k, FFT and multiply. That's very inefficient though. Keep in mind that the sum of length of filter and signal need to be equal or smaller then the FFT size, hence an 8k FFT doesn't work. This gets a little better if you can truncate the 8k impulse response down to 7.5k. Then you can use an 8k FFT since 7.5k+512 <= 8k
2. You can keep accumulating 512k buffers until you have 8k of signal. Then zero pad both to 16k, FFT and multiply. That's a lot cheaper but also increases the latency substantially and you need to do the processing in a different thread.

Typically the best option here is a Segmented Overlap Add or Block Convolver. This works roughly like this

1. Break your 8k impulse response into 16 chunks of 512 each. Zero pad to 1024 and FFT. Now you have 16 frequency domain transfer function vectors $$H_k(z), k= 0,1,2...15$$
2. At every frame n, you get a new signal block $$x_n(t)$$ of length 512. Zero pad to 1024 and FFT. Now have the frequency domain signal vector $$X_n(z)$$. Make sure you keep the last 15 frames around as well, so you have $$X_n(z), X_{n-1}(z) ... X_{n-15}(z)$$
3. Now multiply the signal vectors with the transfer function vectors and sum up all the results. $$Y_n(z) = X_n(z) \cdot H_0(z) + X_{n-1}(z) \cdot H_1(z)+ ... +X_{n-15}(z) \cdot H_{15}(z)$$
4. Inverse FFT, you get 1024 time domain samples, $$y_n(t)$$
5. Manage the overlap. Create the output as the first 512 samples of $$y_n(t)$$ of plus the last 512 from the previous frame $$y_{n-1}(t)$$. Keep the last 512 samples from the current frame, $$y_n(t)$$, as overlap for the next frame.

This method is very efficient since you only have to do two 1k FFTs per frame and it also keeps the latency low. There are ways to improve this further by leveraging that the input data is real and not complex, but that should probably be a different question.

If you don't want to manage the overlap manually, use overlap-save instead. https://en.wikipedia.org/wiki/Overlap%E2%80%93save_method

• thank you for your help. Nr. 1 suggestion I like very much since I am running in serious time problems with smal asio buffers (have been padding filter and buffer to 16K. so far...) . SO this should already improve lots! 2. suggestion I have to try. will this way of breaking the filter down to small chunks (512), zero pad them to 1024, then muliplying 16times and summing, then IFFT, be faster then solution 1, with zero padding the asio once to 8k and doing only one multiplication ?(but having a 8k FFT)? – f.f Jul 3 '19 at 12:34
• Chopping it into 16 blocks will be WAY faster. I'd say about 8-10 times faster than doing 8k FFTs on each frame. The number of vector multiplications is similar: the block convolver has 16 blocks but the blocks are lot shorter than the 8k FFT output. Processing time is dominated by the FFT anyway. – Hilmar Jul 3 '19 at 16:36
• I am getting in trouble with this methode unfotunately. Keeping 15 Samples from past and mixing produces kind of artificial reverse reverb effekt. Maybe i do somting wrong, but can not geht mit. And Ideal? – f.f Jul 4 '19 at 18:14