Forums

FFT Rounding error?

Started by Andrew Holme May 12, 2007
On May 13, 8:31 am, "Andrew Holme" <and...@nospam.com> wrote:
> "Paul Russell" <pruss...@sonic.net> wrote in message > > news:5ao70nF2p0a4oU1@mid.individual.net... > > > > > Andrew Holme 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. > > > 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.
FYI, the window function cleans things up because it gets rid of the "discontinuity" between the 1st and last data points. Any discontinuity, such as you get in a square wave, will add a 1/f component to the Fourier Transform (i.e. 1/f^2 in the power spectrum, or -20 dB/decade). Since the 1st and last data points are treated as consecutive data by the DFT, this -20 dB/dec feature is just an artifact of the spectrum and doesn't represent anything real. Either a window function, or as somebody else suggested removing the "ramp" in the data (get the best-fit line and subtract it from the data). Either way removes the artificial discontinuity. It's easier to apply the window function, but you can try subtracting the best-fit line from one of your scans (and don't window) just to see what happens. Regards, Mark
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?
The fundamental limitation of FFT is that it produces the result as if the data were repeated. To the extent that this assumption is wrong, the results are wrong. The error at the high frequency end is reduced, because, if a fraction of a cycle is included, that error is spread over all the other cycles within the samples. But if a low frequency non integer case is included, that error is contained in only one or a very few cycles, so its significance is greater. For instance, lets say your sample contains significant energy at .5 Hz. Taking a 1 second sample of data must include only a half cycle of this energy. So the FFT will artificially generate harmonics of this clipped and assumed repeated half a cycle. Those generated harmonics will show up as distortions of all the harmonic frequencies of the clipped cycle, with a falling energy as frequency goes up. That is what I think your data is showing.
On May 13, 9:24 am, John Popelish <jpopel...@rica.net> wrote:
> 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? > > The fundamental limitation of FFT is that it produces the > result as if the data were repeated. To the extent that > this assumption is wrong, the results are wrong. The error > at the high frequency end is reduced, because, if a fraction > of a cycle is included, that error is spread over all the > other cycles within the samples. But if a low frequency non > integer case is included, that error is contained in only > one or a very few cycles, so its significance is greater. > > For instance, lets say your sample contains significant > energy at .5 Hz. Taking a 1 second sample of data must > include only a half cycle of this energy. So the FFT will > artificially generate harmonics of this clipped and assumed > repeated half a cycle. Those generated harmonics will show > up as distortions of all the harmonic frequencies of the > clipped cycle, with a falling energy as frequency goes up. > > That is what I think your data is showing.
It could also be a straight line. If the data is known to contain one very strong frequency, you can best fit that signal out before you do the actual FFT. When an FFT is used in distiortion testing, the part cycle problem happens a lot. To avoid it, the generator and ADC timing must be tightly coupled. It is very hard to exactly control the frequency of a super low distortion oscillator. For this reason, there is a lot of code out there for removing one frequency that is very near some user specified frequency. An interesting idea I've had for a while is to come up with software that does an FFT, finds the peaks and then strips out the best fit combination of signals that the peaks indicate. The remaining signal would then be FFTed again. This could be handy for removing things like the 60Hz and its harmonics from data.
"redbelly" <redbelly98@yahoo.com> wrote in message 
news:1179071750.419150.115650@w5g2000hsg.googlegroups.com...

> Either a window function, or as somebody else suggested > removing the > "ramp" in the data (get the best-fit line and subtract it > from the > data). Either way removes the artificial discontinuity.
Not true. Subtracting a best-fit line is not likely to remove the discontinuity.
"MooseFET" <kensmith@rahul.net> wrote in message 
news:1179077471.316911.199300@h2g2000hsg.googlegroups.com...
> > If the data is known to contain one very strong frequency, > you can > best fit that signal out before you do the actual FFT. > When an FFT is > used in distiortion testing, the part cycle problem > happens a lot. To > avoid it, the generator and ADC timing must be tightly > coupled. It is > very hard to exactly control the frequency of a super low > distortion > oscillator. For this reason, there is a lot of code out > there for > removing one frequency that is very near some user > specified > frequency.
*** Warning *** DFT (FFT) coefficients are not the same as least-mean-squares (best-fit) coefficients. I think you're confused if you think you can hide a signal from the DFT by subtracting its "best fit" (assuming you can even identify its "best fit").
> > An interesting idea I've had for a while is to come up > with software > that does an FFT, finds the peaks and then strips out the > best fit > combination of signals that the peaks indicate.
You can't do it.
> The remaining signal > would then be FFTed again. This could be handy for > removing things > like the 60Hz and its harmonics from data. >
No, and for the very reason you alluded to above.
"MooseFET" <kensmith@rahul.net> wrote in message
news:1179077471.316911.199300@h2g2000hsg.googlegroups.com...

> > If the data is known to contain one very strong frequency, you can > best fit that signal out before you do the actual FFT. When an FFT is > used in distiortion testing, the part cycle problem happens a lot. To > avoid it, the generator and ADC timing must be tightly coupled. It is > very hard to exactly control the frequency of a super low distortion > oscillator. For this reason, there is a lot of code out there for > removing one frequency that is very near some user specified > frequency. > > An interesting idea I've had for a while is to come up with software > that does an FFT, finds the peaks and then strips out the best fit > combination of signals that the peaks indicate. The remaining signal > would then be FFTed again. This could be handy for removing things > like the 60Hz and its harmonics from data.
You might want to look at the techniques that astrophysicists use to pull the signals corresponding to stellar pulsations or rotations or planet signatures out of raw data. In particular, you could start with the Lomb-Scargle Periodogram method. Peaks can be suppressed in order to reveal "hidden" smaller peaks.
On May 13, 11:46 am, "John E. Hadstate" <jh113...@hotmail.com> wrote:
> "MooseFET" <kensm...@rahul.net> wrote in message > > news:1179077471.316911.199300@h2g2000hsg.googlegroups.com... > > > > > > > If the data is known to contain one very strong frequency, > > you can > > best fit that signal out before you do the actual FFT. > > When an FFT is > > used in distiortion testing, the part cycle problem > > happens a lot. To > > avoid it, the generator and ADC timing must be tightly > > coupled. It is > > very hard to exactly control the frequency of a super low > > distortion > > oscillator. For this reason, there is a lot of code out > > there for > > removing one frequency that is very near some user > > specified > > frequency. > > *** Warning *** DFT (FFT) coefficients are not the same as > least-mean-squares (best-fit) coefficients. I think you're > confused if you think you can hide a signal from the DFT by > subtracting its "best fit" (assuming you can even identify > its "best fit"). > > > > > An interesting idea I've had for a while is to come up > > with software > > that does an FFT, finds the peaks and then strips out the > > best fit > > combination of signals that the peaks indicate. > > You can't do it.
I disagree. I see no reason that the location of the peak can't be the input to the usual best fit program. The best fit seaches the frequency up and down along with the phase and amplitude to reduce the mean square of what is left over as much as posible. If this program can take a manula input, I see no reason that an automated input can't be used.
> > The remaining signal > > would then be FFTed again. This could be handy for > > removing things > > like the 60Hz and its harmonics from data. > > No, and for the very reason you alluded to above.
What reason is that?
On May 13, 12:33 pm, "Greg Neill" <gneill...@OVEsympatico.ca> wrote:
> "MooseFET" <kensm...@rahul.net> wrote in message > > news:1179077471.316911.199300@h2g2000hsg.googlegroups.com... > > > > > If the data is known to contain one very strong frequency, you can > > best fit that signal out before you do the actual FFT. When an FFT is > > used in distiortion testing, the part cycle problem happens a lot. To > > avoid it, the generator and ADC timing must be tightly coupled. It is > > very hard to exactly control the frequency of a super low distortion > > oscillator. For this reason, there is a lot of code out there for > > removing one frequency that is very near some user specified > > frequency. > > > An interesting idea I've had for a while is to come up with software > > that does an FFT, finds the peaks and then strips out the best fit > > combination of signals that the peaks indicate. The remaining signal > > would then be FFTed again. This could be handy for removing things > > like the 60Hz and its harmonics from data. > > You might want to look at the techniques that astrophysicists > use to pull the signals corresponding to stellar pulsations > or rotations or planet signatures out of raw data. In particular, > you could start with the Lomb-Scargle Periodogram method. Peaks > can be suppressed in order to reveal "hidden" smaller peaks.
That is an interesting idea. Getting the 60Hz and its harmonics out of data is often the first step in trying to find other details in it. This would be quite a bit like taking data from an orbiting object and pulling the simple orbit components out. I bookmarked what I found so that I can go back to the actual text later. The Lomb-Scargle method targets unevenly spaced data. I typically don't have that problem so much as a slight error in the sample rate. Even a few PPM of timing error can make artifacts in the data. Typically, the ADC is run by a crystal that is not exactly on frequency. As a result, what was supposed to be 1.000 seconds of data is really 1.00005 seconds. sin(360 * 0.00005 * 60) = 0.0188 So the problem is real.
On May 13, 11:34 am, "John E. Hadstate" <jh113...@hotmail.com> wrote:
> "redbelly" <redbell...@yahoo.com> wrote in message > > news:1179071750.419150.115650@w5g2000hsg.googlegroups.com... > > > Either a window function, or as somebody else suggested > > removing the > > "ramp" in the data (get the best-fit line and subtract it > > from the > > data). Either way removes the artificial discontinuity. > > Not true. Subtracting a best-fit line is not likely to > remove the discontinuity.
You are right. Don't take out the best fit line unless you are fairly sure the problem is a simple drift. For a straight line drift, the best fit line works well. In most cases, just using the difference between the first and last sample works better than the best fit.
On May 13, 10:31 am, MooseFET <kensm...@rahul.net> wrote:
> On May 13, 9:24 am, John Popelish <jpopel...@rica.net> wrote: > > > > > 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? > > > The fundamental limitation of FFT is that it produces the > > result as if the data were repeated. To the extent that > > this assumption is wrong, the results are wrong. The error > > at the high frequency end is reduced, because, if a fraction > > of a cycle is included, that error is spread over all the > > other cycles within the samples. But if a low frequency non > > integer case is included, that error is contained in only > > one or a very few cycles, so its significance is greater. > > > For instance, lets say your sample contains significant > > energy at .5 Hz. Taking a 1 second sample of data must > > include only a half cycle of this energy. So the FFT will > > artificially generate harmonics of this clipped and assumed > > repeated half a cycle. Those generated harmonics will show > > up as distortions of all the harmonic frequencies of the > > clipped cycle, with a falling energy as frequency goes up. > > > That is what I think your data is showing. > > It could also be a straight line. > > If the data is known to contain one very strong frequency, you can > best fit that signal out before you do the actual FFT. When an FFT is > used in distiortion testing, the part cycle problem happens a lot. To > avoid it, the generator and ADC timing must be tightly coupled. It is > very hard to exactly control the frequency of a super low distortion > oscillator. For this reason, there is a lot of code out there for > removing one frequency that is very near some user specified > frequency.
The audio presicion boxes just do windowing to get around the problem. In some applications, you alter the rate of sampling to make the sampling synchronous to the signal. It's not all that hard, i.e. you just pull a crystal with a varactor. B&K made/makes a signal source with a 10MHz output on the back so that you can synthesize a clock for sampling that is synchronous to the audio test signal.
> > An interesting idea I've had for a while is to come up with software > that does an FFT, finds the peaks and then strips out the best fit > combination of signals that the peaks indicate. The remaining signal > would then be FFTed again. This could be handy for removing things > like the 60Hz and its harmonics from data.