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.
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 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.
I have swept almost the entire TH-cam 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.
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)?
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.
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
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?
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
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?
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.
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..._
skill issue
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 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.
Finally... One of the hundreds who showed what should I do with the output of FFT. Till now this was implicit.
This is the best explanation of FFT on youtube. Thank you.
CAN YOU EXPLAIN IT?
I have swept almost the entire TH-cam 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.
Thanks i literally transcribed the entire video into notes, very helpful
@7:20 the phase-shift (exponential) index shall be doubled for F_2^o, and quadrupled for F_3^o.
Quite good presentation. Clear Explanation.
Just mention that 5:56 the 4th summation should use x3 rather than x4. (x0 x2 x1 x3)
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😅
did you?
This is by far the best explanation of the FFT I had ever seen.
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)?
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
I've been trying to understand this algorithm for a long time, and this video made it click!
a lot better than many other videos out there.
very nice and straight forward explanation
You have great videos. You should continue making videos!!! Thank youu!
wow, dude you just solve my problem.
i'm literally looking for this for 3days and i found the answer at minute 21
at 6:11, since it is not ordered as 0+0+1+(-1), the split of F_even and F_odd group is wrong
It is one of the best. Why do you stop your work? What can you say about Z transform?
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
I think some missing in 5:57 x4 should be the x3.
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
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.
I finally understood FFT
Awesome - great job describing this!
at 6:56, the coefficient of x_2 should be -1 instead of 1. So F_1 = -j
Really helps for a newbie of fourier Transform.
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?
O my god, you are brilliant!
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
your videos are beautiful! thank you so much!
Hey buddy great video, what program did you use to make the vid?
Thanks, Nice explanation!
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
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.
Remember guys, FFT's > NFT's
Why the first value after applying FFT on a one-dimensional array is always the greatest value?
谢谢老哥，讲的太清楚了
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
WHICH IS THE ORIGINAL SEQUENCE?
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.
🤗🤗 very easy to follow
while i calculating like normal DFT why do i get F1 = 0+0j not -2j?
Best video on FFT
Thank you for the video, it is very helpful. Can you make a video about inverse FFT?
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? :)
you are the best, I do not understand nothing, but I pretty sure taht you're a fucking genious. God bless you
Thank you so much!
Wonderful
Can someone show me how he split them in two with more detail
Legend.
Thank you, 100/100
Thanks!
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
Thanks
Example of SVGs path drawing using Fourier Transform : othmanelhoufi.github.io/fourier
thank you .
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
Gonna watch 30 more times then hopefully I will get it lol
F3 should have been F3 = j (-2j )= 2
No sound
thanx aloooooooooooooooot..
God bless you
Cool
Miller Ronald Williams Barbara Lopez Patricia
good ideo
Lewis Susan Thompson Charles Robinson Jason
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