| Re: FFT example. Help! [message #19880 is a reply to message #19879] |
Tue, 02 May 2000 00:00   |
asb
Messages: 13
Registered: May 1994
|
Junior Member |
|
|
I think your confusion stems from a misunderstanding of what the FFT
does. There are at least three related, but not identical, operations
that are referred to as "Fourier transforms".
1) Fourier integral.
A function f(x) that is "well behaved", _continuous_ and _not periodic_
has a Fourier transform F(k) that is "well behaved", continuous and not
periodic. F and f are related by the Fourier transform and Fourier
inversion formulas:
F(k)=int(f(x) exp(-i kx) dx)
and
f(x)=int(F(k) exp(i kx) dx)
The limits of the integral are + and - infinity.
2) Fourier series.
If the function f(x) is a periodic function of x with period L, its
Fourier transform is zero for all k that are not integral multiples of 2
Pi /L, and the integral diverges if k is an integral multiple of 2 Pi /
L. F(k) can be expressed as a sum of dirac delta functions, but it is
more convenient to simplify the notation and write f(x) as a Fourier
series:
f(x) = sum(An sin(n Pi x / L) + Bn cos(n Pi x / L ) )
where the Fourier coefficients An and Bn are
An=(2/L) int(f(x) sin(n pi x / L) dx)
Bn=(2/L) int(f(x) cos(n pi x / L) dx)
3) Discrete Fourier transform (DFT)
If the function F(x) is a periodic function of x with period L and is only
defined at N equally spaced discrete points xn = n L / N, n = 0, N-1, then
its Fourier transform is a periodic function of k = 2 Pi / L and is
nonzero only at the discrete values km = 2 m Pi / L, m = 0, N-1. Instead
of considering the functions F(x) and f(k), which are sums of delta
function, it is easier to consider Fm and fn, the coefficients of the
delta functions. These coefficients are related by the discrete fourier
tranform:
Fm = sum( fn exp(-i 2 Pi m n / N))
and its inverse
fn = (1/N) sum( Fm exp(i 2 Pi m n / N ) )
The FFT is a fast algorithm for computing the discrete fourier transform.
If you want an example using the FFT that "makes sense" (I asume that you
mean one that you can compute analytically), you have to remember that the
FFT computes the discrete Fourier transform, not the Fourier integral.
The simplest example is
fn = 1 for all n
Fm = N for m = 0; 0 otherwise
The FFT is frequently applied to the problem of estimating the Fourier
integral of a non-periodic function whose value is only known at a
discrete set of sampled points. One then must cope with errors introduced
by sampling (aliasing) and truncation (Gibbs ringing).
For a good overview, look in Numerical Recipes by Press et al.
I hope this helps.
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
