Digital Signal Processing

A fast Fourier transform (FFT) is an algorithm that computes either the discrete Fourier transform (DFT) of a sequence or its inverse (IDFT). Fast Fourier transforms are mostly used for Fourier analysis, which converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The main purpose of Fourier analysis is to identify patterns or cycles in time series data or spatial data (such as images). The definition and details about the discrete Fourier transform (DFT) can be found in the section Signal Representation in the Time and Frequency Domains.

The fast Fourier transform has been the most important signal analysis algorithm in digital signal processing. It was included in the top 10 algorithms "with the greatest influence on the development and practice of science and engineering in the 20th century" by the journal IEEE Computing in Science & Engineering.

SAS/IML supports both one-dimensional (1-D) and two-dimensional (2-D) fast forward and inverse Fourier transforms. You can apply the FFT and IFFT functions to real signals, and you can apply the FFTC and IFFTC functions to complex signals. You can compute 2-D fast Fourier transforms of real signals by using the FFT2D and IFFT2D subroutines.