1
$\begingroup$

Edited for conciseness, please see below:

Question: How does overlap and save work, in the context of array buffers? How does overlap and add work? For a specific use case involving STFT, which one is better? Does either return more correct results? My attempts to read about it generally lead to confusion. I cannot read the formulas, and all of the graphical depictions were apparently intended for DFT transforms, such as for FIR filtering, where 1d OLA is used.

Inline is a function which consists of some modified excerpts from the ssqueezepy inverse short time Fourier transform function along with various helper functions, inlined into one object, adding overlap and add(as modified from pyroomacoustics stft class). This function should not be used by programmers as an example which is generally applicable to the diversity of use case scenarios where STFT objects can be used, for which there are a plethora of libraries, including ssqueezepy, librosa, scipy, and pyroomacoustics, but in a specific use case where the function needs to be invoked from numba for audio DSP, it works well. The fixed window, known FFT size, sample count and with other constraints fixed such as [https://dsp.stackexchange.com/a/72590/50076](modulated centering) allow it to perform well, however, it's not really clear how overlap and add work.

@numba.jit(numba.types.Tuple((numba.float64[:],numba.float64[:]))(numba.complex128[:,:],numba.float64[:]))
def istft(Sx: numpy.ndarray,persistent_buffer:numpy.ndarray):

    n_fft = 512
    win_len = 512
    N = 8192
    hop_len = 128

    window  = numpy.asarray([0.00000000e+00,2.52493737e-05,1.00993617e-04,2.27221124e-04,4.03912573e-04,6.31040943e-04,9.08571512e-04,1.23646188e-03,1.61466197e-03,2.04311406e-03,2.52175277e-03,3.05050510e-03,3.62929044e-03,4.25802059e-03,4.93659976e-03,5.66492464e-03,6.44288435e-03,7.27036053e-03,8.14722732e-03,9.07335139e-03,1.00485920e-02,1.10728009e-02,1.21458227e-02,1.32674943e-02,1.44376456e-02,1.56560990e-02,1.69226697e-02,1.82371657e-02,1.95993878e-02,2.10091294e-02,2.24661772e-02,2.39703105e-02,2.55213015e-02,2.71189155e-02,2.87629109e-02,3.04530390e-02,3.21890442e-02,3.39706641e-02,3.57976294e-02,3.76696640e-02,3.95864853e-02,4.15478036e-02,4.35533228e-02,4.56027403e-02,4.76957466e-02,4.98320260e-02,5.20112561e-02,5.42331081e-02,5.64972471e-02,5.88033315e-02,6.11510136e-02,6.35399396e-02,6.59697493e-02,6.84400765e-02,7.09505488e-02,7.35007880e-02,7.60904099e-02,7.87190242e-02,8.13862349e-02,8.40916401e-02,8.68348324e-02,8.96153985e-02,9.24329196e-02,9.52869711e-02,9.81771232e-02,1.01102941e-01,1.04063982e-01,1.07059803e-01,1.10089950e-01,1.13153968e-01,1.16251394e-01,1.19381763e-01,1.22544602e-01,1.25739435e-01,1.28965780e-01,1.32223151e-01,1.35511057e-01,1.38829001e-01,1.42176485e-01,1.45553002e-01,1.48958043e-01,1.52391095e-01,1.55851640e-01,1.59339154e-01,1.62853113e-01,1.66392985e-01,1.69958235e-01,1.73548325e-01,1.77162713e-01,1.80800852e-01,1.84462192e-01,1.88146180e-01,1.91852259e-01,1.95579867e-01,1.99328441e-01,2.03097413e-01,2.06886212e-01,2.10694266e-01,2.14520996e-01,2.18365823e-01,2.22228164e-01,2.26107433e-01,2.30003042e-01,2.33914400e-01,2.37840913e-01,2.41781985e-01,2.45737016e-01,2.49705407e-01,2.53686555e-01,2.57679853e-01,2.61684694e-01,2.65700470e-01,2.69726568e-01,2.73762377e-01,2.77807281e-01,2.81860664e-01,2.85921908e-01,2.89990394e-01,2.94065503e-01,2.98146611e-01,3.02233096e-01,3.06324335e-01,3.10419702e-01,3.14518572e-01,3.18620319e-01,3.22724316e-01,3.26829934e-01,3.30936547e-01,3.35043526e-01,3.39150246e-01,3.43256086e-01,3.47360427e-01,3.51462648e-01,3.55562129e-01,3.59658251e-01,3.63750398e-01,3.67837950e-01,3.71920292e-01,3.75996808e-01,3.80066883e-01,3.84129905e-01,3.88185260e-01,3.92232339e-01,3.96270531e-01,4.00299230e-01,4.04317828e-01,4.08325721e-01,4.12322306e-01,4.16306982e-01,4.20279150e-01,4.24238213e-01,4.28183575e-01,4.32114645e-01,4.36030831e-01,4.39931546e-01,4.43816203e-01,4.47684220e-01,4.51535015e-01,4.55368011e-01,4.59182632e-01,4.62978306e-01,4.66754464e-01,4.70510539e-01,4.74245967e-01,4.77960189e-01,4.81652647e-01,4.85322788e-01,4.88970060e-01,4.92593918e-01,4.96193817e-01,4.99769218e-01,5.03319584e-01,5.06844384e-01,5.10343088e-01,5.13815172e-01,5.17260116e-01,5.20677401e-01,5.24066516e-01,5.27426952e-01,5.30758205e-01,5.34059774e-01,5.37331165e-01,5.40571886e-01,5.43781450e-01,5.46959376e-01,5.50105185e-01,5.53218405e-01,5.56298569e-01,5.59345212e-01,5.62357878e-01,5.65336111e-01,5.68279465e-01,5.71187495e-01,5.74059764e-01,5.76895840e-01,5.79695293e-01,5.82457703e-01,5.85182652e-01,5.87869728e-01,5.90518527e-01,5.93128647e-01,5.95699693e-01,5.98231278e-01,6.00723016e-01,6.03174532e-01,6.05585452e-01,6.07955411e-01,6.10284050e-01,6.12571014e-01,6.14815956e-01,6.17018534e-01,6.19178413e-01,6.21295262e-01,6.23368760e-01,6.25398589e-01,6.27384439e-01,6.29326006e-01,6.31222993e-01,6.33075109e-01,6.34882068e-01,6.36643595e-01,6.38359416e-01,6.40029269e-01,6.41652895e-01,6.43230043e-01,6.44760469e-01,6.46243937e-01,6.47680215e-01,6.49069080e-01,6.50410317e-01,6.51703715e-01,6.52949072e-01,6.54146194e-01,6.55294893e-01,6.56394987e-01,6.57446303e-01,6.58448674e-01,6.59401943e-01,6.60305956e-01,6.61160570e-01,6.61965647e-01,6.62721059e-01,6.63426683e-01,6.64082404e-01,6.64688115e-01,6.65243717e-01,6.65749117e-01,6.66204231e-01,6.66608983e-01,6.66963302e-01,6.67267128e-01,6.67520406e-01,6.67723090e-01,6.67875141e-01,6.67976529e-01,6.68027230e-01,6.68027230e-01,6.67976529e-01,6.67875141e-01,6.67723090e-01,6.67520406e-01,6.67267128e-01,6.66963302e-01,6.66608983e-01,6.66204231e-01,6.65749117e-01,6.65243717e-01,6.64688115e-01,6.64082404e-01,6.63426683e-01,6.62721059e-01,6.61965647e-01,6.61160570e-01,6.60305956e-01,6.59401943e-01,6.58448674e-01,6.57446303e-01,6.56394987e-01,6.55294893e-01,6.54146194e-01,6.52949072e-01,6.51703715e-01,6.50410317e-01,6.49069080e-01,6.47680215e-01,6.46243937e-01,6.44760469e-01,6.43230043e-01,6.41652895e-01,6.40029269e-01,6.38359416e-01,6.36643595e-01,6.34882068e-01,6.33075109e-01,6.31222993e-01,6.29326006e-01,6.27384439e-01,6.25398589e-01,6.23368760e-01,6.21295262e-01,6.19178413e-01,6.17018534e-01,6.14815956e-01,6.12571014e-01,6.10284050e-01,6.07955411e-01,6.05585452e-01,6.03174532e-01,6.00723016e-01,5.98231278e-01,5.95699693e-01,5.93128647e-01,5.90518527e-01,5.87869728e-01,5.85182652e-01,5.82457703e-01,5.79695293e-01,5.76895840e-01,5.74059764e-01,5.71187495e-01,5.68279465e-01,5.65336111e-01,5.62357878e-01,5.59345212e-01,5.56298569e-01,5.53218405e-01,5.50105185e-01,5.46959376e-01,5.43781450e-01,5.40571886e-01,5.37331165e-01,5.34059774e-01,5.30758205e-01,5.27426952e-01,5.24066516e-01,5.20677401e-01,5.17260116e-01,5.13815172e-01,5.10343088e-01,5.06844384e-01,5.03319584e-01,4.99769218e-01,4.96193817e-01,4.92593918e-01,4.88970060e-01,4.85322788e-01,4.81652647e-01,4.77960189e-01,4.74245967e-01,4.70510539e-01,4.66754464e-01,4.62978306e-01,4.59182632e-01,4.55368011e-01,4.51535015e-01,4.47684220e-01,4.43816203e-01,4.39931546e-01,4.36030831e-01,4.32114645e-01,4.28183575e-01,4.24238213e-01,4.20279150e-01,4.16306982e-01,4.12322306e-01,4.08325721e-01,4.04317828e-01,4.00299230e-01,3.96270531e-01,3.92232339e-01,3.88185260e-01,3.84129905e-01,3.80066883e-01,3.75996808e-01,3.71920292e-01,3.67837950e-01,3.63750398e-01,3.59658251e-01,3.55562129e-01,3.51462648e-01,3.47360427e-01,3.43256086e-01,3.39150246e-01,3.35043526e-01,3.30936547e-01,3.26829934e-01,3.22724316e-01,3.18620319e-01,3.14518572e-01,3.10419702e-01,3.06324335e-01,3.02233096e-01,2.98146611e-01,2.94065503e-01,2.89990394e-01,2.85921908e-01,2.81860664e-01,2.77807281e-01,2.73762377e-01,2.69726568e-01,2.65700470e-01,2.61684694e-01,2.57679853e-01,2.53686555e-01,2.49705407e-01,2.45737016e-01,2.41781985e-01,2.37840913e-01,2.33914400e-01,2.30003042e-01,2.26107433e-01,2.22228164e-01,2.18365823e-01,2.14520996e-01,2.10694266e-01,2.06886212e-01,2.03097413e-01,1.99328441e-01,1.95579867e-01,1.91852259e-01,1.88146180e-01,1.84462192e-01,1.80800852e-01,1.77162713e-01,1.73548325e-01,1.69958235e-01,1.66392985e-01,1.62853113e-01,1.59339154e-01,1.55851640e-01,1.52391095e-01,1.48958043e-01,1.45553002e-01,1.42176485e-01,1.38829001e-01,1.35511057e-01,1.32223151e-01,1.28965780e-01,1.25739435e-01,1.22544602e-01,1.19381763e-01,1.16251394e-01,1.13153968e-01,1.10089950e-01,1.07059803e-01,1.04063982e-01,1.01102941e-01,9.81771232e-02,9.52869711e-02,9.24329196e-02,8.96153985e-02,8.68348324e-02,8.40916401e-02,8.13862349e-02,7.87190242e-02,7.60904099e-02,7.35007880e-02,7.09505488e-02,6.84400765e-02,6.59697493e-02,6.35399396e-02,6.11510136e-02,5.88033315e-02,5.64972471e-02,5.42331081e-02,5.20112561e-02,4.98320260e-02,4.76957466e-02,4.56027403e-02,4.35533228e-02,4.15478036e-02,3.95864853e-02,3.76696640e-02,3.57976294e-02,3.39706641e-02,3.21890442e-02,3.04530390e-02,2.87629109e-02,2.71189155e-02,2.55213015e-02,2.39703105e-02,2.24661772e-02,2.10091294e-02,1.95993878e-02,1.82371657e-02,1.69226697e-02,1.56560990e-02,1.44376456e-02,1.32674943e-02,1.21458227e-02,1.10728009e-02,1.00485920e-02,9.07335139e-03,8.14722732e-03,7.27036053e-03,6.44288435e-03,5.66492464e-03,4.93659976e-03,4.25802059e-03,3.62929044e-03,3.05050510e-03,2.52175277e-03,2.04311406e-03,1.61466197e-03,1.23646188e-03,9.08571512e-04,6.31040943e-04,4.03912573e-04,2.27221124e-04,1.00993617e-04,2.52493737e-05,0.00000000e+00])

    with numba.objmode(xbuf ="float64[:,:]"):
      xbuf = numpy.fft.irfft(Sx, n=n_fft, axis=0).real
      xbuf = numpy.fft.fftshift(xbuf, axes=0) 

    x = np.zeros(8192, dtype=numpy.float64) 

            # treat number of frames as the multiple channels for DFT
            # back to time domain
    n = 0
    for i in range(xbuf.shape[1]):
        processing = xbuf[:, i] * window
        out = processing[0 : hop_len]  # fresh output samples
        out[:128] += persistent_buffer[:128]
        # update state variables
        persistent_buffer[: -hop_len] = persistent_buffer[hop_len:]  # shift out left
        persistent_buffer[-hop_len :] = 0.0
        persistent_buffer[:] += processing[-384:] #n_FFT - hop_length
        x[n : n + hop_len] = out[:]
        n += hop_len
    return x, persistent_buffer

For completeness, the stft class that accompanies it is provided here:

@numba.jit(numba.complex128[:,:](numba.float64[:],numba.float64[:]))
def stft(x, window):
#note: this function should not be used as an example of how to write a stft.
#a number of explicit assumptions are made here to improve performance with assumed inputs. modifications here also allow for LLVM acceleration of other code that calls this logic.

    n_fft = 512
    win_length = 512
    hop_len = 128

    # process args
    N = 8192
    n_fft = 512

    xp = numpy.zeros(25087,dtype=numpy.float64)
    xp[256:-255]= x[:]
    xp[0:256] = xp[257:(256*2)+1][::-1]
    xp[-255:] = xp[-255*2-1:-256][::-1]

    seg_len = n_fft
    n_overlap = n_fft - hop_len
    hop_len = seg_len - n_overlap
    n_segs = (xp.shape[-1] - seg_len) // hop_len + 1
    s20 = int(numpy.ceil(seg_len / 2))
    s21 = s20 - 1 if (seg_len % 2 == 1) else s20
    Sx = numpy.zeros(((seg_len, n_segs)), dtype=numpy.float64)
    for i in range(n_segs):
        start0 = hop_len * i
        end0   = start0 + s21
        start1 = end0
        end1   = start1 + s20
        Sx[:s20, i] = xp[start1:end1]
        Sx[s20:, i] = xp[start0:end0]

    with numba.objmode(Sx ="complex128[:,:]"):
      window = numpy.fft.ifftshift(window)
      Sx *= window.reshape(-1, 1) #apply windowing
      Sx = numpy.fft.rfft(Sx, axis=0)


    return Sx

The included synthesis window is produced by

pypyroomacoustics.transform.stft.compute_synthesis_window(analysis_window, hop)

utilizing a raised cosine bell/hann window, and will optimally invert a modified hann-filtered input When this is replaced with a hann window for both, it perfectly inverts the input. D. Griffin and J. Lim, Signal estimation from modified short-time Fourier transform, IEEE Trans. Acoustics, Speech, and Signal Process., vol. 32, no. 2, pp. 236-243, 1984.


[1]: https://%20https://dsp.stackexchange.com/a/72590/50076
$\endgroup$
4
  • $\begingroup$ Welcome to DSP SE! Sorry, but your question is longish and a bit hard to read. Can you trim it down to the essential problem? Overlap-add and overlap-save are well established methods or implementing linear time-invariant filtering. Is your problem that you don't know how to implement them or that they don't do what you need them to do ? $\endgroup$
    – Hilmar
    Feb 15, 2023 at 4:48
  • $\begingroup$ I don't know how to implement them. And the descriptions of how to implement them confuse me. The only implementation I have access to uses a bunch of complicated array structures to manage and mangle data and it confuses me further. Secondly, I understand they are different, and I dont know which would be best for my use case. $\endgroup$
    – HFGCS
    Feb 15, 2023 at 5:15
  • $\begingroup$ So is there still a question? I see stuff was edited out - I suggest separating content into issue summary and supplementing details, with labeled sections, as that's more readable than a stream of paragraphs. Full code typically goes at bottom, and relevant bits pasted in body if applicable. $\endgroup$ Feb 15, 2023 at 10:43
  • 1
    $\begingroup$ @OverLordGoldDragon No, there is no longer a question. Although I am still not fully certain what it does, the measurable product is that it works correctly, and allows the modified ssqueezepy stft and istft to be invoked from a numba context. $\endgroup$
    – HFGCS
    Feb 15, 2023 at 20:51

1 Answer 1

1
$\begingroup$

Overlap add is one way of doing block convolution of data larger than the block size. Block convolution usually requires the input and output blocks to be the same size. But there is a problem. That problem is that the result of block N size of data convolved with a kernel of size M is N+M-1 in size. Too big to fit in an output the same size at the input.

What overlap add does to solve this problem is to use a buffer to store the part that doesn't fit, so that is this left over part that doesn't fit in the current result can be later added into the results of other adjacent block convolutions, either in time or space (before or after or left or right or above or below, etc., depending on where the left over parts of the convolution in the buffers belong.)

$\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.