Forums

FFT Rounding error?

Started by Andrew Holme May 12, 2007
Andrew Holme wrote:

> "Andrew Holme" <andrew@nospam.com> wrote in message > news:f25kim$607$1$8300dec7@news.demon.co.uk... > >>"John Popelish" <jpopelish@rica.net> wrote in message >>news:NdydneGbHaGG0dvbnZ2dnUVZ_qfinZ2d@comcast.com... >> >>>Andrew Holme wrote: >>> >>>>I computed this forward FFT using MS VC++ 6.0 and FFTW: >>>> >>>>http://www.holmea.demon.co.uk/Misc/FFT.gif >>>> >>>>I don't think the "tail" should flick up like that at the low-frequency >>>>end. Is this caused by a lack of floating-point precision? >>> >>>This may be a result of having a non integer number of cycles at the >>>lowest frequency computed. >> >>Ah! I think you put your finger on it. I've just removed the DC, and the >>problem has gone. When you have an exactly integral number of cycles, the >>FFT shows a sharp reponse, and when you don't, it spills into adjacent >>buckets doesn't it? I think my DC bucket is spilling. >> >>Thanks John. >> >> > > > Damn. The problem is back. It's not just DC. I think I need to make the > 1e6 samples end on the same value they started at. Something like a Hanning > window. I think the discontinuity is creating a response at 1 Hz. Does > FFTW do windowing? > >
I'm not exactly sure what your application of the FFT is for how ever, in one of my apps, I calculate a group, use only the middle results, shifted the original samples over and added to the samples and recalculated. You may want to look for "Continuous FFT" coding. -- "I'm never wrong, once i thought i was, but was mistaken" Real Programmers Do things like this. http://webpages.charter.net/jamie_5
Andrew Holme wrote:

> I computed this forward FFT using MS VC++ 6.0 and FFTW: > > http://www.holmea.demon.co.uk/Misc/FFT.gif > > I don't think the "tail" should flick up like that at the low-frequency > end. Is this caused by a lack of floating-point precision? > > TIA
What do you mean by "flick up"? The graph provided has no "flick up". What the heck are you blathering on about? -- JosephKK Gegen dummheit kampfen die Gotter Selbst, vergebens.&nbsp;&nbsp; --Schiller
On 2007-05-12, Andrew Holme <andrew@nospam.com> wrote:
> I computed this forward FFT using MS VC++ 6.0 and FFTW: > > http://www.holmea.demon.co.uk/Misc/FFT.gif > > I don't think the "tail" should flick up like that at the low-frequency end. > Is this caused by a lack of floating-point precision?
I'm not sure what is causing that, but it reminds me of the FFT graphs I get from LTspice. BTW, what are you using to make that graph? -- Ben Jackson AD7GD <ben@ben.com> http://www.ben.com/
"Ben Jackson" <ben@ben.com> wrote in message 
news:slrnf4dbrn.2e62.ben@saturn.home.ben.com...
> On 2007-05-12, Andrew Holme <andrew@nospam.com> wrote: >> I computed this forward FFT using MS VC++ 6.0 and FFTW: >> >> http://www.holmea.demon.co.uk/Misc/FFT.gif >> >> I don't think the "tail" should flick up like that at the low-frequency >> end. >> Is this caused by a lack of floating-point precision? > > I'm not sure what is causing that, but it reminds me of the FFT graphs > I get from LTspice. > > BTW, what are you using to make that graph?
My C program outputs the data to a CSV file which I then paste into Microsoft Excel to plot the graph.
> > -- > Ben Jackson AD7GD > <ben@ben.com> > http://www.ben.com/
"Andrew Holme" <andrew@nospam.com> wrote in message 
news:f25gke$dlo$1$8302bc10@news.demon.co.uk...
>I computed this forward FFT using MS VC++ 6.0 and FFTW: > > http://www.holmea.demon.co.uk/Misc/FFT.gif > > I don't think the "tail" should flick up like that at the low-frequency > end. Is this caused by a lack of floating-point precision?
My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = 1 MHz i.e. duration = 1 second; and I want to analyse the frequency content. I'm using an FFT; but I'm getting a strong response in the FFT output at 1 Hz. This would be correct if the same 1e6 samples repeated, but they don't. Is there any way to reduce this effect, or is it a fundamental limitation of the FFT?
Andrew Holme wrote:
> "Andrew Holme" <andrew@nospam.com> wrote in message > news:f25gke$dlo$1$8302bc10@news.demon.co.uk... >> I computed this forward FFT using MS VC++ 6.0 and FFTW: >> >> http://www.holmea.demon.co.uk/Misc/FFT.gif >> >> I don't think the "tail" should flick up like that at the low-frequency >> end. Is this caused by a lack of floating-point precision? > > My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = 1 > MHz i.e. duration = 1 second; and I want to analyse the frequency content. > I'm using an FFT; but I'm getting a strong response in the FFT output at 1 > Hz. This would be correct if the same 1e6 samples repeated, but they don't. > Is there any way to reduce this effect, or is it a fundamental limitation of > the FFT? > >
This is probably just spectral leakage from the DC bin - my guess is that you are not applying an appropriate windowing function to the data prior to the FFT ? Paul
"Paul Russell" <prussell@sonic.net> wrote in message 
news:5anvbhF2om6lkU1@mid.individual.net...
> Andrew Holme wrote: >> "Andrew Holme" <andrew@nospam.com> wrote in message >> news:f25gke$dlo$1$8302bc10@news.demon.co.uk... >>> I computed this forward FFT using MS VC++ 6.0 and FFTW: >>> >>> http://www.holmea.demon.co.uk/Misc/FFT.gif >>> >>> I don't think the "tail" should flick up like that at the low-frequency >>> end. Is this caused by a lack of floating-point precision? >> >> My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = 1 >> MHz i.e. duration = 1 second; and I want to analyse the frequency >> content. I'm using an FFT; but I'm getting a strong response in the FFT >> output at 1 Hz. This would be correct if the same 1e6 samples repeated, >> but they don't. Is there any way to reduce this effect, or is it a >> fundamental limitation of the FFT? > > This is probably just spectral leakage from the DC bin - my guess is that > you are not applying an appropriate windowing function to the data prior > to the FFT ? > > Paul
Eliminating the DC component did not help. I am not using a windowing function at the moment. Can you suggest one? I don't mind sacrificing frequency resolution.
Andrew Holme wrote:
> "Paul Russell" <prussell@sonic.net> wrote in message > news:5anvbhF2om6lkU1@mid.individual.net... >> Andrew Holme wrote: >>> "Andrew Holme" <andrew@nospam.com> wrote in message >>> news:f25gke$dlo$1$8302bc10@news.demon.co.uk... >>>> I computed this forward FFT using MS VC++ 6.0 and FFTW: >>>> >>>> http://www.holmea.demon.co.uk/Misc/FFT.gif >>>> >>>> I don't think the "tail" should flick up like that at the low-frequency >>>> end. Is this caused by a lack of floating-point precision? >>> My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = 1 >>> MHz i.e. duration = 1 second; and I want to analyse the frequency >>> content. I'm using an FFT; but I'm getting a strong response in the FFT >>> output at 1 Hz. This would be correct if the same 1e6 samples repeated, >>> but they don't. Is there any way to reduce this effect, or is it a >>> fundamental limitation of the FFT? >> This is probably just spectral leakage from the DC bin - my guess is that >> you are not applying an appropriate windowing function to the data prior >> to the FFT ? >> >> Paul > > Eliminating the DC component did not help. I am not using a windowing > function at the moment. Can you suggest one? I don't mind sacrificing > frequency resolution. >
As a rule of thumb you almost always need to use a windowing function prior to an FFT. There are plenty to choose from but the Hann or "Hanning" window is a good choice unless you have any very specific requirements which might dictate an alternate function. <http://en.wikipedia.org/wiki/Window_function#Hann_window> Paul
"Paul Russell" <prussell@sonic.net> wrote in message 
news:5ao70nF2p0a4oU1@mid.individual.net...
> Andrew Holme wrote: >> "Paul Russell" <prussell@sonic.net> wrote in message >> news:5anvbhF2om6lkU1@mid.individual.net... >>> Andrew Holme wrote: >>>> "Andrew Holme" <andrew@nospam.com> wrote in message >>>> news:f25gke$dlo$1$8302bc10@news.demon.co.uk... >>>>> I computed this forward FFT using MS VC++ 6.0 and FFTW: >>>>> >>>>> http://www.holmea.demon.co.uk/Misc/FFT.gif >>>>> >>>>> I don't think the "tail" should flick up like that at the >>>>> low-frequency end. Is this caused by a lack of floating-point >>>>> precision? >>>> My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = >>>> 1 MHz i.e. duration = 1 second; and I want to analyse the frequency >>>> content. I'm using an FFT; but I'm getting a strong response in the >>>> FFT output at 1 Hz. This would be correct if the same 1e6 samples >>>> repeated, but they don't. Is there any way to reduce this effect, or is >>>> it a fundamental limitation of the FFT? >>> This is probably just spectral leakage from the DC bin - my guess is >>> that you are not applying an appropriate windowing function to the data >>> prior to the FFT ? >>> >>> Paul >> >> Eliminating the DC component did not help. I am not using a windowing >> function at the moment. Can you suggest one? I don't mind sacrificing >> frequency resolution. >> > > As a rule of thumb you almost always need to use a windowing function > prior to an FFT. There are plenty to choose from but the Hann or "Hanning" > window is a good choice unless you have any very specific requirements > which might dictate an alternate function. > > <http://en.wikipedia.org/wiki/Window_function#Hann_window> > > Paul
Thanks, Paul. The Hann window works well. I still get a large response at 1 Hz, which I would expect; but there's no spillage into 2 Hz and above.
On May 13, 1:23 am, "Andrew Holme" <and...@nospam.com> wrote:
> "Paul Russell" <pruss...@sonic.net> wrote in message > > news:5anvbhF2om6lkU1@mid.individual.net... > > > > > Andrew Holme wrote: > >> "Andrew Holme" <and...@nospam.com> wrote in message > >>news:f25gke$dlo$1$8302bc10@news.demon.co.uk... > >>> I computed this forward FFT using MS VC++ 6.0 and FFTW: > > >>>http://www.holmea.demon.co.uk/Misc/FFT.gif > > >>> I don't think the "tail" should flick up like that at the low-frequency > >>> end. Is this caused by a lack of floating-point precision? > > >> My C++ program generates 1e6 samples of aperiodic data, sampled at Ts = 1 > >> MHz i.e. duration = 1 second; and I want to analyse the frequency > >> content. I'm using an FFT; but I'm getting a strong response in the FFT > >> output at 1 Hz. This would be correct if the same 1e6 samples repeated, > >> but they don't. Is there any way to reduce this effect, or is it a > >> fundamental limitation of the FFT? > > > This is probably just spectral leakage from the DC bin - my guess is that > > you are not applying an appropriate windowing function to the data prior > > to the FFT ? > > > Paul > > Eliminating the DC component did not help. I am not using a windowing > function at the moment. Can you suggest one? I don't mind sacrificing > frequency resolution.
Before you do any windowing, take out the DC and the trend. If the data has either, the windowing tends to make new problems. Chances are when you take out the DC and the trend, the problem will be much less without windows. I've had good luck with 1.5 - cos(T) - 0.5*cos(2*T) It depends a lot on what your data looks like and what you want to get out of it.