2

Currently I've implemented an overlap-add method using resources on the internet, but I couldn't find a well documented way to minimize the cost of the method. In other words, how do I pick the window size so that the algorithm would work with the best performance possible? For now I use impulse response size and a constant multiplier to determine window size, but since the input signal size might vary, how to determine multiplier in relation to the input signal size?

My concern is performance, but the bottleneck is not addition, but the amount of performed FFT convolutions. Experimentally I found out that for each impulse response size there is an optimal window size, yet it varies. For example, if I pick 40000 samples of input signal and 128 samples of impulse response signal the optimal ratio between window and impulse response lengths is approximately 1:24.

It seems that Wikipedia suggests to use 1:8 ratio for both methods, as seen in the pseudocode of both overlap-add and overlap-save methods, then in the next section they provide measures of complexity for the methods, but I'm unable to wrap my head around how to utilize this information.

Ocelot
  • 121
  • 4
  • Have you read the answer to this question and the article cited there? – Matt L. Jan 27 '20 at 11:54
  • @MattL. what article? It leads to the 404 page – Ocelot Jan 27 '20 at 12:24
  • Try again, it's there now. Google is your friend. – Matt L. Jan 27 '20 at 12:56
  • @MattL. okay, so where the answer is, exactly? The article is not even about overlap add, and the question is unrelated. – Ocelot Jan 27 '20 at 17:16
  • Which page, which line? I don't know, it might not even be there at all, but you might learn something anyway. And if efficiency is your concern you might want to check out overlap-save, but it is all up to you. – Matt L. Jan 27 '20 at 17:23
  • @MattL. the benefit of overlap save comes from the lack of addition, however, the windowed nature of the method is still there, just another way of handling overlaps. So even if I pick overlap save, the question will still remain unanswered. How do I pick an optimal window size? – Ocelot Jan 27 '20 at 17:35
  • 1
    I have a comprehensive answer about this in another answer. You still have to come up with your relative cost coefficients, but if you have a 128 sample impulse response, i think you want an FFT size of either 512 or 1024. – robert bristow-johnson Oct 24 '20 at 17:46
  • 1
    I recommend the paper by fred harris “On the Use of windows for harmonic analysis using the discrete Fourier transform” where he provides the analytic considerations you seek – Dan Boschen Jun 21 '21 at 17:02

1 Answers1

-1

The optimal size is likely not just algorithmic, but depends on the cache sizes and levels and the compute-to-memory-bandwidth ratio for the particular processors and systems(s) on which you plan to run this code. Also, your applications latency requirements (which filling big FFTs add).

hotpaw2
  • 35,346
  • 9
  • 47
  • 90
  • 1
    Well I assume that's why we have big O notation. So what's the solution, can't we at least approximate the optimal size? – Ocelot Jan 28 '20 at 08:09