Talk:Overlap–save method

new pseudocode, Mar 5, 2014

Yes, the previous algorithm is "simple", which is a good thing. The difference is that it chooses the FFT size (N) in an optimal way, and derives the arbitrary segment length (L) accordingly. No zero-padding is necessary, so the claim "circular convolution used in it may be wrong, because we should pad zeroes in the head at initial step" is wrong and misleading. Your more-complicated algorithm, prioritizes the choice of L above the FFT size, P, (an important performance parameter). The claim that your inefficient and complicated code achieves the same result as conv(•) (as does the efficient, simple code) is not sufficient.
--Bob K (talk) 20:07, 5 March 2014 (UTC)[reply]

Illustration of overlap-save algorithm

The figure is wrong (April 2015)

As can be seen in the Octave source code, the figure is generated using linear convolutions (Octave's conv() function). This just about totally defeats the whole point behind this algorithm, i.e. to use circular convolutions (since these can be efficiently implemented using FFTs). As far as I can see, the operation b = conv(a(Xa),h) should be replaced with:

H = fft([h, zeros(1, length(Xa)-M)]);
b = ifft(H .* fft(a(Xa)));

The results from this seem more sensible to me. Could anyone confirm this?

I believe that change would work. Also, a working example can be found at Discrete_Hilbert_transforms, if that's what you are looking for. In that example, the impulse response is zero-phase, because the result is subsequently compared to a non-FIR result, which is also zero-phase. Zero-phase means that the edge-effects are at both ends, instead of just the beginning.

But the change you propose does not match the description in the article, which breaks the whole thing down into two key concepts. Fully half of the main section, and all of the math, is devoted to the concept depicted in the figure, which is that of doing piece-wise convolution and creating a seamless result. It is easier to explain that without the unnecessary complexity of circular convolution. I think this is the only place in Wikipedia where it is found. The details of circular convolution are explained in another article, which is WikiLinked here.

--Bob K (talk) 12:22, 2 April 2015 (UTC)[reply]

The figure illustrating the overlap-save algorithm is misleading/wrong

the vertical axis labels indicate that the signals have an offset. The mean value seems to be 1. However, the convolution result itself indicates that the signals have zero-mean. Most likely the vertical axis is wrongly labeled. The labels should 0,1,2 should be replaced by -1,0,1.
the double arrow below the horizontal axis is misleading. The arrows should be removed or only the one pointing to the right should be shown
the length of the segments is not clear. From the caption it seems to 100 taps, but the red portion of the upper plot indicates a different length
it is not clear which part is overlapping from the previous segment
the impulse response should also be shown

Sascha.spors (talk) 13:58, 16 January 2015 (UTC)[reply]

Plot #1 (top) is labeled "X[n], with segment k=3 in red". A similar label for plot #3 would be:

"Convolution of X₃ and a lowpass filter, with Y₃ shown in red. The non-red portions are the filter's discarded transient responses. Note that the rise-time response for Y₁ (in plot #4) was not discarded, meaning that the filter is causal."

That's a bit long for a label... perhaps you would like to add it to the caption.

The vertical axes are all labeled correctly. I think that will be obvious to you, once you understand the rise and fall times.

The traditional algorithm name (Overlap-save) is not helpful. Overlap-discard would be more helpful. But we can't re-write history.

--Bob K (talk) 15:37, 16 January 2015 (UTC)[reply]

Thanks. That makes things much clearer to me und the labels are indeed correct.

Do you know what overlap was used for the computation? How long was the impulse response of the lowpass? This information put into the caption would be helpful to understand the process better.

Sascha.spors (talk) 16:22, 16 January 2015 (UTC)[reply]

The filter is a 16-sample boxcar. So the overlap is 15.

The script is available for inspection here: https://commons.wikimedia.org/wiki/File:Overlap-save_algorithm.png

--Bob K (talk) 16:39, 16 January 2015 (UTC)[reply]

I have added the information to the figure caption and removed the dubious. Hope this helps others to understand the illustration better.

Sascha.spors (talk) 17:11, 16 January 2015 (UTC)[reply]

incorrect pseudocode change

The following was recently added to the pseudocode example:

(need to add M zeros to the beginning of the signal to simulate 1st buffer filling from M to N, otherwise result is not equal to filter(x,h))
x = concatenate(zeros(1,M), x)

The idea is to preserve the "start-up" transient (filter rise-time) produced by a function "filter(x,h)", which apparently prepends zeros and performs non-circular convolution. But with circular convolution, the first output value is a weighted average of the last M-1 samples of the input segment (and the first sample of the segment). The next M-2 outputs are weighted averages of both the beginning and the end of the segment. Prepending M zeros changes that statement to "The next M-2 outputs are weighted averages of a decreasing number of samples from the end of the segment." So it's the filter turn-off transient. Then the next M-1 outputs are the start-up transient that one would see from "filter(x,h)".

--Bob K (talk) 15:29, 30 April 2017 (UTC)[reply]