The FFT function returns a result equal to the complex, discrete Fourier transform of *Array*. The result of this function is a single- or double-precision complex array.

The discrete Fourier transform, *F*(*u*), of an *N*-element, one-dimensional function, *f*(*x*), is defined as:

And the inverse transform, (*Direction* > 0), is defined as:

If the keyword OVERWRITE is set, the transform is performed in-place, and the result overwrites the original contents of the array.

For a one-dimensional FFT, running time is roughly proportional to the total number of points in *Array* times the sum of its prime factors. Let *N* be the total number of elements in *Array*, and decompose *N* into its prime factors:

Running time is proportional to:

where *T*_{3} ~ *4T*_{2}. For example, the running time of a 263 point FFT is approximately 10 times longer than that of a 264 point FFT, even though there are fewer points. The sum of the prime factors of 263 is 264 (1 + 263), while the sum of the prime factors of 264 is 20 (2 + 2 + 2 + 3 + 11).

*Result* = FFT( *Array* [, *Direction*] [, DIMENSION=*vector*] [, /DOUBLE] [, /INVERSE] [, /OVERWRITE] )

FFT returns a complex array that has the same dimensions as the input array. The output array is ordered in the same manner as almost all discrete Fourier transforms. Element 0 contains the zero frequency component, F_{0}. The array element F_{1} contains the smallest, nonzero positive frequency, which is equal to 1/(N_{i} T_{i}), where N_{i} is the number of elements and T_{i} is the sampling interval of the *i*^{th} dimension. F_{2} corresponds to a frequency of 2/(N_{i} T_{i}). Negative frequencies are stored in the reverse order of positive frequencies, ranging from the highest to lowest negative frequencies.

Note |

For an even number of points in the i^{th} dimension, the frequencies corresponding to the returned complex values are:

0, 1/(N_{i}T_{i}), 2/(N_{i}T_{i}), ..., (N_{i}/2-1)/(N_{i}T_{i}), 1/(2T_{i}), -(N_{i}/2-1)/(N_{i}T_{i}), ..., -1/(N_{i}T_{i})

where 1/(2T_{i}) is the Nyquist critical frequency.

For an odd number of points in the i^{th }dimension, the frequencies corresponding to the returned complex values are:

0, 1/(N_{i}T_{i}), 2/(N_{i}T_{i}), ..., (N_{i}/2-0.5)/(N_{i}T_{i}), -(N_{i}/2-0.5)/(N_{i}T_{i}), ..., -1/(N_{i}T_{i})

The array to which the Fast Fourier Transform should be applied. If *Array* is not of complex type, it is converted to complex type. The dimensions of the result are identical to those of *Array*. The size of each dimension may be any integer value and does not necessarily have to be an integer power of 2, although powers of 2 are certainly the most efficient.

*Direction* is a scalar indicating the direction of the transform, which is negative by convention for the forward transform, and positive for the inverse transform. If *Direction* is not specified, the forward transform is performed.

A normalization factor of 1/*N*, where *N* is the number of points, is applied during the forward transform.

Note |

Note also that the value of *Direction* is ignored if the INVERSE keyword is set.

Set this keyword to the dimension across which to calculate the FFT. If this keyword is not present or is zero, then the FFT is computed across all dimensions of the input array. If this keyword is present, then the FFT is only calculated only across a single dimension. For example, if the dimensions of *Array* are N1, N2, N3, and DIMENSION is 2, the FFT is calculated only across the second dimension.

Set this keyword to a value other than zero to force the computation to be done in double-precision arithmetic, and to give a result of double-precision complex type. If DOUBLE is set equal to zero, computation is done in single-precision arithmetic and the result is single-precision complex. If DOUBLE is not specified, the data type of the result will match the data type of *Array*.

Set this keyword to perform an inverse transform. Setting this keyword is equivalent to setting the *Direction* argument to a positive value. Note, however, that setting INVERSE results in an inverse transform even if *Direction* is specified as negative.

If this keyword is set, and the *Array* parameter is a variable of complex type, the transform is done "in-place". The result overwrites the previous contents of the variable. For example, to perform a forward, in-place FFT on the variable a:

a = FFT(a, -1, /OVERWRITE)

This routine is written to make use of IDL's *thread pool*, which can increase execution speed on systems with multiple CPUs. The values stored in the

Note |

Display the log of the power spectrum of a 100-element index array by entering:

PLOT, /YLOG, ABS(FFT(FINDGEN(100), -1))

As a more complex example, display the power spectrum of a 100-element vector sampled at a rate of 0.1 seconds per point. Show the 0 frequency component at the center of the plot and label the abscissa with frequency:

; Define the number of points and the interval: N = 100 T = 0.1 ; Midpoint+1 is the most negative frequency subscript: N21 = N/2 + 1 ; The array of subscripts: F = INDGEN(N) ; Insert negative frequencies in elements F(N/2 +1), ..., F(N-1): F[N21] = N21 -N + FINDGEN(N21-2) ; Compute T0 frequency: F = F/(N*T) ; Shift so that the most negative frequency is plotted first: PLOT, /YLOG, SHIFT(F, -N21), SHIFT(ABS(FFT(F, -1)), -N21)

Compute the FFT of a two-dimensional image by entering:

; Create a cosine wave damped by an exponential. n = 256 x = FINDGEN(n) y = COS(x*!PI/6)*EXP(-((x - n/2)/30)^2/2) ; Construct a two-dimensional image of the wave. z = REBIN(y, n, n) ; Add two different rotations to simulate a crystal structure. z = ROT(z, 10) + ROT(z, -45) WINDOW, XSIZE=540, YSIZE=540 LOADCT, 39 TVSCL, z, 10, 270 ; Compute the two-dimensional FFT. f = FFT(z) logpower = ALOG10(ABS(f)^2) ; log of Fourier power spectrum. TVSCL, logpower, 270, 270 ; Compute the FFT only along the first dimension. f = FFT(z, DIMENSION=1) logpower = ALOG10(ABS(f)^2) ; log of Fourier power spectrum. TVSCL, logpower, 10, 10 ; Compute the FFT only along the second dimension. f = FFT(z, DIMENSION=2) logpower = ALOG10(ABS(f)^2) ; log of Fourier power spectrum. TVSCL, logpower, 270, 10

Introduced: Original