FFT Rounding error?

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.

Not true. Subtracting a best-fit line is not likely to remove the discontinuity.

*** 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").

You can't do it.

No, and for the very reason you alluded to above.

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.

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.

What reason is that?

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.

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.

don't.

of

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.

[.. FFTs of real word data ..]

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.

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.

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

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:

2) On Sinusoidal Parameter Estimation available at:

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

Yes, you need to pick the right window. That is, do you want amplitude accuracy, frequency accuracy, etc.

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:

Yes, altering the sample rate will only save your arse in particular cases where the noise is harmonically related.

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

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

[.... windowed FFT in real world ...]

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.

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.

[....]

Closer to twice that would be good.

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.

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.

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

John Popelish wrote: (snip)

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

I often wonder how Crystal tests their ADCs? Perhaps an off the shelf function generator and passive filters.

(snip regarding FFT and periodicity)

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