FFT Rounding error?

On May 13, 4:06 pm, m...@sushi.com wrote:
> On May 13, 10:31 am, MooseFET <kensm...@rahul.net> wrote:
[.. FFTs of real word data ..]
> > > 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.

That doesn't always cut it.  Windowing creates its own artifacts.  It
spreads signals into the the channels beside their true frequency.
You also really need to remove the DC before you window.  If you
don't, the windowing raises the whole spectrum.


> 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.

Have you done this?  I found that people who say things aren't hard
have often not tried it.  I pulled an SRS generator's clock to force
it onto the exact needed frequency once.  One of the problems was that
any circuit that let me pull the crystal also added noise to the
crystal's frequency.  In the end, I found a way that allowed a very
limited range.

Sometimes you are just screwed.  If you have a signal at PI Hz and
another at sqrt(2) Hz, there is no way to align the sampling.  This is
sort of what can happen when you have main noise and some other
signal.


> 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.

Do you know the number?  I generally use SRS stuff when I need low
noise signals.

On May 13, 10:31 am, MooseFET <kensm...@rahul.net> wrote:
> On May 13, 9:24 am, John Popelish <jpopel...@rica.net> wrote:
>
>
> 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.

This general approach is a common one, though not necessarily based on
a "best fit combination".
Sometimes the final application is only signal estimation, sometimes
as in 4) below, the goal is to estimate and remove some of the tones
to allow further processing of a complex signal.

Examples include:

1)
A. P. Klapuri, "Multiple fundamental frequency estimation based on
harmonicity and spectral smoothness." IEEE Trans. Speech aand Audio
Proc,.11(6), 804-816, 2003
available at:
http://www.cs.tut.fi/sgn/arg/klap/multiplef0.pdf

2)
On Sinusoidal Parameter Estimation
available at:
http://www.elec.qmul.ac.uk/dafx03/proceedings/pdfs/dafx04.pdf

3)
A fast spectral estimation algorithm based on the FFT
Gough, P.T.
Dept. of Electr. & Electron. Eng., Canterbury Univ., Christchurch;
This paper appears in: Signal Processing, IEEE Transactions on
Publication Date: Jun 1994
On page(s): 1317-1322
Volume: 42,   Issue: 6

and
4)
J. A. Young and J. S. Lehnert, "Performance metrics for windows used
in real-time DFT-based multiple tone frequency excision," IEEE
Transactions on Signal Processing, vol. 47, no. 3, pp. 800-812, March
1999.


Dale B Dalrymple
http;//dbdimages.com

On May 13, 4:38 pm, MooseFET <kensm...@rahul.net> wrote:
> On May 13, 4:06 pm, m...@sushi.com wrote:> On May 13, 10:31 am, MooseFET <kensm...@rahul.net> wrote:
>
> [.. FFTs of real word data ..]
>
>
>
> > > > 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.
>
> That doesn't always cut it.  Windowing creates its own artifacts.  It
> spreads signals into the the channels beside their true frequency.
> You also really need to remove the DC before you window.  If you
> don't, the windowing raises the whole spectrum.

Yes, you need to pick the right window. That is, do you want amplitude
accuracy, frequency accuracy, etc.
>
> > 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.
>
> Have you done this?  I found that people who say things aren't hard
> have often not tried it.  I pulled an SRS generator's clock to force
> it onto the exact needed frequency once.  One of the problems was that
> any circuit that let me pull the crystal also added noise to the
> crystal's frequency.  In the end, I found a way that allowed a very
> limited range.

Pulling the crystal was done in digital video recorders. [The usual
signal flow is 4x over sampling, then create I and Q channel). Have I
personally done this? No, I was working on a project where the
consultant had done this elsewhere, but the project got canceled. I
have done the scheme where the sample rate is controlled by a DPLL. We
did this on a (don't laugh) 2400bps modem design. So the sample rate
was tweaked to match the signal, but not by pulling the crysta.

There is a Phiips chip that does the crystal pulling without a
varactor required. Come to think of it, I was around when a disk drive
chipset was being designed, and they pulled the crystal using a
varactor commonly used in FM radios. It had to be a cheap circuit,
hence the common varactor. That chipset didn't see the light of day,
so I don't know how well it worked. Getting back to the Philips chip,
my recollection is they changed the current in a bipolar amp to alter
the transconductance, and somehow that pulled the crystal.

I recall when working on the video project that needed the crystal
pulled, a good reference was a book by Frerking. Something like that.
Certain cuts of crystals are easier to pull. Here is the book:
<http://www.amazon.com/gp/offer-listing/0442224591/
ref=sr_1_olp_4/102-4707966-1571351?
ie=UTF8&s=books&qid=1179133963&sr=8-4>

>
> Sometimes you are just screwed.  If you have a signal at PI Hz and
> another at sqrt(2) Hz, there is no way to align the sampling.  This is
> sort of what can happen when you have main noise and some other
> signal.

Yes, altering the sample rate will only save your arse in particular
cases where the noise is harmonically related.
>
> > 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.
>
> Do you know the number?  I generally use SRS stuff when I need low
> noise signals.

I think it was the B&K 1049. It's only good to -96db, which was fine
in the day.

On May 13, 11:46 am, "John E. Hadstate" <jh113...@hotmail.com> wrote:
> *** Warning *** DFT (FFT) coefficients are not the same as
> least-mean-squares (best-fit) coefficients.

In what way?  In typical situations the result of an FFT
is invertable (minus rounding noise), so the "fit" is perfect
(zero-squared-error) against the full DFT basis set of
orthogonal sinusoids.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On May 13, 12:35 am, "Andrew Holme" <and...@nospam.com> wrote:
> 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.

This assumption may be part of the problem with your interpretation.

The content of the 1 Hz bin and any periodic repetition are not
necessarily related.  It's possible to create a signal which repeats
every 1 second but which has no content in the 1 Hz bin.  And
conversely, any content in the 1 Hz bin of an FFT aperture tells
you nothing about the signals behavior outside of that finite FFT
aperture window without a lot of other assumptions.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On May 14, 2:15 am, m...@sushi.com wrote:
> On May 13, 4:38 pm, MooseFET <kensm...@rahul.net> wrote:
[.... windowed FFT in real world ...]
> > That doesn't always cut it.  Windowing creates its own artifacts.  It
> > spreads signals into the the channels beside their true frequency.
> > You also really need to remove the DC before you window.  If you
> > don't, the windowing raises the whole spectrum.
>
> Yes, you need to pick the right window. That is, do you want amplitude
> accuracy, frequency accuracy, etc.

What if I want both?  Fitting a sine wave doesn't mess with either.
Yes it uses more CPU time but CPU time is cheap these days.





> > > 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.
>
> > Have you done this?  I found that people who say things aren't hard
> > have often not tried it.  I pulled an SRS generator's clock to force
> > it onto the exact needed frequency once.  One of the problems was that
> > any circuit that let me pull the crystal also added noise to the
> > crystal's frequency.  In the end, I found a way that allowed a very
> > limited range.
>
> Pulling the crystal was done in digital video recorders. [The usual
> signal flow is 4x over sampling, then create I and Q channel). Have I
> personally done this? No, I was working on a project where the
> consultant had done this elsewhere, but the project got canceled. I
> have done the scheme where the sample rate is controlled by a DPLL. We
> did this on a (don't laugh) 2400bps modem design. So the sample rate
> was tweaked to match the signal, but not by pulling the crysta.

None of those could be considered a low noise situation.  When you are
working with a noisy signal, the added noise of the crystal pulling
circuit doesn't matter.  The DPLL method makes some interesting spikes
in the spectrum that come and go depending on a lot of factors.

The output of a DPLL has a phase jitter caused by the fact that the
output must either switch on this edge or the next.  The this vs the
next timing shake and the slope of a low frequency signal makes a
small artifact waveform.

[....]
> > > 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.
>
> > Do you know the number?  I generally use SRS stuff when I need low
> > noise signals.
>
> I think it was the B&K 1049. It's only good to -96db, which was fine
> in the day.

Closer to twice that would be good.

On May 13, 10:14 pm, dbd <d...@ieee.org> wrote:
> On May 13, 10:31 am, MooseFET <kensm...@rahul.net> wrote:
>
> > On May 13, 9:24 am, John Popelish <jpopel...@rica.net> wrote:
>
> > 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.
>
> This general approach is a common one, though not necessarily based on
> a "best fit combination".

The fitting is the key point here.  It is based on the assumption that
the unwanted signal is steady over the aquistition time, but it
doesn't require that the frequency be known exactly.

I know that a lot of software already exists that takes in the user's
guess about the position of the unwanted signal and a search range.
My idea was to make a version that creates it own guesses from the
results of an initial FFT.

This would be, perhaps, only useful when things like the 60Hz are much
larger than the signal being looked for.  I know from experience that
the side bands on the 60Hz fall off very rapidly with frequency
offset.  At least this is the case in the places I have made the
measurements.

This method won't help to get the effects of an electronic ballast for
a fluorescent light out of the data.  That signal is something like
24KHz with a 20KHz FM modulation.  It goes all over the place.  There
is no easy way to fit to it.


> Sometimes the final application is only signal estimation, sometimes
> as in 4) below, the goal is to estimate and remove some of the tones
> to allow further processing of a complex signal.

That is more or less my case.  The tone removal based on DFT with the
extra step of the fitting is what I'm thinking of coding up.

To some degree, this will be a learning experience.  Making this work
will likely make me better understand the signals I'm dealing with.

John Popelish wrote:
(snip)

> 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.

If the name was FFS, for Fast Fourier Series, then this question
would come up less often.  The whole idea behind the Fourier
series is the analysis of periodic functions.  The Fourier transform
is the limit as the period goes to infinity, something computers
can't do.

I wouldn't call it a limitation, though, but fundamental, yes.

-- glen

glen herrmannsfeldt wrote:
> John Popelish wrote:
> (snip)
> 
>> 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.
> 
> If the name was FFS, for Fast Fourier Series, then this question
> would come up less often.  The whole idea behind the Fourier
> series is the analysis of periodic functions.  The Fourier transform
> is the limit as the period goes to infinity, something computers
> can't do.
> 
> I wouldn't call it a limitation, though, but fundamental, yes.

Okay.  It is a fundamental 'feature".  ;-)

John Popelish wrote:
> glen herrmannsfeldt wrote:

(snip regarding FFT and periodicity)

>> I wouldn't call it a limitation, though, but fundamental, yes.

> Okay.  It is a fundamental 'feature".  ;-)

I will agree with that.

There is an old saying I can't quite remember about using a
wrench to pound in nails when you can't find the hammer.

-- glen