FFT Example: Unraveling the Recursion
81,299
Published 2020-11-15
We break down how the FFT evaluates a particular polynomial at the roots of unity by unraveling the recursive process completely.
0:00 Introduction
1:13 FFT Example Breakdown
Support: www.patreon.com/reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
All music by Aakash Gandhi
All Comments (21)
-
Why doesnt this channel have the recommendation it deserves. Its by far the best CS edutainment channel I have discovered yet.
-
Finally I have found an explanation that makes sense. Many thanks!
-
I remember studying the FFT in college (some 50 years ago) and I used it throughout my career. I’m now retired, but I still love to watch videos on Maths. Yours are particularly clear; in fact, they are works of art. Excellent!
-
This series alone earned you my subscription. It ain't much, but it's something. Thank you for the explanations.
-
Thankyou so much for this very intuitive breakdown of fft ! Commenting so that ,this series will get the views it deserves.
-
What a lovely set of videos! it helped me refresh my memories from Signal Processing classes. Would have loved to see some butterfly diagrams though, they are very beautiful to look at and quite useful to visually understand the process.
-
Man... learning computer science with 3b1b style. Insta sub
-
thanks for this example, I wouldn't have understood the FFT without it
-
I love your channel! I run my high school computer club and your videos are an invaluable resource for both learning and teaching!
-
Your channel is awesome, I'm looking forward to seeing the next video!
-
Please continue making these videos they are so helpful
-
you always make me cry, be its tower of hanoi, recursion in number of colour, now fast fourier. Thanks a lot for being so supportive
-
I have been mulling over the FFT for WEEKS. Finally I have understood it, just by seeing that for 4 elements, the number of multiplications we did was 2*2+4 = 8 = 4 log2(4), compared to 4^2 = 16 for the DFT. For 8, it would be 4*2+2*4+8 = 24 = 8log2(8), compared to 8^2 = 16. I have an exam on this this Monday, so thanks to you if i ace the FFT question!
-
Why does this channel only have 20k subscribers?? Great content.
-
i remember how i fought my way through this algorithm :D very good video!
-
simply outstanding... respect
-
mmmmmmmm , a master piece of art , thnx dude...
-
I'd like to add a very interesting point. While working with discrete signals, it common to use Z- transform. It leads a vector to a polynom in the variable z. The interesting point is that a polynomial multiplication is the convolution of its coefficients. The discrete convolution can be performed with a "smart" internal product. "Smart" because of size of results, where the product starts and finishes for each and a back to front flip. I'd be glad with a Z transform video. :)
-
This is awesome!!
-
We needs more videos about Wavelets!
