is FFT always approximate?

If I have a time signal which is periodic, and I use FFT to obtain the 
spectrum, which should be discrete, will this FFT procedure be approximate? 
I am wondering about this because I've heard that FFT is only an 
approximation to the true Fourier transform... 

Michael wrote:
> If I have a time signal which is periodic, and I use FFT to obtain the 
> spectrum, which should be discrete, will this FFT procedure be approximate? 
> I am wondering about this because I've heard that FFT is only an 
> approximation to the true Fourier transform... 
> 
> 
If you have a sampled-time signal which is periodic with a strict 
integer period, then a digital Fourier transform over that period is 
necessarily exact.  The FFT (Fast Fourier Transform) is just a clever 
way of implementing a DFT over a period that can be expressed by 2^N.

If your signal is continuous-time and isn't band limited, then when you 
sample it you will introduce aliasing, which will render your 
sampled-time signal inadequate for representing your continuous-time 
signal -- but your FFT of the sampled-time signal will be exact.

Should you happen to have a continuous-time, perfectly band limited, 
periodic signal that you can sample then once you get the scaling 
figured out your FFT will, indeed, be exact.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html

"Tim Wescott" <tim@seemywebsite.com> wrote in message 
news:p7GdnQ-4Wtl8zlPZnZ2dnUVZ_uWdnZ2d@web-ster.com...
> Michael wrote:
>> If I have a time signal which is periodic, and I use FFT to obtain the 
>> spectrum, which should be discrete, will this FFT procedure be 
>> approximate? I am wondering about this because I've heard that FFT is 
>> only an approximation to the true Fourier transform...
> If you have a sampled-time signal which is periodic with a strict integer 
> period, then a digital Fourier transform over that period is necessarily 
> exact.  The FFT (Fast Fourier Transform) is just a clever way of 
> implementing a DFT over a period that can be expressed by 2^N.
>

What do you mean by "strict integer period"? My signal currently has 2*pi as 
its period, but I can do time scaling to get a period of 1, does that count? 

Michael skrev:
> If I have a time signal which is periodic, and I use FFT to obtain the
> spectrum, which should be discrete, will this FFT procedure be approximate?

The Fast Fourier Transform, FFT, is an EXACT but efficient
implementation of the Discrete Fourier Transform, DFT. The DFT
is itself an exact representation of a signal discrete-time signal
of finite length.

> I am wondering about this because I've heard that FFT is only an
> approximation to the true Fourier transform...

The depends on how you define the "true Fourier transform."

There are four different flavours of Fourier transforms. Signals can
be contionuous (C) in time or discrete (D), and they may be of
finite (F) or infinite (I) extend. The four flavours are CI, CF, DI
and DF.

The DFT is exact for the DF case, that is used in digital computers
for practical reasons. If your "real" objective is to analyze one
of the other variations, the DFT must be regarded as an
approximation of what you really want.

Rune

Michael wrote:
> If I have a time signal which is periodic, and I use FFT to obtain the
> spectrum, which should be discrete, will this FFT procedure be approximate?
> I am wondering about this because I've heard that FFT is only an
> approximation to the true Fourier transform...

FFT gives you the exact same answer as the DFT, it is just an efficient
way to compute the DFT, if you perform a simple DFT by hand, that is
multiple it all out on paper or on a big black board, and do it ten
times, you may gain some insight and see that some computations are
repeated over and over again and that you can take shortcuts by
exploiting symmetries and get the same answer, this is how Gauss
discovered the FFT over 200 years ago when DFT's were done by hand

Michael wrote:
> If I have a time signal which is periodic, and I use FFT to obtain the
> spectrum, which should be discrete, will this FFT procedure be approximate?
> I am wondering about this because I've heard that FFT is only an
> approximation to the true Fourier transform...

There are some good answers already given, but I wanted to throw
something else in.

The FFT can only give you coefficients for frequencies up to the
Nyquist frequency.  If you want it to give you the exact Fourier series
coefficients, which would extend beyond the Nyquist frequency, then you
would be out of luck.

This was mentioned by others earlier, when they talking about the
aliasing of high frequencies.  Even frequencies below the Nyquist
frequency could be in error, due to this.

I have found it useful to use Fourier interpolation (at least, that is
what I think it is called) to see what the time domain signal looks
like by the Fourier transform.  This interpolated signal is found by
putting the frequency domain components into a much larger frequency
domain array, keeping all the added higher frequency components at
zero, and being careful to split the Nyquist component into two parts,
half at the positive frequency, half at the negative frequency.  When
you IFFT back to the time domain, you see what you "really" have.

Since you are representing your time domain signal by a limited range
of frequencies, you might be surprised at the result.  For example, a
linear ramp no longer looks linear, or a square pulse doesn't look
square.  You will see the Gibbs ringing.

Good luck.

Michael wrote:
> "Tim Wescott" <tim@seemywebsite.com> wrote in message
> news:p7GdnQ-4Wtl8zlPZnZ2dnUVZ_uWdnZ2d@web-ster.com...
> > Michael wrote:
> >> If I have a time signal which is periodic, and I use FFT to obtain the
> >> spectrum, which should be discrete, will this FFT procedure be
> >> approximate? I am wondering about this because I've heard that FFT is
> >> only an approximation to the true Fourier transform...
> > If you have a sampled-time signal which is periodic with a strict integer
> > period, then a digital Fourier transform over that period is necessarily
> > exact.  The FFT (Fast Fourier Transform) is just a clever way of
> > implementing a DFT over a period that can be expressed by 2^N.
> >
>
> What do you mean by "strict integer period"? My signal currently has 2*pi as
> its period, but I can do time scaling to get a period of 1, does that count?

when you scale it, you want the period to be precisely N samples long
where N is the size of the DFT ("FFT" *is* a DFT, just a fast method of
doing it).  the DFT inherently periodically extends whatever data you
give it (i.e. it assumes the N samples passed to it are representative
of exactly one period).  then the output bins will have the amplitude
and phase of each harmonic.  bin 0 will have the DC component, bin 1
(and N-1) will have the first harmonic (or fundamental), bin 2 (and
N-2) will have the 2nd harmonic, etc.

r b-j

robert bristow-johnson skrev:
> Michael wrote:
> > "Tim Wescott" <tim@seemywebsite.com> wrote in message
> > news:p7GdnQ-4Wtl8zlPZnZ2dnUVZ_uWdnZ2d@web-ster.com...
> > > Michael wrote:
> > >> If I have a time signal which is periodic, and I use FFT to obtain the
> > >> spectrum, which should be discrete, will this FFT procedure be
> > >> approximate? I am wondering about this because I've heard that FFT is
> > >> only an approximation to the true Fourier transform...
> > > If you have a sampled-time signal which is periodic with a strict integer
> > > period, then a digital Fourier transform over that period is necessarily
> > > exact.  The FFT (Fast Fourier Transform) is just a clever way of
> > > implementing a DFT over a period that can be expressed by 2^N.
> > >
> >
> > What do you mean by "strict integer period"? My signal currently has 2*pi as
> > its period, but I can do time scaling to get a period of 1, does that count?

It depends on your "true" data. If your data is a finite length sample
of
a process of infinite duration, then all sorts of things happen and you

need to be very careful about how you proceed. You *can* proceed
assuming that you happened to sample exactly one period of some
periodic process, which everybody understand is a ridiculous claim.
However, that's just about the only way forward in this case.

As I said in a nother post, there are several different versions of
the Fourier transform. The DFT is exact for the case it was
designed for. It also happens to be the one version of the FT
that is possible to implement on a computer; neither continuous-
time signals nor infinitely long sequences are very easy to deal
with on a computer.

If your objective is to analyze some of the other FTs, you still
(usually) have to use the DFT for computations. Knowing the
basis for the DFT and how it differes from whatever version
of the FT you are interested in, is the key to get anywhere.

> when you scale it, you want the period to be precisely N samples long
> where N is the size of the DFT ("FFT" *is* a DFT, just a fast method of
> doing it).  the DFT inherently periodically extends whatever data you
> give it (i.e. it assumes the N samples passed to it are representative
> of exactly one period).

RBJ is right, PROVIDED you really use the (finite length) DFT to
analyse some infinite length sequence. This periodic/non-periodic
thing is NOT a property with the DFT itself (it only works on a
sequence of finite length which is available at all times); the
periodic extension shows how it relates to infinite series. It is no
problem as long as you are aware of what is going on; you could
easily find yourself in serious trouble if you forget about these
things.

You should be aware that a lot of people inherently assume that
the "real" objective for the analysis is a continuous-time signal
of infinite extent. If so, there are several issues to be aware of,
like the sampling theorem and aliasing, convergence and Gibbs'
phenomenon, as well as "artificially" introduced periodic properties
of the signal. A surprising number of people seem to attribute
these considerations as "weaknesses" of the DFT. I disagree
with such views.

As far as I am concerned, the DFT works perfectly well for what
it is intended to do. The problems occur when it is used for
analyses it was not intended for, but where no better
computational tools exist.

Rune

another hash over an old topic and perenial dispute here.

Rune Allnor wrote:
...
> It depends on your "true" data.

Rune, the DFT doesn't know or care what the "true" data is.  it
crunches the numbers the same in any case.  it does not know if the N
samples you pass it were N samples of some aperiodic sequence or if
those happened to be N samples defining exactly one period of a
periodic sequence.  it deals with it the same in either case and (this
is what is inexplicably controversial here sometimes) assumes it is the
latter.

> If your data is a finite length sample of
> a process of infinite duration, then all sorts of things happen and you
> need to be very careful about how you proceed.

to that we agree.  but i continue to contend that the "bad stuff" (the
effect of windowing) happens when you yank that finite length sample
out of that process of infinite duration.  that's when the windowing
happens. (before the DFT even sees the data.)

then when you pass those samples to the DFT, it inherently periodically
extends that.  i know Rick and other often object to anthropomorphizing
the DFT, but the DFT assumes the N samples passed to it are one period
of a periodic sequence.  whether it was originally (which the OP should
try to insure) or not is not something the DFT knows about.  it still
periodically extends that data inherently in its fundamental operation.

> You *can* proceed
> assuming that you happened to sample exactly one period of some
> periodic process, which everybody understand is a ridiculous claim.

with scaling and interpolation it need not be ridiculous.

> However, that's just about the only way forward in this case.
...
> > when you scale it, you want the period to be precisely N samples long
> > where N is the size of the DFT ("FFT" *is* a DFT, just a fast method of
> > doing it).  the DFT inherently periodically extends whatever data you
> > give it (i.e. it assumes the N samples passed to it are representative
> > of exactly one period).
>
> RBJ is right, PROVIDED you really use the (finite length) DFT to
> analyse some infinite length sequence. This periodic/non-periodic
> thing is NOT a property with the DFT itself

here we disagree.  i may state it more stridently the Oppenhiem and
Schafer, but the main property of the DFT is that it maps one periodic
sequence of length N to another periodic sequence of length N (where in
both cases, only N samples are used to represent either) according to
the equations:

           N-1
    X[k] = SUM{ x[n] exp(-j*2*pi*n*k/N) }
           n=0


               N-1
    x[n] = 1/N SUM{ X[k] exp(+j*2*pi*n*k/N) }
               k=0


in both cases x[n+N] = x[n] and X[k+N] = X[k]  for all n and k.

that's a pretty fundamental property.

> (it only works on a
> sequence of finite length which is available at all times); the
> periodic extension shows how it relates to infinite series. It is no
> problem as long as you are aware of what is going on; you could
> easily find yourself in serious trouble if you forget about these
> things.

to that i agree.

> You should be aware that a lot of people inherently assume that
> the "real" objective for the analysis is a continuous-time signal
> of infinite extent. If so, there are several issues to be aware of,
> like the sampling theorem and aliasing, convergence and Gibbs'
> phenomenon, as well as "artificially" introduced periodic properties
> of the signal. A surprising number of people seem to attribute
> these considerations as "weaknesses" of the DFT. I disagree
> with such views.

the effects of windowing is not the fault of the DFT.  the circular
effect of convolution (done by multiplying spectra) *is* something to
blame on the DFT.

r b-j

"robert bristow-johnson" <rbj@audioimagination.com> wrote in
news:1154406448.806363.135510@b28g2000cwb.googlegroups.com: 

snip....snip
 
> Rune, the DFT doesn't know or care what the "true" data is.  it

ship....snip


It's data are, not data is.  Data is plural.  Datum is singular.  I would 
have thought that someone as anal retentive as yourself would have known 
that.