FFT implementation issues

Hi,

I am new to signal processing, so please don't laugh if my questions
appear silly to you.

In my knowledge, to get accurate spectrum result using FFT, the
sampling period should be close to the integal times of the whole
cycles of input signal period and the sampling points should be 2^n.
For example, 1KHz square wave, the sampling time should be integal
times of 1ms, i.e., 10ms. However, I am using a system from a company
that analyzes signal spectrum using FFT. The spectrum lines is only
selectable among 1600, 3200, 6400, 12800, and the sampling period is
not integral times of signal period. The spectrum result, amazingly,
is very close to the one we obtained with standard radix-2 FFT
algorithm sampling for integral signal period.

My question is, is there some specical FFT algorithm that sample for a
fixed time (i.e., probably fractional signal period) but can realize
similiar spectrum result as that obtained by standard FFT algorithm
with integral signal period?

Hopefully I made myself understood.

Any contribution to this question is appreciated.
David

<engp0931@gmail.com> wrote in message 
news:11b0658a-c87e-4679-ac59-e1aa46090957@i29g2000prf.googlegroups.com...
> Hi,
>
> I am new to signal processing, so please don't laugh if my questions
> appear silly to you.
>
> In my knowledge, to get accurate spectrum result using FFT, the
> sampling period should be close to the integal times of the whole
> cycles of input signal period and the sampling points should be 2^n.
> For example, 1KHz square wave, the sampling time should be integal
> times of 1ms, i.e., 10ms. However, I am using a system from a company
> that analyzes signal spectrum using FFT. The spectrum lines is only
> selectable among 1600, 3200, 6400, 12800, and the sampling period is
> not integral times of signal period. The spectrum result, amazingly,
> is very close to the one we obtained with standard radix-2 FFT
> algorithm sampling for integral signal period.
>
> My question is, is there some specical FFT algorithm that sample for a
> fixed time (i.e., probably fractional signal period) but can realize
> similiar spectrum result as that obtained by standard FFT algorithm
> with integral signal period?
>
> Hopefully I made myself understood.
>
> Any contribution to this question is appreciated.
> David

General signals don't have the type of characteristic that you cite.  For 
example, the sum of sin(t) and sin(pi*t) is not periodic although can be 
viewed as "close enough" for certain selected time spans.

And, generally, DFTs or FFTs aren't "tuned" to a signal period as you 
suggest.  But, if you have a situation where it can be done then more power 
to you.

Whichever time span is selected will smear the spectral information with a 
sinc whose width is inversely proportional to the time span.  When the time 
span is an integral number of periods of a periodic waveform then the sinc 
zeros coincide with the frequency samples and you get a nice neat set of 
samples of single sinc peaks.  When the time span isn't an integral number 
of periods of anything then the sinc peaks occur elsewhere and the sinc 
zeros don't coincide with the frequency samples.  Thus, there will be lots 
of nonzero samples particularly around the tonal frequencies - and caused 
perhaps only by a single tone.  This is called "spectral leakage".


There's one situation where this can be forced and can include variations in 
frequencies.  This is used in studying machinery noise where the noise would 
otherwise be in the noise or even in the noise coming out of a narrowband 
analyzer or FFT.  A tachometer on the machine is used as the clock base for 
doing the analysis.  This might be done by using the tachometer for the 
clock base of the sampler.  Then the sample rate will be an integer multiple 
of the machine speed and the spectral components will be harmonically 
related to the machine speed.  Even if the machine speed is erratic the 
machinery noises will stand out better than in a fixed-clock case.

You want to look at "spectral estimation"

Fred 

On 26 Mar, 06:07, engp0...@gmail.com wrote:
> Hi,
>
> I am new to signal processing, so please don't laugh if my questions
> appear silly to you.
>
> In my knowledge, to get accurate spectrum result using FFT, the
> sampling period should be close to the integal times of the whole
> cycles of input signal period

Wrong. The DFT is a representation of the input sequence which
is exact to within numerical accuracy, regardless of the
properties of the input signal.

> and the sampling points should be 2^n.

That used to be a constraint in order to use the FFT; that's
not the case anymore. You can use the FFT with any signal length.

> For example, 1KHz square wave, the sampling time should be integal
> times of 1ms, i.e., 10ms.

Nope; the sampling interval should be higher than the Nyquist
limit. Defining the Nyquist limit for a square wave may be
a bit tricky, as the square wave has infinite bandwidth, but
once you decide on a bandwidth B the sampling frequency Fs
must satisfy

    Fs > 2B.

There are no constraints wrt to the period of the square wave.

> However, I am using a system from a company
> that analyzes signal spectrum using FFT. The spectrum lines is only
> selectable among 1600, 3200, 6400, 12800, and the sampling period is
> not integral times of signal period. The spectrum result, amazingly,
> is very close to the one we obtained with standard radix-2 FFT
> algorithm sampling for integral signal period.

The spectrum analyzer works because the DFT is far more robust
to signal parameters than you think. Just take one second to
contemplate what you wrote in the paragraph above: IF the FFT
happened to depend on signal parameters as strongly as you
suggest (it doesn't), that would mean that the designers of the
spectrum analyzers would have to make equipment that would have
to be able to work at all possible sampling frequencies. It is
both very hard and very expensive to make that sort of
equipment.

Second, you as analyst would have to know what the signal
looks like in advance, *before* making an actual measurement,
in order to select the correct settings. Whitch is something
of a Catch 22 situation.

> My question is, is there some specical FFT algorithm that sample for a
> fixed time (i.e., probably fractional signal period) but can realize
> similiar spectrum result as that obtained by standard FFT algorithm
> with integral signal period?

Well, the DFT is a *representation* of the data which is very
robust, and gives useful results for statonary (not necessarily
periodic) data. The key is to remember that the DFT gives the
'big picture' for these general types of data, but you can't
trust the details. The details match to prefection only with
very special classes of periodic data, where the signal is
sampled over an integer multiple of periods etc.

Rune

On Mar 26, 4:27 am, Rune Allnor <all...@tele.ntnu.no> wrote:

> ...
> Well, the DFT is a *representation* of the data which is very
> robust, and gives useful results for statonary (not necessarily
> periodic) data. The key is to remember that the DFT gives the
> 'big picture' for these general types of data, but you can't
> trust the details. The details match to prefection only with
> very special classes of periodic data, where the signal is
> sampled over an integer multiple of periods etc.
>
> Rune

David

The above has a very 'formalist derived' slant. I would put it
differently, and perhaps no more usefully as:

Well, the DFT is an exact *representation* of the data within it's
window which is very robust, and gives useful results, and for
statonary (not necessarily periodic) data gives useful results about
data outside it's window. If you want exact representation to be
correct at other times, calculate another DFT for a data window then.
The key is to remember that the DFT gives the 'big picture' for these
general types of data, but you can't trust the details to be ideal.
The details match to the ideal only with very special classes of data,
where the data window and transform size contain samples over an
integer multiple of periods etc.


For a good general discussion of spectrum estimation related issues
with less slant than either of the above try:
Power Spectrum Estimation (04-Nov-1995)
http://www.national.com/an/AN/AN-255.pdf

Dale B. Dalrymple

On Mar 26, 3:27 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 26 Mar, 06:07, engp0...@gmail.com wrote:
> > I am new to signal processing, so please don't laugh if my questions
> > appear silly to you.
>
> > In my knowledge, to get accurate spectrum result using FFT, the
> > sampling period should be close to the integal times of the whole
> > cycles of input signal period
>
> Wrong. The DFT is a representation of the input sequence which
> is exact to within numerical accuracy, regardless of the
> properties of the input signal.

I note that the two above claims are talking about
two differently worded concepts, depending on how much
the OP's definition of "accurate spectrum result"
corresponds with Rune's "accurate representation".

If the OP considers an FFT only to produce an "accurate
spectrum result" if, say, just the 5 peak bins correspond
exactly to a signal composed of 5 arbitrary frequency
sinusoids (below Fs/2), then the two above claims are not
necessarily contradictory.



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

"Ron N." <rhnlogic@yahoo.com> wrote in message 
news:3a52c80e-9308-4e3f-9f25-386381db1318@i7g2000prf.googlegroups.com...
> On Mar 26, 3:27 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>> On 26 Mar, 06:07, engp0...@gmail.com wrote:
>> > I am new to signal processing, so please don't laugh if my questions
>> > appear silly to you.
>>
>> > In my knowledge, to get accurate spectrum result using FFT, the
>> > sampling period should be close to the integal times of the whole
>> > cycles of input signal period
>>
>> Wrong. The DFT is a representation of the input sequence which
>> is exact to within numerical accuracy, regardless of the
>> properties of the input signal.
>
> I note that the two above claims are talking about
> two differently worded concepts, depending on how much
> the OP's definition of "accurate spectrum result"
> corresponds with Rune's "accurate representation".
>
> If the OP considers an FFT only to produce an "accurate
> spectrum result" if, say, just the 5 peak bins correspond
> exactly to a signal composed of 5 arbitrary frequency
> sinusoids (below Fs/2), then the two above claims are not
> necessarily contradictory.
>

Yes.  Another way to say it is that the OP really wants to compute a Fourier 
Series of an actual periodic waveform and is using the DFT to do that. 
Probably no reason why not.  It's just a slightly unusual way of looking at 
things.  But it does help one understand the difference between a Fourier 
Series and a general DFT.  One (the DFT or a Fourer Transform of a windowed 
function) has spectral leakage in general and one (a Fourier Series) doesn't 
perforce.

The only other thing to say is that since time is discrete here that the 
Fourier Series integral over one period becomes finite sum over one period. 
That's why the DFT can do the "work" of computing a Fourier Series.

Fred 

On Mar 25, 10:07 pm, engp0...@gmail.com wrote:
> Hi,
>
> I am new to signal processing, so please don't laugh if my questions
> appear silly to you.
>
> In my knowledge, to get accurate spectrum result using FFT, the
> sampling period should be close to the integal times of the whole
> cycles of input signal period and the sampling points should be 2^n.
> For example, 1KHz square wave, the sampling time should be integal
> times of 1ms, i.e., 10ms. However, I am using a system from a company
> that analyzes signal spectrum using FFT. The spectrum lines is only
> selectable among 1600, 3200, 6400, 12800, and the sampling period is
> not integral times of signal period. The spectrum result, amazingly,
> is very close to the one we obtained with standard radix-2 FFT
> algorithm sampling for integral signal period.
>
> My question is, is there some specical FFT algorithm that sample for a
> fixed time (i.e., probably fractional signal period) but can realize
> similiar spectrum result as that obtained by standard FFT algorithm
> with integral signal period?
>
> Hopefully I made myself understood.
>
> Any contribution to this question is appreciated.
> David


David

Another general reference is at:

http://cp.literature.agilent.com/litweb/pdf/5988-6774EN.pdf


To deal with the case of signals not having an integer number of
cycles in the DFT window and transform size there are at least 5
common responses:

1) generate the sampling frequency to enforce integer number of
cycles...
Fred has already mention the use of tachs for this. Some references:

http://www.home.agilent.com/upload/cmc_upload/All/6C06DATAACQ_ORDER.pdf
http://www.ni.com/pdf/labview/us/order_analysis_toolkit.pdf
http://pcfarina.eng.unipr.it/Public/Kalman/SAE_972006.pdf

2) resample the time domain data to a new sampling frequency that
provides an integer number of cycles...

3) resample the complex frequency domain coefficients at the desired
frequencies. In some circles such as IEEE Trans. on Instrumentation
and Measurement this is refered to as the 'interpolated FFT'

4) interpolate the peaks of the magnitude response in the frequency
domain, such as is included in the good discussion in:

http://www.ericjacobsen.org/FTinterp.pdf

5) pick the nearest bin and accept the error or complain about the
inaccuracy of the FFT (It ain't like my actual Fourier transform.)


I hope these references may be of some use to you.

Nevermind while the rest of us sit back in our armchairs, wave our
hands and philosophize here at length.

Dale B. Dalrymple

Fred Marshall wrote:
(snip)

> Yes.  Another way to say it is that the OP really wants to compute a Fourier 
> Series of an actual periodic waveform and is using the DFT to do that. 
> Probably no reason why not.  It's just a slightly unusual way of looking at 
> things.  But it does help one understand the difference between a Fourier 
> Series and a general DFT.  One (the DFT or a Fourer Transform of a windowed 
> function) has spectral leakage in general and one (a Fourier Series) doesn't 
> perforce.

I always thought it should have been called FFS (Fast Fourier Series),
along with DFS, DSS, and DCS.

> The only other thing to say is that since time is discrete here that the 
> Fourier Series integral over one period becomes finite sum over one period. 
> That's why the DFT can do the "work" of computing a Fourier Series.

Time is always discrete when doing an FFT, whether you like it or not.
You might be simulating continuous time, but the transform is done
in discrete time.  It would seem to me, then, that the transform name
assumes one is simulating continuous time, but the transform doesn't
know that.

-- glen

On Tue, 25 Mar 2008 22:07:23 -0700 (PDT), engp0931@gmail.com wrote:

>Hi,
>
>I am new to signal processing, so please don't laugh if my questions
>appear silly to you.

Hi David,
  Your questions are definitely NOT silly.
Although we do have to make assumptions on 
what are the meanings of some of the 
terminology that you used in your questions.

>In my knowledge, to get accurate spectrum result using FFT, the
>sampling period should be close to the integal times of the whole
>cycles of input signal period and the sampling points should be 2^n.

If by "accurate" you mean FFT results that show very 
little "leakage", then I believe your statement is 
essentially correct.  However, real-world (information carrying) 
signals are not periodic.  So the idea of having the 
time-duration of the FFT's input sequence being 
an integer multiple of some signal's period goes 
"out the window".  

>For example, 1KHz square wave, the sampling time should be integal
>times of 1ms, i.e., 10ms. 

As Rune said, squarewaves have an infinite bandwidth 
so squarewaves are not a good example of a periodic 
time sequence for use in discussing the "accuracy" of 
the FFT. 

>However, I am using a system from a company
>that analyzes signal spectrum using FFT. The spectrum lines is only
>selectable among 1600, 3200, 6400, 12800, and the sampling period is
>not integral times of signal period. The spectrum result, amazingly,
>is very close to the one we obtained with standard radix-2 FFT
>algorithm sampling for integral signal period.

Oops.  I don't know what you mean by "spectrum lines" 
as it pertains to your "system".

>My question is, is there some specical FFT algorithm that sample for a
>fixed time (i.e., probably fractional signal period) but can realize
>similiar spectrum result as that obtained by standard FFT algorithm
>with integral signal period?

Assuming I understand your question, my answer 
is, "None that I know of."
People use the process of "windowing" their 
time-damain samples to reduce "FFT leakage", but I 
know of no algorithm that will totally eliminate 
FFT leakage due to non-periodic input signals.

Good Luck,
[-Rick-]

On Mar 26, 10:58 am, dbd <d...@ieee.org> wrote:
> On Mar 25, 10:07 pm, engp0...@gmail.com wrote:
> > I am new to signal processing, so please don't laugh if my questions
> > appear silly to you.
>
> > In my knowledge, to get accurate spectrum result using FFT, the
> > sampling period should be close to the integal times of the whole
> > cycles of input signal period and the sampling points should be 2^n.
> > For example, 1KHz square wave, the sampling time should be integal
> > times of 1ms, i.e., 10ms. However, I am using a system from a company
> > that analyzes signal spectrum using FFT. The spectrum lines is only
> > selectable among 1600, 3200, 6400, 12800, and the sampling period is
> > not integral times of signal period. The spectrum result, amazingly,
> > is very close to the one we obtained with standard radix-2 FFT
> > algorithm sampling for integral signal period.
>
> > My question is, is there some specical FFT algorithm that sample for a
> > fixed time (i.e., probably fractional signal period) but can realize
> > similiar spectrum result as that obtained by standard FFT algorithm
> > with integral signal period?
>
> > Hopefully I made myself understood.
>
> > Any contribution to this question is appreciated.
> > David
>
> David
>
> Another general reference is at:
>
> http://cp.literature.agilent.com/litweb/pdf/5988-6774EN.pdf
>
> To deal with the case of signals not having an integer number of
> cycles in the DFT window and transform size there are at least 5
> common responses:
>
> 1) generate the sampling frequency to enforce integer number of
> cycles...
> Fred has already mention the use of tachs for this. Some references:
>
> http://www.home.agilent.com/upload/cmc_upload/All/6C06DATAACQ_ORDER.pdfhttp://www.ni.com/pdf/labview/us/order_analysis_toolkit.pdfhttp://pcfarina.eng.unipr.it/Public/Kalman/SAE_972006.pdf
>
> 2) resample the time domain data to a new sampling frequency that
> provides an integer number of cycles...
>
> 3) resample the complex frequency domain coefficients at the desired
> frequencies. In some circles such as IEEE Trans. on Instrumentation
> and Measurement this is refered to as the 'interpolated FFT'

3b) zero-padding and using a longer FFT is one method
of computing interpolated or resampled frequency domain
coefficients, and may be more computationally efficient
than other methods of resampling.

> 4) interpolate the peaks of the magnitude response in the frequency
> domain, such as is included in the good discussion in:
>
> http://www.ericjacobsen.org/FTinterp.pdf

4b) if by "accurate" you mean accurate magnitude, then you
could use a "flat-top" window before the FFT, which then
trivializes magnitude "interpolation" in the frequency
domain.

> 5) pick the nearest bin and accept the error or complain about the
> inaccuracy of the FFT (It ain't like my actual Fourier transform.)

This seems to be the most common response from non-DSP
students attempting to use an FFT.

> I hope these references may be of some use to you.
>
> Nevermind while the rest of us sit back in our armchairs, wave our
> hands and philosophize here at length.

I have more "hand waving" references regarding various
random attempts at frequency estimation on my DSP web page:
 http://www.nicholson.com/rhn/dsp.html



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