FFT

Purpose:

Calculates the Fast Fourier transform of a series in Cartesian (Real/Imaginary) form.

Syntax:

FFT(series, len)

Returns:

A complex series or table in Cartesian form.

Example:

W1: fft({1, 2, 3})

returns the complex series:

{6, -1.5 + 0.8660i, -1.5 - 0.8660i}

Example:

W1: gcos(1024*1024*1 + 1, 0.01, 10);setvunits("V")

W2: gcos(1024*1024*1, 0.01, 10);setvunits("V")

W3: tic;fft(w1);toclabel

W4: tic;fft(w2);toclabel

Both W1 and W2 contain a 10 Hz cosine wave sampled at 100 Hz. W1 has 1,048,577 samples while W2 has 1,048,576 samples (2²⁰).

W3 and W4 compute the FFT for each, labeling the result with computation time. W2's power-of-2 length enables significantly faster FFT computation in W4.

Example:

W5: fft(w1, 1024)

calculates a 1024 point FFT of W1 by appending 3 (1024 – 1021) zeros before performing the FFT computation.

Example:

W6: fft(w1, bestpow2(w1))

calculates a 1024 point FFT of W1 where 1024 is the smallest power of two size based on the length of W1.

Remarks:

FFT and IFFT implement the discrete Fourier transform pair X[k] and x[n] for series x of length N and start index 1 by:

The FFT result is complex and by default the REAL component is displayed. Use MAGNITUDE to display the magnitude and PHASE to display the phase.

The FFT always obeys Parseval's Theorem:

For example:

W1: gsqr(1000, 1/1000, 4)

W2: fft(w1)

W3: {sum(mag(w1)^2)}

W4: {mean(mag(w2)^2)}

W3 == W4 == 500.0

A mixed radix FFT algorithm is employed to process series of any length, however series with lengths equal to a power of 2 will be processed faster than series with lengths that are not equal to a power of 2.

Use LENGTH or SIZE to find out if a series is a power of 2 points long.

If the series length is a power of two and the series is purely real, further speed optimizations based on symmetry are employed.

See BESTPOW2 to specify the nearest power-of-two FFT size based on the input series length.

AMPSPEC computes a complex FFT normalized by the series length.

Use FFTP to create a magnitude/phase output and SPECTRUM to produce a normalized magnitude plot.

See NFFT to compute an N point FFT by zero padding or time aliasing.

See POWSPEC to compute the power spectrum.

See PSD to compute the power spectral density.

See WINFUNC for a list of windowing functions and amplitude correction schemes.

See DADiSP/FFTXL to optimize the FFT computation.

See Also:

AMPSPEC

BESTPOW2

DADiSP/FFTXL

DFT

FFT2

FFTSHIFT

GOERTZELDFT

HAMMING

IFFT

IMAGINARY

MAGNITUDE

NFFT

PHASE

POWSPEC

PSD

REAL

SPECGRAM

SPECTRUM

WINFUNC

References:

Oppenheim and Schafer

Digital Signal Processing

Prentice Hall, 1975

Digital Signal Processing Committee

Programs for Digital Signal Processing

I.E.E.E. Press, 1979