Applied DSP No. 8: Filtering via Fast Fourier Transform

Applied Digital Signal Processing at Drexel University: In this video, we look at implementing efficient FIR filtering (convolution) via the Fast Fourier Transform (FFT).

I'm teaching the course again this Fall (September 2022), so I *really* will be posting more in this series in the coming weeks. Now would be a great time to subscribe to my channel, @Youngmoo Kim , for updates. Please leave feedback in the comments and let me know if there are DSP topics you'd like to see in future videos!

==
Music credits:
Background music by the PolyPhase generative sequencer iPad app.

[theDemongd]

These videos are really stellar, please keep it up. I learned all the mathematical underpinnings of this stuff in my physics degree but this summary is just what I needed to wrap my head around the practical aspects to do some low level audio programming. Thanks!

[Tarnith]

Thanks for making these videos! Excellent presentation, this makes a great DSP study aid.

[gadirom]

Some of the best videos on dsp I've ever seen!

[georgephillips]

This channel is amazing... honestly lost for words. This could easily complete with 3b1b.

[arianamzp]

great high quality content! learned a lot. keep it up.

[nihar]

Thank you so much for these video. Please continue with the series (fast😅)

[lutzmmobil]

I love these videos, they're super helpful in preparing for my Technical Computing exam (well it's tomorrow now but I've been preparing for longer obviously)!

[standardengineer]

Great video! I wish the overlap-save method was also shown as your animations really bring the DSP steps to life!

[mattrobinson]

Absolutely brilliant explanation. Thank you.

[noharahien]

5:25 Could you please explain how does this phenomenon relate to the concept "aliasing" more?
From what I've seen, the overlapping isn't a result of lack of resolution in freq domain, because if you do not do zero-padding, but only increase the fft size so that more samples are being taken each time to do the fft, you get the fft result in a doubled resolution, but you're not solving the time domain overlapping at all. It's still overlapping in the size of the convolution window.
Generally very good content, thank you so much for all these videos!!

[Banzay]

Your intro are so cool, love it, and the content is excellent! Do you use any music software for your intro?

[dranoel]

Thank you for these awesome videos! :)

Also I can't keep myself from pointing out (which probably nobody has every done^^) that you first name might be condensed to "calf" :P

[goofi]

Can you do a video on frequency/phase recovery? I love your videos!

[ytubeleo]

Big O notation describes what happens at the limit but doesn't take into account the complexity of the operations involved in each step. Presumably convolution starts out being far, far easier than FFT. For example, I would imagine that the given example of a 257 sample long moving average convolved is much easier computationally than taking the FFT. For a signal of 1, 024 convolved with a filter of length 257, that's 263 thousand integer multiply-and-acccumulate operations and 1024 division operations, plus the bit of extra signal at the end, I guess. But my guess is that the 31, 744 "Fourier operations" (and more with zero-passing) are going to be way more complicated than simple MAC operations and one division for each sample, or am I wrong about that?

Can you give some indication of roughly when it makes sense to switch to using FFT instead of convolution?

Actually, in the context of a moving average filter, I don't think it's ever going to make sense, since the big O notation for a moving average filter is actually O(N), so it's never going to be better to use FFT. Or am I totally misunderstanding something here? Thanks.