public class FFT extends Object implements Serializable, Cloneable
FFT computes the discrete Fourier transform of a real
vector of size n. The method used is a variant of the
Cooley-Tukey algorithm, which is most efficient when n
is a product of small prime factors. If n satisfies
this condition, then the computational effort is proportional to
n log n.
forward method computes the forward transform. If
n is even, then the forward transform is
If n is odd, is defined as above for m from 1 to (n - 1)/2.
Let f be a real valued function of time. Suppose we sample f at n equally spaced time intervals of length seconds starting at time . That is, we have
We will assume that n is odd for the remainder of
this discussion. The class
FFT treats this sequence as if
it were periodic of period n. In particular, it
assumes that . Hence, the period of the function is assumed to be
. We can invert the above transform for
p as follows:
This formula is very revealing. It can be interpreted in the following
manner. The coefficients q produced by
determine an interpolating trigonometric polynomial to the data. That is,
if we define
then we have
Now suppose we want to discover the dominant frequencies, forming the vector P of length (n + 1)/2 as follows:
These numbers correspond to the energy in the spectrum of the signal. In particular, corresponds to the energy level at frequency
Furthermore, note that there are only resolvable frequencies when n observations are taken. This is related to the Nyquist phenomenon, which is induced by discrete sampling of a continuous signal. Similar relations hold for the case when n is even.
backward method is used, then the backward transform
is computed. If
n is even, then the backward transform is
If n is odd,
The backward Fourier transform is the unnormalized inverse of the forward Fourier transform.
FFT is based on the real FFT in FFTPACK, which was
developed by Paul Swarztrauber at the National Center for Atmospheric
|Constructor and Description|
Constructs an FFT object.
|Modifier and Type||Method and Description|
Compute the real periodic sequence from its Fourier coefficients.
Compute the Fourier coefficients of a real periodic sequence.
public FFT(int n)
n- is the length of the sequence to be transformed
public double backward(double coef)
doublearray containing the Fourier coefficients
doublearray containing the periodic sequence
public double forward(double seq)
doublearray containing the sequence to be transformed
doublearray containing the transformed sequence
Copyright © 1970-2015 Rogue Wave Software
Built October 13 2015.