Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations TugboatEng on being selected by the Eng-Tips community for having the most helpful posts in the forums last week. Way to Go!
Nice article on FFT vs DFT 3
- Thread starter GregLocock
- Start date
- Status
-
1
- #2
electricpete
Electrical
In the terminology of Oppenheimer's dsp textbooks.
A note on terminology
FFT is just an algorithm to compute the DFT. When you look at the results they are the same thing.
DTFT (discrete time fourier transform) is a different beast. It is general a continuous function of frequency.
A note on terminology
FFT is just an algorithm to compute the DFT. When you look at the results they are the same thing.
DTFT (discrete time fourier transform) is a different beast. It is general a continuous function of frequency.
-
2
- Thread starter
- #3
GregLocock
Automotive
Damn!
You are right, of course. Although if I put my stiff upper lip on shouldn't it be "the DFT and the FFT of the same sampled data are identical" ?
Or am I digging a deeper hole for myself?
Cheers
Greg Locock
You are right, of course. Although if I put my stiff upper lip on shouldn't it be "the DFT and the FFT of the same sampled data are identical" ?
Or am I digging a deeper hole for myself?
Cheers
Greg Locock
electricpete
Electrical
Didn't mean to nit-pick on the original post. It seemed like your subject line raised q question of contrast between FFT and DFT that wasn't discussed in the link.
"the DFT and the FFT of the same sampled data are identical". I'm not sure I get it. Sounds like you're saying the same thing as me.
Maybe the better terminology is that your upper lip has high dynamic stiffness?
"the DFT and the FFT of the same sampled data are identical". I'm not sure I get it. Sounds like you're saying the same thing as me.
Maybe the better terminology is that your upper lip has high dynamic stiffness?
- Thread starter
- #5
GregLocock
Automotive
"Didn't mean to nit-pick on the original post. It seemed like your subject line raised q question of contrast between FFT and DFT that wasn't discussed in the link."
No, I just liked the article. No nitpicking. (I'm biased, I know the author- he has a good solid background in signal analysis)
""the DFT and the FFT of the same sampled data are identical". I'm not sure I get it. Sounds like you're saying the same thing as me. "
Well it all depends on when you sample - an FFT has built-in limits , whereas a DFT doesn't. That is, you can give me a DFT for every FFT, I can't give you an FFT for every DFT.
Now, what really interests me is that the FFT terms were non symmetric about the centrally placed signal. Weren't they?
Cheers
Greg Locock
No, I just liked the article. No nitpicking. (I'm biased, I know the author- he has a good solid background in signal analysis)
""the DFT and the FFT of the same sampled data are identical". I'm not sure I get it. Sounds like you're saying the same thing as me. "
Well it all depends on when you sample - an FFT has built-in limits , whereas a DFT doesn't. That is, you can give me a DFT for every FFT, I can't give you an FFT for every DFT.
Now, what really interests me is that the FFT terms were non symmetric about the centrally placed signal. Weren't they?
Cheers
Greg Locock
electricpete
Electrical
Now I am back to thinking you misunderstand the terminology of Oppenheimer which I have expresssed.
FFT is a means to compute the DFT, period. Either one will require definition of a number of points. You can compute DFT by the definition which involves the sum of complex exponenentials. Or you can use a FFT algorithm which breaks it down hierarchically into smaller pieces. When you're done you have the same thing. Only difference is how much computer time you spent.
DTFT on the other hand is a different beast. As I said it is in general a continuous function of frequency. I think maybe that is what you are thinking of when you speak of the DFT.
FFT is a means to compute the DFT, period. Either one will require definition of a number of points. You can compute DFT by the definition which involves the sum of complex exponenentials. Or you can use a FFT algorithm which breaks it down hierarchically into smaller pieces. When you're done you have the same thing. Only difference is how much computer time you spent.
DTFT on the other hand is a different beast. As I said it is in general a continuous function of frequency. I think maybe that is what you are thinking of when you speak of the DFT.
electricpete
Electrical
OK, I get your point. The most common FFT algorithm is restricted to number of poitns 2^N.
electricpete
Electrical
"Now, what really interests me is that the FFT terms were non symmetric about the centrally placed signal. Weren't they?"
I don't see what you are referring to.
I don't see what you are referring to.
- Thread starter
- #9
GregLocock
Automotive
Yes it was the 2^n restriction I was talking about. If you look at his graph you'll see that the two biggest contributors to his 63 Hz peak are not of equal height. This is odd, since he is using 2 Hz resolution, so I'd expect the contributions from the 62 and 64 Hz lines to be equal.
Incidentally either you, Tom, or Mike suggested a while back that modern PCs are so fast that a DFT algorithm was no longer an unfeasible alternative to an FFT. Even on my blazingly slow 400 MHz PC this is the case, for 1024 points, even running interpreted basic. This is (or will be...) very handy for wavelet type analysis since the frequency/time/amplitude structure can now be teased out very smoothly.
Cheers
Greg Locock
Incidentally either you, Tom, or Mike suggested a while back that modern PCs are so fast that a DFT algorithm was no longer an unfeasible alternative to an FFT. Even on my blazingly slow 400 MHz PC this is the case, for 1024 points, even running interpreted basic. This is (or will be...) very handy for wavelet type analysis since the frequency/time/amplitude structure can now be teased out very smoothly.
Cheers
Greg Locock
electricpete
Electrical
As you know the spike is spread out as result of the rectangular time window. It produces a sinc function in the DTFT and that is samples at discrete points to give DFT.
That sinc function has a tail which goes inversely with frequency separation. I am pretty sure the difference in heights can be explained by remembering that there are really two peaks in the original continuous frequency function... one at +63 and one at -63. The tail of the -63 is additive to the tail of +63 in the neighborhood of +62, and it is subtractive in the neighborhood of +64. (180 degree phase shift between 62 and 64).
That sinc function has a tail which goes inversely with frequency separation. I am pretty sure the difference in heights can be explained by remembering that there are really two peaks in the original continuous frequency function... one at +63 and one at -63. The tail of the -63 is additive to the tail of +63 in the neighborhood of +62, and it is subtractive in the neighborhood of +64. (180 degree phase shift between 62 and 64).
- Thread starter
- #11
GregLocock
Automotive
My slack attitude leads me up the garden path again. Thanks.
Cheers
Greg Locock
Cheers
Greg Locock
electricpete
Electrical
Slack?? I’m almost afraid to ask.
If you’re slack, then my hair is red.
If you’re slack, then my hair is red.
electricpete
Electrical
I can see it is an overflow from discussion on the other forum.
All I can say is that I think you misunderstood.
ElectricPEte
All I can say is that I think you misunderstood.
ElectricPEte
- Thread starter
- #14
GregLocock
Automotive
No, what goes on in that forum stays in that forum. Here we discuss the interesting stuff.
I am slack in that I rapidly stopped looking at the maths of FFTs once I left uni, and just treat it as a black box, far too often. I have ignored the folded back contribution for decades, since all my practical experience is that whoever codes the algorithm up handles it properly, or failing that, I haven't noticed!
Cheers
Greg Locock
I am slack in that I rapidly stopped looking at the maths of FFTs once I left uni, and just treat it as a black box, far too often. I have ignored the folded back contribution for decades, since all my practical experience is that whoever codes the algorithm up handles it properly, or failing that, I haven't noticed!
Cheers
Greg Locock
electricpete
Electrical
I am glad that we have the other forum behind. Sorry to misunderstand you.
I would say the folded back stuff from the negative side is real, not an error. i.e. it really belongs there where it shows up on the positive side, regardless of the algorithm (algorithm doesn’t affect the results).
I think that if you look closely at the spectrum of any sinusoid which has been sampled over non-integral number of cycles, you will see that the spectrum falls away slower toward f=zero than it does toward f=infinitity (due to the negative spike tail going into positive frequency). It is easier to see the pattern if you are looking at high frequency resolution spectrum on a log scale. Also more readily apparent when “no-window” or “rectangular window” is applied than when Hamming applied.
You can see in the behavior of the tails in your link as well. At f=0 the magnitude is noticeably higher than at f=100, even though f=100 is closer to the spike at f=63.
If there was no spillover from the negative we would expect symmetric behavior. Rectangular window applied to sinsusoid in the time domain gives frequency impulse at 63hz in frequency convolved with sinc function in frequency domain. Since sinc function is symmetric about 0, we would expect the result to be symmetric about f=63 if not for the negative tail.
Looking at difference in the 62 and 64 magnitudes, it is clear that difference cannot be explained by the rate of fall of the negative tail which is relatively flat by the time it reaches positive ground. It is apparently caused by the 180 degree phase shift of the positive pattern between 62 and 64 so that the full value of negative tail is added to 62 and subtracted from 64.. I have to think a little bit where that 180 degree phase shift of the postiive pattern at f=63 comes from (any ideas?).
Sorry to take a small question and turn it into a big discussion. It’s interesting to try to figure it out.
I would say the folded back stuff from the negative side is real, not an error. i.e. it really belongs there where it shows up on the positive side, regardless of the algorithm (algorithm doesn’t affect the results).
I think that if you look closely at the spectrum of any sinusoid which has been sampled over non-integral number of cycles, you will see that the spectrum falls away slower toward f=zero than it does toward f=infinitity (due to the negative spike tail going into positive frequency). It is easier to see the pattern if you are looking at high frequency resolution spectrum on a log scale. Also more readily apparent when “no-window” or “rectangular window” is applied than when Hamming applied.
You can see in the behavior of the tails in your link as well. At f=0 the magnitude is noticeably higher than at f=100, even though f=100 is closer to the spike at f=63.
If there was no spillover from the negative we would expect symmetric behavior. Rectangular window applied to sinsusoid in the time domain gives frequency impulse at 63hz in frequency convolved with sinc function in frequency domain. Since sinc function is symmetric about 0, we would expect the result to be symmetric about f=63 if not for the negative tail.
Looking at difference in the 62 and 64 magnitudes, it is clear that difference cannot be explained by the rate of fall of the negative tail which is relatively flat by the time it reaches positive ground. It is apparently caused by the 180 degree phase shift of the positive pattern between 62 and 64 so that the full value of negative tail is added to 62 and subtracted from 64.. I have to think a little bit where that 180 degree phase shift of the postiive pattern at f=63 comes from (any ideas?).
Sorry to take a small question and turn it into a big discussion. It’s interesting to try to figure it out.
- Thread starter
- #16
GregLocock
Automotive
Well, I shall have to dig out my dft program and have a play, this has got so deep into the noise floor of my usual measurements that I have no experience with it.
At least I know what to look for, now!
Funny thing you should mention windows. I have lost count of the number of times people have made bad measurements by applying windows from force of habit. It got to the point with the HP3562A that I saved all my setups with a rectangular window (ie no window in practical terms), so that the user was forced to think about which window and why, and had hopefully taken some data with a rectangular window so that any huge errors with his choice of window were visible. This was wild optimism on my part, of course.
Cheers
Greg Locock
At least I know what to look for, now!
Funny thing you should mention windows. I have lost count of the number of times people have made bad measurements by applying windows from force of habit. It got to the point with the HP3562A that I saved all my setups with a rectangular window (ie no window in practical terms), so that the user was forced to think about which window and why, and had hopefully taken some data with a rectangular window so that any huge errors with his choice of window were visible. This was wild optimism on my part, of course.
Cheers
Greg Locock
- Thread starter
- #18
GregLocock
Automotive
Z=DFT? No:
But it is very closely related.
fractal transform ? Yes
it is lossy, hence not much used for engineering.
Cheers
Greg Locock
But it is very closely related.
fractal transform ? Yes
it is lossy, hence not much used for engineering.
Cheers
Greg Locock
electricpete
Electrical
Z transform is to DFT
as
Laplace transform is to Fourier transform.
Both Laplace and Z have the comlex plane as an indepdent variable.
Fourier takes Laplace and restricts s=sigma+j*w to s=jw... restricts the time "building blocks" from exponential decaying exp(-sigma*t)cos(w*t+theta) to sinusoidal cos(w*t+theta)
DFT takes Laplace and restricts z=r*exp(j*theta) to z=exp(jOmega). Restricts the building blocks from z^k=exp(r*k)exp(j*theta*k) to exp(j*theta*k).
as
Laplace transform is to Fourier transform.
Both Laplace and Z have the comlex plane as an indepdent variable.
Fourier takes Laplace and restricts s=sigma+j*w to s=jw... restricts the time "building blocks" from exponential decaying exp(-sigma*t)cos(w*t+theta) to sinusoidal cos(w*t+theta)
DFT takes Laplace and restricts z=r*exp(j*theta) to z=exp(jOmega). Restricts the building blocks from z^k=exp(r*k)exp(j*theta*k) to exp(j*theta*k).
- Status
Similar threads
- Locked
- Question
- Question
- Locked
- Question
- Locked
- Question