FFT Rounding error?

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.