Fast Fourier Transform: FFT



DC On DC Off

FFT Physlet evaluates the Fast Fourier Transform, fft, of an analytic function.   The function string is parsed and then evaluated at a predetermined number of points before the fft is performed.  The transformed data can then be passed to other Physlets, such as DataGraph, using a data connection.  The FFT data source is identified using the getID() method.  It provides a data set containing the following variables:  n, f, fftsin, fftcos, and fft where fftsin and fftcos are the sin and cos terms of the transform, respectively. Whereas fftsin and fftcos variable can return either positive or negative coefficients, the fft variable contains the power spectrum and is therefore always positive.

The FFT Physlets contains a second data source that returns the (x,y) coordinate pairs of the original function.  This data source id is returned using the getFunctionID() method.  The data source variables are "x" and "y".

The above script shows the fft PowerTest the above applet with sinusoidal functions that are periodic on the interval [-1, 1].  The proportion of sin and cos terms are within the fft are shown as blue and green dots within the power spectrum.

Time Dependence

If the analytic function is a function of time, the Physlet animation clock will cause a new transform to be evaluated at every clock tick.

Even/Odd Numbers of Points

A periodic sinusoidal function will not produce a single fft component if the function is not continuous across boundaries. That is, extending a sinusoidal function past the past data point must reproduce the first data point.  Clearly, the interval, max-min, must contain exactly one harmonic.

Since the fft algorithm requires an even number of points, we have chosen to drop the last data point --the point where the function is evaluated as f(max) -- if an odd number of points is specified.  Dropping the last data point makes it easy to produce a function that is periodic on the interval [xmin, xmax].   If f(max) = f(min) and the last point is the same as the first data point of the next cycle and dropping this point produces the desired continuity.

Nyquist Frequency

In order to accurately represent an analytic function, the sampling rate must be at least twice the highest frequency component of the function, the Nyquist frequency.  This minimum sampling frequency, known as the Nyquist frequency, is calculated to be (number_of_points)/(max - min)/2.

Power Spectrum

A Fourier transform produces both sine and cos frequency components.  The power spectrum is the rms value of these components at a given frequency.

DC Component

Functions with a nonzero average value may produce a zero frequency component that obscures more interesting components.  This zero frequency component, that is, the average value of the function, can be suppressed using the setShowDC( boolen) method.  The default value is true.

GNU Software

The FFT routine used in the mathapps.FFT applet  uses the jnt.fft package that was developed by Bruce Miller at NIST. Several routines in this subpackage are Java ports of routines derived from Brian Gough's FFT routines in the Gnu Scientific Library (GSL). GSL is released under the Gnu General Public License; As such, this package must also be released under GPL.

The Physlet code for the mathapps.FFT applet may be downloaded here.