1
$\begingroup$

We learned that overlap add and overlap save are used as fast convolution methods, because they can be applied with fft due to the formula $x[n] * y[n] = \text{IFFT}(X[k] Y[k])$

So now I was wondering why it should have a speed performance to use overlapping effects when one signal is cut in small pieces of length $L$

  • Fast convolution with FFT is said to be in $O(N \log N)$ where $N = |x[n]| + |y[n]| -1$
  • So when I trim $x[n]$ in $k$ pieces of length $L$ I set $M = |y[n]| + L - 1$ for each separate convolution I will get $O(k M \log(M)) = O(N \log N)$

So it should have a little bit better speed but when $N$ increases it will increase in the same order.

So are there any other reasons to use overlap algorihtms or might I be wrong with comparing the speed performance?

$\endgroup$
1
  • 3
    $\begingroup$ As ZR Han correctly pointed out, $\mathcal O(kM\log M) = \mathcal O(N \log M)\ne \mathcal O (N \log N)$; in fact, $\mathcal O(N\log M) \subsetneq \mathcal O (N \log N)$. $\endgroup$ Commented Feb 24, 2022 at 11:38

3 Answers 3

7
$\begingroup$

The main reason for using overlap-save or overlap-add is latency. Usually you don't want to wait for the complete signal before the first output samples can be computed. Of course, you also save memory if you don't need to store the complete signal before processing.

So if you want to do (quasi-)real-time filtering in the frequency domain, you need to process relatively small chunks of the signal. That type of processing is called block convolution. Overlap-add and overlap-save are two specific implementations of block convolution.

$\endgroup$
9
$\begingroup$

Apart from the latancy reason, fast convolution is faster than the linear convolution when $x[n]$ and $y[n]$ have similar lengths. Suppose the lengths of $x[n]$ and $y[n]$ are $M$ and $L$ respectively, and the number of FFT should be greather than $N=M+L-1$.

Fast convolution has a complexity of $O(N\log_2 N)$ while linear convolution has a complexity of $O(ML)$. When $M\gg L$, we have $N\approx M$ and the fast convolution is in $O(M\log_2 M)$.

You can see that fast convolution is not fast anymore when $\log_2 M>L$. Thus we need to split very long signal into blocks and apply OLA or OLS.

$\endgroup$
5
  • 2
    $\begingroup$ btw, $O(kM\log(M))=O(N\log N)$ should be $O(kM\log(M))=O(N\log M)$, that's the main difference, right? $\endgroup$
    – ZR Han
    Commented Feb 24, 2022 at 11:24
  • $\begingroup$ You set $M=|y[n]| + L - 1$, not $M=N-(|y[n]|+L-1)$. $\endgroup$
    – ZR Han
    Commented Feb 24, 2022 at 11:32
  • $\begingroup$ You are right, this was a bit misleading. I thought that M is dependent of N but M can be chosen arbitrarily so it is not correct. $\endgroup$ Commented Feb 24, 2022 at 11:35
  • $\begingroup$ @OuttaSpaceTime can't be chosen arbitrarily, it depends on the shorter sequence's length $\endgroup$ Commented Feb 24, 2022 at 11:45
  • $\begingroup$ @MarcusMüller yes I meant theoretically I could choose the shorter length $L$ arbitrarily, thus $M$ is arbitrarily as well, but you are right $M$ will with have a lower limit and upper limit for its size. Though not sure if there are other practical implications on the size of $L$ $\endgroup$ Commented Feb 24, 2022 at 11:48
3
$\begingroup$

Aside from Matt's great answer: Don't forget that typically, your filter's impulse response will be orders of magnitude shorter than your signal to be filtered; and in that, your formula is at least misleading (but it follows the underlying idea of $\mathcal O$-notation).

The time complexity you read in text books is essentially a theoretical statement with some disconnect from computing reality; for relevant sizes, you will mostly find compute architectures (both in the CPU and the digital logic design world) with high-latency, high-bandwidth, large-size external dynamic RAM, and then layers of caching to make that useful for locally jumping operations. If your whole computation fits in a cache, that greatly increases speed. Last benchmark I did, expect a single fetch from RAM to take the time of about 400 complex multiplications (!) on a modern x86_64 CPU.

So, thinking your FFT scales "smoothly" in complexity like $N\log N$ would suggest is really really misleading. There's jumps in real-world complexity that happen when your CPU, its caches and the memory controller can't prepare the data for the CPU to have it locally. And as there's typically three layers of caches in modern compute-optimized CPUs, you'll see these quite prominently. $N \log N$ becomes a good approximation once your sizes are generally beyond any cache sizes. And then it's still worth realizing that this is a growth rate limit, not an actual upper limit, so imagine arbitrary constants in front of that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.