Yes, good catch. x[8] should not be on slide 4 at 10:04, but it should be x[0] x[2] x[4] x[6] as Colo Ricatti pointed out. Somehow I skipped x[4] when counting.
Best clear cut explanation , this video helps to jump from FT to FFT and understand the computational efficiency. Come with some prep study of FT and do an actual calculation in excel then come here and you are done!
no, at 11:10 it is just splitting even and odd index terms (splitting N = 8 DFT into 2 DFTs of N = 4). The full bit reversal (x(0) x(4) x(2) x(6) ) occurs after three stages of splitting - see 15:08
@@CanaDan One tricky bit I’ve learned recently. You will want to skew the visualization horizontally towards the right. For audio, the FFT contains a ton of detailed high frequency information so if you just visualize the FFT as is, it is hard to see the bass/miss areas. You want to skew the visualization to emphasize the bass and mid regions for regular viewing as you might see in a spectrum analyzer in your DAW
At 9:33 you say "x sub zero" and I found that a bit confusing later in the video, when I forgot where it's came for, but now I have realized that it's more like "x sub oh". :) Thanks for the great video! It really helped me!
frankly, i didn't get this 8:09 - N > n, k isn't great value too because of Nyquist limit (actually, k sample rate, the're no any sense in such calculations - it computes damn lot of ghost frequencies, because it increases sample rate.
9:05 I don't think the sum for even terms Σ(r=0 to (N/2)-1) x[2r] * (w_N/2)^kr is the DFT for N/2 samples since it should evaluate both the function x and the complex exponential at 2r instead of x at 2r and the exponential at r to be the DFT, and same for the sum for odd terms. This comment is supposed to be a question ...
This is a good overview of FFT. It would be nice to explain how the DFT convolution sum is derived. Also, the de-interlacing of the inputs was glossed over (not explained clearly) but only the reversed binary notation was mentioned (this is just an after-the-fact observation of How, not an explanation of Why). Readers who dive deeper into the splitting of a larger N-point FFT into two smaller N/2-point FFT’s, or understand the relationships between the twiddle factors (and their periodic nature) would understand and retain better the FFT technique (and be able to conquer any arbitrary size of N-point FFT (N being a power of 2, of course).
How would the butterfly diagram (@ 15:06) change if there were numerous iterations of inputs? For example if N=128 but the 8 channels structure is maintained? Thanks
I highly suggest going back to second-year advanced calculus textbooks. There're many well-rounded explanations of FFT rather than what we have in DSP textbooks.
To calculate the cost in the 13:42. It should be 2(N/2)^2+N/2, the next steps will be similar. So the final cost will be 3/2N+1/2N logN. It is because that the w of the lower half are simply negative of those of the upper half. So the cost should not be counted. Of course under big O notation, the final answer is still O(NlogN). You are really helpful, but there are some minor mistakes.
Yes. There is an annotation at 10:07 that points out the problem, but that may not be visible on your device. I have also uploaded a corrected version of this video to my channel, called The Fast Fourier Transform (FFT) Algorithm (c)
You missed one of the main parts: How to compute X[k+N/2]. So you only take k from 0 to N/2. Based on this, you didn't prove that the asymptotics is 2*(N/2)^2.
X[k] = Xe[k] + Wn,k*Xo[k]. Index for X runs from 0 - 7, but that of Xe and Xo runs from 0 - 3. Please reply how to deal with X's when the index runs above 3. (I'm assuming N=8)
The complexity calculation for the FFT as you explained in the video is incorrect. 2 summations of half size of the array will be N(N/2 • 2), which is N^2. The benefit of FFT is from the fact that W_N^rk = -W_N^r(k-N) when k ≥ N. This is due to the symmetric property of the exponential function: e^j2π = -e^jπ Now you only have to compute the FT for half the array and the other half can be constructed by negating those terms, so you end up with complexity N(N/2) for the first split.
I don't know if you ever check comments for this particulair video since it's been a while since you've uploaded it, but I have a question: how do you get O(((N^2)/2)+N)? I know you explained it in the video (at around 12:00), but I don't understand it. Thanks in advance!
where can i learn more about what "k" and "w"(omega) and all these greek symbols mean? i'm studying too many things and it is just hard to remember what they mean.
i am gonna implement FFT in verilog and previously i was a moderate knowledgeabout FFT but after watching this video get through from this Thanks saving my life :v
As an electronics technician of only a 2 year Associate in Science Technology degree in electronics for 37 years, and retired now, who helped engineers design, test breadboard and build / troubleshoot practical low frequency RLC circuits and also at the microwave frequencies for building 'cascaded microwave stripline amplifiers' in the 4 to 30 GHZ range for use in the real world, I had never used Fourier Transforms nor Laplace Transforms, I only used High Tech Oscilloscopes, Spectrum Analyzers, Vector Network Analyzers, SMITH CHARTS, Voltmeters, Ammeters, Frequency counters and computers, and sometimes used ALGEBRA and TRIGONOMETRY to solve electronics circuits problems In the laboratory and in the REAL WORLD, I have great RESPECT for the Geniuses of ELECTROMAGNETICS Pioneers, who had derived the mathematical physics of all the basics the we based our technology from: James Clerk Maxwell, Hertz, Gauss, Faraday, Lenz, Oersted, Henry, Steinmetz, Heaviside, Tesla, Weber, and many more, including STEVE WOZNIAC.
How it is n = 2r for even and n = 2r+1 for odd.. Can you explain please?.. Lets say if n = 8, for even -> n=2r -> 2*4 = 8. whereas, for odd -> n=2*r+1 => 9
Let us take the case that N is 8, the samples are numbered X[0], X[1], X[2], ... till X[7]. By dividing them into even and odd samples, X[0], X[2], X[4], and X[6] are grouped together, and X[1], X[3], X[5], and X[7] are grouped together. The value of r ranges from 0 to N/2 - 1. Thus, We can say that r is in the range of 0 to 3 (N/2 - 1 = 8/2 - 1 = 4 -1 = 3), making 2r and 2r+1 fall in the same range as well. Hope this makes things clear :)
This video is 10 years old and is still the most complete and concise video on the subject 💯
5:30 to skip review of big-O and DFT stuff, good video thanks
Awesome video thank you! Explained in ten minutes what I couldn't understand my professor was trying to say in three hours.
Thank you so much!! So clear!! I read the book, resulting in feeling hopeless, and your explanation just lightens up my world. ^_^ Thanks again!
your photo is so cute
I wish I could say the same...
Yes, good catch. x[8] should not be on slide 4 at 10:04, but it should be x[0] x[2] x[4] x[6] as Colo Ricatti pointed out. Somehow I skipped x[4] when counting.
Spent 20 mins trying to figure if there was something I'd missed lol. Will come back to the comments more often in the future
Best clear cut explanation , this video helps to jump from FT to FFT and understand the computational efficiency.
Come with some prep study of FT and do an actual calculation in excel then come here and you are done!
no, at 11:10 it is just splitting even and odd index terms (splitting N = 8 DFT into 2 DFTs of N = 4). The full bit reversal (x(0) x(4) x(2) x(6) ) occurs after three stages of splitting - see 15:08
This video had so much potential but glossed over so so much.
At 12:00, shouldn't the first left numbers be 0, 2, 4 and 6?
Yes
Yes
Yes
Yes
yes
the best i have watched so far..
Super helpful! I'm trying to make an audio spectrum analyzer. This has gotten me closer to understanding the concept, thanks!
did you build it ? can you share the circuit diagram?
me too. iv been looking around kinda everwhere for good information on how this all works and how to calculate audio into something viewable
@@CanaDan One tricky bit I’ve learned recently. You will want to skew the visualization horizontally towards the right. For audio, the FFT contains a ton of detailed high frequency information so if you just visualize the FFT as is, it is hard to see the bass/miss areas. You want to skew the visualization to emphasize the bass and mid regions for regular viewing as you might see in a spectrum analyzer in your DAW
Feel bad for Mr. Gauss
Somebody please get this guy a raise
At 9:33 you say "x sub zero" and I found that a bit confusing later in the video, when I forgot where it's came for, but now I have realized that it's more like "x sub oh". :)
Thanks for the great video! It really helped me!
Finally someone explains FFT that people can understand!!!!
哪来的8啊
Nan Wu 诶。。。 你怎么也看这个了
Nan Wu 什么8？
Steven Z 就扫了一眼封面就看到了x[8]
真的是眼力很好啊！
Thank you, this was super helpful in understanding the transition from DFT to DFFT.
frankly, i didn't get this 8:09 - N > n, k isn't great value too because of Nyquist limit (actually, k sample rate, the're no any sense in such calculations - it computes damn lot of ghost frequencies, because it increases sample rate.
9:05
I don't think the sum for even terms Σ(r=0 to (N/2)-1) x[2r] * (w_N/2)^kr is the DFT for N/2 samples since it should evaluate both the function x and the complex exponential at 2r instead of x at 2r and the exponential at r to be the DFT, and same for the sum for odd terms.
This comment is supposed to be a question ...
This is a good overview of FFT. It would be nice to explain how the DFT convolution sum is derived. Also, the de-interlacing of the inputs was glossed over (not explained clearly) but only the reversed binary notation was mentioned (this is just an after-the-fact observation of How, not an explanation of Why). Readers who dive deeper into the splitting of a larger N-point FFT into two smaller N/2-point FFT’s, or understand the relationships between the twiddle factors (and their periodic nature) would understand and retain better the FFT technique (and be able to conquer any arbitrary size of N-point FFT (N being a power of 2, of course).
How would the butterfly diagram (@ 15:06) change if there were numerous iterations of inputs? For example if N=128 but the 8 channels structure is maintained? Thanks
I highly suggest going back to second-year advanced calculus textbooks. There're many well-rounded explanations of FFT rather than what we have in DSP textbooks.
Thank you very very much ,Barry, very nice and deep explanation. Your way of explanation is very good. Thank you so much.
i just want to say that i love you man
there is a lot of interesting points at 13:41. please check that, if it is wrong.
GREAT THANK YOU , HELPED A LOT
To calculate the cost in the 13:42. It should be 2(N/2)^2+N/2, the next steps will be similar. So the final cost will be 3/2N+1/2N logN. It is because that the w of the lower half are simply negative of those of the upper half. So the cost should not be counted. Of course under big O notation, the final answer is still O(NlogN). You are really helpful, but there are some minor mistakes.
Yes, those end up being the twiddle factors - see them in the example diagram for N=8 at 15:14
@1:21 it should be N complex multiplies and N complex adds (not N-1) ... there are as many multiplies as there are adds
all important things at a place!!!
Not sure why you left out the recursive relation between the odd and even functions and the DFT. I was so confused where the speed gain was from.
FANTASTIC
In butterfly diagram it should be x[4] instead of x[8] ,right?
Yes. There is an annotation at 10:07 that points out the problem, but that may not be visible on your device. I have also uploaded a corrected version of this video to my channel, called The Fast Fourier Transform (FFT) Algorithm (c)
14:53 he cancels out the N^2/N (=N) saying "for capital N large enough, this term dominates". Someone, please help me, why do you drop the +N?
Awesome explanation. Made it very clear. Thanks
Great explanation on Butterfly algorithm!
Excellent explanation. Helped a lot. Thanks!
this is beautiful, thanks man!
Like si crees que Sergio y compañía no se han visto el vídeo, pero la recomendación ahí queda.
You missed one of the main parts: How to compute X[k+N/2]. So you only take k from 0 to N/2. Based on this, you didn't prove that the asymptotics is 2*(N/2)^2.
you are my hero .. I think I will use the website too .. thanks
X[k] = Xe[k] + Wn,k*Xo[k]. Index for X runs from 0 - 7, but that of Xe and Xo runs from 0 - 3. Please reply how to deal with X's when the index runs above 3. (I'm assuming N=8)
my question too
The complexity calculation for the FFT as you explained in the video is incorrect.
2 summations of half size of the array will be N(N/2 • 2), which is N^2.
The benefit of FFT is from the fact that
W_N^rk = -W_N^r(k-N) when k ≥ N.
This is due to the symmetric property of the exponential function:
e^j2π = -e^jπ
Now you only have to compute the FT for half the array and the other half can be constructed by negating those terms, so you end up with complexity
N(N/2) for the first split.
Wan , you're the best .
where is the input X[4] in the block diagram?
I don't know if you ever check comments for this particulair video since it's been a while since you've uploaded it, but I have a question: how do you get O(((N^2)/2)+N)? I know you explained it in the video (at around 12:00), but I don't understand it. Thanks in advance!
I just understood FFT for the first time!
Very cool, but maybe it lacks some schemas to express more the ideas of the simplification.
Really good video!!! Clearly explained!!! thankyou!
Thank you for sharing your knowledge.
where can i learn more about what "k" and "w"(omega) and all these greek symbols mean? i'm studying too many things and it is just hard to remember what they mean.
There shouldn't be an x[8] term, right? Because then N would be 9?
When you pull the WN^k term out at 7:55, is that term known as the twiddle coefficient?
I seen your channel mate, really love the content. Subscribed straight away, We should connect!
there might be sign errors: -1 should be used for X(k+N/2)
I'm having a hard time finding the equation you are referring to. Could you give me a time stamp in the video and be a bit more specific? Thanks.
Hi, sorry for the unclear description.There might be a sign error in the example graphs.
CAI Jianping why dont you just give the time in the video when the example graph appears
i am gonna implement FFT in verilog and previously i was a moderate knowledgeabout FFT but after watching this video get through from this Thanks saving my life :v
perfect explanation, thank you !
As an electronics technician of only a 2 year Associate in Science Technology degree in electronics for 37 years, and retired now, who helped engineers design, test breadboard and build / troubleshoot practical low frequency RLC circuits and also at the microwave frequencies for building 'cascaded microwave stripline amplifiers' in the 4 to 30 GHZ range for use in the real world, I had never used Fourier Transforms nor Laplace Transforms, I only used High Tech Oscilloscopes, Spectrum Analyzers, Vector Network Analyzers, SMITH CHARTS, Voltmeters, Ammeters, Frequency counters and computers, and sometimes used ALGEBRA and TRIGONOMETRY to solve electronics circuits problems In the laboratory and in the REAL WORLD,
I have great RESPECT for the Geniuses of ELECTROMAGNETICS Pioneers, who had derived the mathematical physics of all the basics the we based our technology from: James Clerk Maxwell, Hertz, Gauss, Faraday, Lenz, Oersted, Henry, Steinmetz, Heaviside, Tesla, Weber, and many more, including STEVE WOZNIAC.
where's all the cosines and sines in the equations?
what will it be if N = 30 ?
ist there an advantage of bit reversed positioning ?
10:08 its x[0] x[2] x[4] x[6]
Very good thank you! Nice and clear and well explained.
How do you choose appropriate W values ?
fuck me this is hard
well done brother
sorry i dont get it... first example N = 8.... second example N = 8 again but more stages... help pls
Could somebody explains what if the signal is 10 points sampled(which is not 2^N), please?
pad it with 0, or loop it
Thanks a lot Sir.. You are awesome! ;-)
How it is n = 2r for even and n = 2r+1 for odd.. Can you explain please?.. Lets say if n = 8, for even -> n=2r -> 2*4 = 8. whereas,
for odd -> n=2*r+1 => 9
Let us take the case that N is 8, the samples are numbered X[0], X[1], X[2], ... till X[7]. By dividing them into even and odd samples, X[0], X[2], X[4], and X[6] are grouped together, and X[1], X[3], X[5], and X[7] are grouped together. The value of r ranges from 0 to N/2 - 1. Thus, We can say that r is in the range of 0 to 3 (N/2 - 1 = 8/2 - 1 = 4 -1 = 3), making 2r and 2r+1 fall in the same range as well. Hope this makes things clear :)
This video saved my ass. Thank you Barry
Thankyou for the video, its great
Great video! Thanks
just what i wanted..thanx a lot :)
Linear filtering methods based on dft problems
While solving decimation in time and frequency algorithm of fft we used only DFT why not IDFT sir.
Thanks a lot that was really helpful. Great Job :)
Is that the power of j or i?
If you are electrical engineer like me, we use j
Great video
beautifully explained (y)
Great video. Thank you.
I just read the fast and fourious transform.
what is "j" ????
это i комплексная)
спасибо)
Thanks a lot...
Good one
Can anyone make a subtitle :目?
really good n useful
Thanks a ton.!!!
Good video but the ads are very distracting. if your intention to help, minimize or remove the ads. thumb down.
Its awesome :)) !..
15:07 muck fe
Sorry but gauss was not, Fourier was
very nice
LMAO imagine waiting 31 years for your image to be processed xD
awesome
well mama what about how well we are doing in skewl... the Kids
interesting！
15:33 ♡♡
هاذه صورت بابا اني هبه احبك هواي انته وعالتك اني حبكم هواي باي
Crap audio.
Ffg