Fast Convolution: FFT-based, Overlap-Add, Overlap-Save, Partitioned [DSP #09]

✅ Check out the related article on TheWolfSound.com: www.thewolfsound.com/fast-con...
✅ Sign up for WolfSound's newsletter: thewolfsound.com/newsletter/
✅ Please subscribe to WolfSound to let the little Wolf 🐺 grow:
/ @wolfsoundaudio
In this video, we are presenting the fast convolution algorithms: FFT-based convolution, Overlap-Add convolution scheme, Overlap-Save convolution scheme, and partitioned convolution.
An amazing source about fast convolution techniques is [1]. I highly encourage you to check it out especially if you would like to read more on the topic.
[1] Frank Wefers "Partitioned convolution algorithms for real-time auralization", PhD Thesis, Zugl.: Aachen, Techn. Hochsch., 2015.
In case of any doubt in understanding, please, refer to the article above 🙂
00:00 Introduction
00:40 Linear convolution time complexity
00:59 Circular convolution time complexity
01:29 Convolution property of the DFT
01:54 FFT-based fast convolution
03:25 Block-based convolution
03:57 Overlap-Add fast convolution
05:25 Overlap-Save fast convolution
06:22 Partitioned convolution
07:19 Summary
#dsp #convolution

[@WolfSoundAudio]

Have I helped you with this video? If yes, please, consider buying me a ☕ coffee at www.buymeacoffee.com/janwilczek
Thanks! 🙂

[@stefanhopman9176]

Thank you for the great video!

[@WolfSoundAudio]

Thanks for the feedback!

[@sorrefly]

You're amazing, thank you :)

[@WolfSoundAudio]

Thank you for the feedback: I hope you found the video helpful :)

[@yumnanassif]

❤❤

[@happyTonakai]

Nice video, thumb up. Still not very clear about partitioned convolution after reading the thesis of Wefer, especially the implementation non-uniform partitioned convolution. Since you said that it's the state-of-the-art algorithm to perform a artificial reverberation, could you make another video to explain it in detail? Thx!

[@WolfSoundAudio]

Hi Zerui, thanks for the comment! If you want to discuss that topic, maybe we could get in contact? You can reach out to me via janwilczek.com/contact/, for example.

[@AbhayaParthy]

This was excellent. Thanks! Can you make a video and blog post on partitioned convolution please?

[@WolfSoundAudio]

Thanks, I am happy to hear that!
Oh, that's really difficult to say... It is possible in the future, but probably not this year.

[@przekladanki]

Cool thumbnail!

[@WolfSoundAudio]

Thank you! :)

[@MyronJeffrey]

Great Video and thanks!
I've read a Paper, where a "windowed Overlap-Add" is used to get data blocks of a PPG time signal. On each of these blocks they used an ICA-Algorithm. At the end they reconstruct these blocks by "overlap-add synthesis".
I know what the window method of FIR filters is but in the paper, they didnt spoke about a filter. They just said, "a bartlett window is used". That confuses me, because i dont rly understand what the filter is. Is h(n) the bartlett window funtion, so they just convolve the window funktion with these data block? Actually these windows are multiplicated with a filter like: h(n)_window = h(n) * bartlett(n) and then you convolve h(n)_window with these data blocks. Does it makes sense, if you just convolve each data block with an bartlett window?
Thanks again, for your great video and your article!

[@WolfSoundAudio]

Overlap-add in this sense (probably) means something different. In this context, it sounds as if they had small portions of the signal ("windowed" signal) that are at the end simply added together with some offset.
You can find something similar in time-scale modification. If you window a signal and then add the windowed parts "closer-together" you will receive a shorter signal but with the same pitch. Check here: www.mdpi.com/2076-3417/6/2/57
In sound synthesis, this is called granular synthesis.
"Does it makes sense, if you just convolve each data block with an bartlett window?" -> yes, you make the data block smooth in time then.
I hope that helps!

[@raksipulikka]

Hey, question about the diagram regarding non-uniformly partitioned convolution shown at 6:42. Why is the final delay 1024 instead of 512, is it a typo? I believe I've read the relevant parts of the thesis but can't find an explanation.