Intuitive understanding of how 'overlap save' works in contrast to 'overlap add'

Question

I am having a hard time to grasp how overlap save is exactly working in contrast to overlap add.

The starting of both procedure seem pretty similar. Both algorithms are trimming the input series $x[k]$ into pieces of length $L$ and then do a partial circular convolution with the impulse response $h[n]$. The convolution part would be done using the related DFT formula in practice.

I know that for overlap add these partial convolutions $y_k$ are added in the end to result in $y[n]$.

What is happening for overlap save afterwards differently?

Answer 1

Here's a sketch of what comes out of your "circular" convolution if you're careful to avoid the circular part. Note that I'm being general here -- normally the leading zeros wouldn't be there, and the trailing zeros only might be there.

The key to using overlap & save is to take the definitely good stuff, trim off everything else, concatenate the sections, and find joy.

The key to using overlap & add is to recognize that the increasingly good stuff plus the decreasingly good stuff from the previous segment adds up to definitely good stuff. So you take a slightly larger segment, add the latest increasingly good stuff to the last decreasingly bad stuff, and find joy. The bottom line is that with some more bookkeeping to get your output right, and the need to do the summation, you can do fewer FFTs per output sample.

As to which is best -- that's going to be a tactical decision that depends on what filtering you're doing and how expensive it is on your hardware to do the 'add' part of overlap & add, vs. the extra FFTs to do overlap & save.

Answer 2

The result of a convolution between vectors of length N and M (if both are greater than 1 sample in length) is longer than either N or M. So, for block based (same block length for both input and output) algorithms, the problem is what to do with a convolution output longer than the input.

Overlap add or overlap save are used to solve this problem.

In overlap add, the "tail" of the convolution result is saved, to be added to the result of the subsequent convolution or convolutions. The current block is output only after summing any previously saved "tails" that should overlap it.

For tails longer than one block length, this may require saving and summing (lots of "add" operations) several block length fragments of multiple tails into any result block.

In overlap save, the input block or blocks are saved, the convolution is done using a concatenation of all the saved input blocks and the current input block (to create a length >= N+M-1). Then, only the end of that convolution is output, since it includes the resulting overlapping convolution portions of all the previously saved blocks as well as for the current input block. The earlier portion, prior to the output block, of the longer convolution is then discarded. No "tail" results need to be saved. And no extra "add" ops are required (thus just "save", no add.)

For convolutions with results longer than twice the block length, this may require a much longer block convolution (e.g. a longer FFT) than twice the block length. Plus memory for multiple save blocks.

Answer 3

Beyond the good explanations given here I found the examples from this website quite excellent. I will use the pictures to show the general procedure with the related definitions.

I will leave out what kind of procedure for convolution is used as other have pointed out that the exact convolution is also a tactical decision which depends on the exacts situation.

Given

• $x[n] = \{ 3, -1, 0, 3, 2, 0, 1, 2, 1 \}$
• $h[n] = \{1, -1, 1\}$
• $L = 3$
• $M = |h[x]| = 3$
• $N = L + M - 1 = 3 + 3 - 1 = 5$

Convolution by Overlap-Add

Step 1: creating $x_k[n]$

$x_k[n]$ is now defined like

• ${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

which can visually be presented quite good as:

Step 2: using convolution to get $y_k[n]$

$y_k[n]$ is defined as

• $y_k[n] = x_k[n](n - kL)*h[n]$ (note that t indices are shifted by $n - kL$ to zero for the non zero values)

So the point is that both signals are convolved in some kind of way so that $x_k[n]$ is shifted to start from $0$ again

• In the website from above this is shown quite nicely how this can be achieved by DFT or circular convolution.
• Other answers have pointed out that theoretically any procedure for convolution could be used.

Step 3: creating $y[n]$ using all $y_k[n]$

Now $y[n]$ can be written as

• $y[n]=\sum _{k}y_{k}[n-kL]=\sum _{k}(x_{k}[n-kL]*h[n])=(\sum _{k}x_{k}[n-kL])*h[n]$
• not that using $n-kL$ shifts the $y_k[n]$ so that they start at index $kL$ again.
• Since every $y_k[n]$ is of length $N$ they their overlap of $N-L$ values will be added

which can be presented tabular as

Convolution by Overlap-Save

Step 1: creating $x_k[n]$

First we fill $x[n]$ with $M-1=2$ zero values at the beginning.

Now $x_k$ is defined as

• $\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}$

we get as tabular form for every $x_k$

Step 2: Computing partial values of $y[n]$

Now we can compute every $y_k[n]$ on the fly and the concatenate the result in an array for $y[n]$ without have to do any adding at all, since the first $M-1$ value will overlap.

For a better understanding I will split this in two steps to get a beter overview though both steps are done in one loop for every calculated $y_k[n]$!

Step 2.1: using convolution to get $y_k[n]$

$y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m]$

So everything said about the convolution in Step 2 from overlap-add applies as well.

Step 2.2: adding the resulting $y_k[n]$ to get $y[n]$

We can define this step as $\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL]$

• So every $x_k[n]$ starts at $kL$ for it's value of $k$ but for the overlapping values just $0$ values are added, since the overlapping stuff is not required!

So in tabular manner this could be seen as: