I spent part of a semester in college learning this, back in the 1980's. It cost me ~$500 in 1985 $s. Now it's free on the Internet, and presented much more clearly. Thanks.
Its also hard to find good teachers - with things like this topic, skipping even a single step is like a broken chain, and I think a lot of professors find it hard to remember this, or simply don't care. Simon presents the most solid explanation of the FFT I have found, not missing or skipping any critical information.
This is such an amazing straightforward explanation when combined with your video on the DFT. This was impenetrable to me when I got my engineering undergraduate. I was just grateful at the time I didn't have to fully understand it to use it. I hope at some point you consider teaching undergraduates. Even if you aren't an academic some of my best classes were taught by people from industry that wanted to make sure we got something useful.
By far the best explanation of exactly how the FFT algorithm works that I have been able to find on the net. I recreated your code in c#, and compared to some common FFT libraries - got the exact same results. Great work.
I have swept almost the entire RUclips offering on FFT and I agree that this is the most accessible and concrete treatment with the best presentation. I love fresh colour-coded method of teaching. Can you say what software you used to make this? Yes at 6:42 it is a tiny error in the 2nd term of F1 but it multiplies by zero and doesn't change the final answer. So the F1 equation should be: F1 = 0 + -1(0) + (-j)[1+(-1)(-1)] = -2j I believe the rest of the video is error-free. Great work! For an even better understanding I encourage viewers to split the summations one more time to have 8 summations, remembering that exp(x)*exp(y) = exp(x+y), and then it really becomes obvious how elegant Simon Xu's way of organizing terms really is. Then the pattern becomes obvious and you could technically split as many times as you want, confidently, to have 16 terms or 32 terms without having to do all the math but instead by following the pattern. Simon, "I'll be watching your career with much interest young man".... quote from Senator Palpatine :)
I first used FFT as a R&D engineer in 1979. It took a microprocessor and a load of custom electronics. Recently did it on an Arduino. Awesome progress.
Instructors who may be reading: I absolutely hate it when you skip steps and make mistakes when I, the student, am trying to learn from following your "easy" explanation, step-by-step. It irks me so. You don't impress me; rather, you just frustrate and piss me, the student, off. I shouldn't have to find your mistakes; it's not my job to find your mistakes while twisting my brain in knots which shouldn't exist. You shouldn't be making mistakes. If you're making mistakes, then don't, in all your "brilliance," skip steps. (...seems a no-brainer to me.) But what's nice is I can finally say this to an instructor after so many years and not interrupt class to do it. :-)
And if you make mistakes intentionally, just to see if I'm following you, and I learn this, then you really piss me off. (...assuming it matters.) Educational costs are high, and students can't afford to have instructors who make mistakes because they want to appear brilliant and skip steps.
Sorry all, I just noticed all the comments in my email when I checked this account today.. Based upon your comments I think I probably have several errors in my video. Hopefully I can create a new video that fixes all these errors in the future. I created this video as a resume filler when I was job hunting, had no idea it would be viewed so many times.
Yes your video is realy great, I watched tens of similar, but only your helped me to understand, especially DFT video, because here the true is that there are a lot of mistakes that made me crazy, I but after watch it ten times I catch the errors and I think I got the idea of FFT. But still I have some question like: 1) Shoul we always devide our array until we get sums of one sample ("m" goes from 0 to 0)? I wonder because there is Nyquest (??? somebody like that) idea that there should be sampling rate 2x highest frequency we want to measure. I think I understand that Nyquest idea, but I'm not how it corresponds with deviding array to just one sample? I think it would be great if you make video FFT with 8 sample rate example like in DFT video, 8 sample rate would make it much more clear I think 2) "Windowing" - it's not about this videao exactly but it's about FFT also. I understand exactly what "windowing" makes, but I have big problem to understand how to make Inversion FFT from that windowed FFT transfered data. When I try to plot inverted data I recive some strange results. Maybe you could also create video about that case? Again thanks for that videos and thanks in advance for any new if you create.
Hi, I'm writing a paper on the Fourier Transform, and one of the sections focuses on the FFT. One part of this video, however, confuses me. At 6:04, you establish that F0 = x0+x2+x1+x3 = 0 + 1 + 0 + -1. It appears that you've rearranged the x values in between the second and third parts of this equation, going from x0+x2+x1+x3 to x0+x1+x2+x3 (I'm assuming that x0=0, x1=1, x2=0, and x3=-1). Using the first ordering, it seems that Fe0 should equal 0 + 0 (x0+x2) and Fo0 should equal 1 + -1 (x1 + x3). This affects the even and odd sums, thereby affecting the results of F3 and F4. Am I missing a step here? Do Fe0 really equal x0+x1 (1) and Fo0 really equal x2+x3 (0 + -1)?
The statement "If we add a multiple of 2pi to the operand of cos (3:54) you end up with simply the 2pi functions with the 2pi multiple." Please elaborate. How can it be canceled? Apology if I sounded stupid but I just couldn't figure out how it gets removed. Maybe because it's a neglible value?. I don't know
There Is an error computing F1: the second term of the sum should be -1(0). It does not affect the final value because this product is 0, but for the sake of correctnes
Hello how x2 = 1, if you take 4 samples, x0=0, x1=1, x2=0 and x3 = -1, isn't it...at 6: 09 u splited even n odds but u considered x0 n x1 as odd. N other as even.. How? Plz correct me n guide
Good catch you found an error there. F(0)_even = 0, F(1)_even = 0; F(0)_odd = 0, F(1) _odd= 2. Note even is always zero because of the sample. The -1 Sample flips sign on F(1) because of green 4*pi term. Note to leave out the 2*pi term on f(1)_odd when calculating the odd_sum.
Damn everything looks so fine unless you go into details :( Not even sure are they really mistakes or do I make mistakes myself. For example how e(-j4pk/N) = 1 in one case and it equals -1 in the other, when k=1 and N=4. Doesn't it make cos(p)-jsin(p) = -1 in both cases?
Such a wonderful video! Could you explain the part @ 5:58 , F0 = 0 + 1 + 0 - 1. All exponents = 1, how is X3 = -1. How is X0 and X3 = 0? If X0 is 0, why is X2 not = 0. Thanks alot in advance
Hi, ignore my question, of course I understand now that you are simply applying the coefficients of 0, pi/4,pi/2 and pi of the first term. But therefore referring to 5:51, the content should be X0 = 0, X2 = 0.707, X1 = 0, X3 = -1?
I was about to thank you for using C++, then you had to go and mention python! WHY WOULD YOU USE A SUPER SLOW VIRTUAL LANGUAGE FOR AN ALGORITHM THAT IS SUPPOSED TO BE FAST!
I spent part of a semester in college learning this, back in the 1980's. It cost me ~$500 in 1985 $s. Now it's free on the Internet, and presented much more clearly.
Thanks.
you should see what it cost today in college.....
Its also hard to find good teachers - with things like this topic, skipping even a single step is like a broken chain, and I think a lot of professors find it hard to remember this, or simply don't care. Simon presents the most solid explanation of the FFT I have found, not missing or skipping any critical information.
welcome to the _future..._
This is such an amazing straightforward explanation when combined with your video on the DFT. This was impenetrable to me when I got my engineering undergraduate. I was just grateful at the time I didn't have to fully understand it to use it.
I hope at some point you consider teaching undergraduates. Even if you aren't an academic some of my best classes were taught by people from industry that wanted to make sure we got something useful.
By far the best explanation of exactly how the FFT algorithm works that I have been able to find on the net. I recreated your code in c#, and compared to some common FFT libraries - got the exact same results. Great work.
This is by far the best explanation of the FFT I had ever seen.
This is the greatest explanation of FFT ever! I hope that my knowledge and skills will allow me to pass my image processing test tomorrow😅
I have swept almost the entire RUclips offering on FFT and I agree that this is the most accessible and concrete treatment with the best presentation. I love fresh colour-coded method of teaching. Can you say what software you used to make this?
Yes at 6:42 it is a tiny error in the 2nd term of F1 but it multiplies by zero and doesn't change
the final answer. So the F1 equation should be:
F1 = 0 + -1(0) + (-j)[1+(-1)(-1)] = -2j
I believe the rest of the video is error-free. Great work! For an even better understanding I encourage viewers to split the summations one more time to have 8 summations, remembering that exp(x)*exp(y) = exp(x+y), and then it really becomes obvious how elegant Simon Xu's way of organizing terms really is. Then the pattern becomes obvious and you could technically split as many times as you want, confidently, to have 16 terms or 32 terms without having to do all the math but instead by following the pattern.
Simon, "I'll be watching your career with much interest young man".... quote from Senator Palpatine :)
This is the best explanation of FFT on youtube. Thank you.
CAN YOU EXPLAIN IT?
I've been trying to understand this algorithm for a long time, and this video made it click!
Thanks i literally transcribed the entire video into notes, very helpful
Finally... One of the hundreds who showed what should I do with the output of FFT. Till now this was implicit.
I first used FFT as a R&D engineer in 1979. It took a microprocessor and a load of custom electronics. Recently did it on an Arduino. Awesome progress.
a lot better than many other videos out there.
Quite good presentation. Clear Explanation.
Just mention that 5:56 the 4th summation should use x3 rather than x4. (x0 x2 x1 x3)
Instructors who may be reading: I absolutely hate it when you skip steps and make mistakes when I, the student, am trying to learn from following your "easy" explanation, step-by-step. It irks me so. You don't impress me; rather, you just frustrate and piss me, the student, off. I shouldn't have to find your mistakes; it's not my job to find your mistakes while twisting my brain in knots which shouldn't exist. You shouldn't be making mistakes. If you're making mistakes, then don't, in all your "brilliance," skip steps. (...seems a no-brainer to me.) But what's nice is I can finally say this to an instructor after so many years and not interrupt class to do it. :-)
And if you make mistakes intentionally, just to see if I'm following you, and I learn this, then you really piss me off. (...assuming it matters.) Educational costs are high, and students can't afford to have instructors who make mistakes because they want to appear brilliant and skip steps.
Awesome - great job describing this!
You have great videos. You should continue making videos!!! Thank youu!
very nice and straight forward explanation
your videos are beautiful! thank you so much!
Really helps for a newbie of fourier Transform.
Thanks, Nice explanation!
wow, dude you just solve my problem.
i'm literally looking for this for 3days and i found the answer at minute 21
O my god, you are brilliant!
@7:20 the phase-shift (exponential) index shall be doubled for F_2^o, and quadrupled for F_3^o.
Best video on FFT
Sorry all, I just noticed all the comments in my email when I checked this account today.. Based upon your comments I think I probably have several errors in my video. Hopefully I can create a new video that fixes all these errors in the future. I created this video as a resume filler when I was job hunting, had no idea it would be viewed so many times.
Yes your video is realy great, I watched tens of similar, but only your helped me to understand, especially DFT video, because here the true is that there are a lot of mistakes that made me crazy, I but after watch it ten times I catch the errors and I think I got the idea of FFT. But still I have some question like:
1) Shoul we always devide our array until we get sums of one sample ("m" goes from 0 to 0)? I wonder because there is Nyquest (??? somebody like that) idea that there should be sampling rate 2x highest frequency we want to measure. I think I understand that Nyquest idea, but I'm not how it corresponds with deviding array to just one sample? I think it would be great if you make video FFT with 8 sample rate example like in DFT video, 8 sample rate would make it much more clear I think
2) "Windowing" - it's not about this videao exactly but it's about FFT also. I understand exactly what "windowing" makes, but I have big problem to understand how to make Inversion FFT from that windowed FFT transfered data. When I try to plot inverted data I recive some strange results. Maybe you could also create video about that case?
Again thanks for that videos and thanks in advance for any new if you create.
apparently it never happens
Thank you so much!
Thank you for the video, it is very helpful. Can you make a video about inverse FFT?
I finally understood FFT
Hi,
I'm writing a paper on the Fourier Transform, and one of the sections focuses on the FFT. One part of this video, however, confuses me. At 6:04, you establish that F0 = x0+x2+x1+x3 = 0 + 1 + 0 + -1. It appears that you've rearranged the x values in between the second and third parts of this equation, going from x0+x2+x1+x3 to x0+x1+x2+x3 (I'm assuming that x0=0, x1=1, x2=0, and x3=-1). Using the first ordering, it seems that Fe0 should equal 0 + 0 (x0+x2) and Fo0 should equal 1 + -1 (x1 + x3). This affects the even and odd sums, thereby affecting the results of F3 and F4. Am I missing a step here? Do Fe0 really equal x0+x1 (1) and Fo0 really equal x2+x3 (0 + -1)?
thank you. I've been trying to learn FFT . your video is very helpful!
What is the use and application of FFT?
Could you reply me please
@@KarthikReddy-tkr tings
It is one of the best. Why do you stop your work? What can you say about Z transform?
谢谢老哥，讲的太清楚了
Thank you, 100/100
🤗🤗 very easy to follow
Wonderful
Thanks!
thank you .
Legend.
at 6:11, since it is not ordered as 0+0+1+(-1), the split of F_even and F_odd group is wrong
Hey buddy great video, what program did you use to make the vid?
Thanks
at 6:56, the coefficient of x_2 should be -1 instead of 1. So F_1 = -j
Quick question, in the video the index k and n are going from 0 to # of samples. Should it be going from 0 to number of samples minus 1?
+Prisma Dynamics LLC Yes you are correct, sorry for the mistake
while i calculating like normal DFT why do i get F1 = 0+0j not -2j?
thanx aloooooooooooooooot..
Can someone show me how he split them in two with more detail
Why the first value after applying FFT on a one-dimensional array is always the greatest value?
The statement "If we add a multiple of 2pi to the operand of cos (3:54) you end up with simply the 2pi functions with the 2pi multiple." Please elaborate. How can it be canceled? Apology if I sounded stupid but I just couldn't figure out how it gets removed. Maybe because it's a neglible value?. I don't know
The cosine wave is periodic, repeating every 2pi. So adding a 2pi value simply obtains the same result as before adding 2pi.
There Is an error computing F1: the second term of the sum should be -1(0). It does not affect the final value because this product is 0, but for the sake of correctnes
I think some missing in 5:57 x4 should be the x3.
in 6:42 I get -1 no 1 as you show in the video why?
N=4, K=1, so e^(-j4pik/N) = 1? I get -1
yes, you are right, its -1, it didnt affect the result because it was multiplied by 0 but nice find
if you have the c++ code, is it possible that you would put it up in the description or something so it's possible to download? :)
Cool
you are the best, I do not understand nothing, but I pretty sure taht you're a fucking genious. God bless you
Hello how x2 = 1, if you take 4 samples, x0=0, x1=1, x2=0 and x3 = -1, isn't it...at 6: 09 u splited even n odds but u considered x0 n x1 as odd. N other as even.. How? Plz correct me n guide
Good catch you found an error there. F(0)_even = 0, F(1)_even = 0; F(0)_odd = 0, F(1) _odd= 2. Note even is always zero because of the sample. The -1 Sample flips sign on F(1) because of green 4*pi term. Note to leave out the 2*pi term on f(1)_odd when calculating the odd_sum.
good ideo
Damn everything looks so fine unless you go into details :( Not even sure are they really mistakes or do I make mistakes myself. For example how e(-j4pk/N) = 1 in one case and it equals -1 in the other, when k=1 and N=4. Doesn't it make cos(p)-jsin(p) = -1 in both cases?
I saw that too, I think it should be -1.
What's the use and application of FFT?
Such a wonderful video! Could you explain the part @ 5:58 , F0 = 0 + 1 + 0 - 1. All exponents = 1, how is X3 = -1. How is X0 and X3 = 0? If X0 is 0, why is X2 not = 0. Thanks alot in advance
Hi, ignore my question, of course I understand now that you are simply applying the coefficients of 0, pi/4,pi/2 and pi of the first term. But therefore referring to 5:51, the content should be X0 = 0, X2 = 0.707, X1 = 0, X3 = -1?
@@alfietankokleong they are just the data samples which are taken from the sine wave. watch again by starting at 5:00
Another Quick question, in the video 20000*log2 20000 = 285754 operations, it's not 28600?
rounded to 28600
@@skywaysecurities Yes but rounded is 286000 not 28600 because log2(20000) ~ 14 not 1.4
Thanks, I was confused about it, hope OP can correct it.
Gonna watch 30 more times then hopefully I will get it lol
God bless you
WHICH IS THE ORIGINAL SEQUENCE?
No sound
Example of SVGs path drawing using Fourier Transform : othmanelhoufi.github.io/fourier
what do you mean by "bin"?
a repository. A place where you put all the results from the different frequencies.
#unibrow ;D
@@sticky4loop227 bin laden
Remember guys, FFT's > NFT's
F3 should have been F3 = j (-2j )= 2
Really wish you'd have raised the volume to where we could hear it. No. P.S. NOT LOUD ENOUGH!!! P.P.S. Can't hear it!!!
I really wish you got yourself an external dac/amp SO YOU COULD JUST TURN IT UP lmao
@@AccuphaseMan he need hearing aid lol
Broski can't even hear the captions
this is no so simple :(
¿???¿??????????????????
P,ease explain something WHAT ARE YOU DOING???????
I was about to thank you for using C++, then you had to go and mention python! WHY WOULD YOU USE A SUPER SLOW VIRTUAL LANGUAGE FOR AN ALGORITHM THAT IS SUPPOSED TO BE FAST!
UI Spoof