# FFT: Fast Fourier Transform

A physical process can be considered in two domains:

1. The time domain, with the values of a parameter as a function of time.
2. The frequency domain, with the amplitude of the process as a function of frequency.

The two representations are equivalent, and each can be converted to the other with the appropriate Fourier transform.

The FFT, or Fast Fourier Transform, provides a very fast way to transform data between the two domains. Its discovery, in an era of very limited computing power, allowed Fourier transforms in real time with the collection of data. The FFT has been used in an extremely wide range of fields.

The Power Density Spectrum can be computed as either a one-sided or two-sided value, which will differ by a factor of two. Users frequently will not explicitly state which convention they used, so you should not be surprised if estimates of power vary by a factor of two. Other choices in the processing (segment size, windows, or padding) can also affect the precise numbers obtained as estimates of the power.

Infinite series will have infinite power, so often power is expressed in terms of the power spectral density per unit time. The power density will generally show a steady decrease with smaller periods or larger frequency, but may be interrupted by frequencies with anomalous power that represent cyclic phenomena.

The data for a Fourier transform are always samples at discrete time intervals from a continuous series. The reciprocal of the time interval is the sampling rate.

Sampling and aliasing. Power from periods (or frequencies) outside the sampling range will be folded back into the periods observed. This is known as aliasing, and is governed by the Nyquist Sampling Theorem.

Zero padding the series adds a number of zero values at the end of the series. The speed benefits of the FFT transform require an even power of two for the number of data points. Zero padding also removes some wraparound problems at the ends of data sets.

The FFT will estimate power only at discrete periods (or frequencies), T/n where T is the duration of the time segments used to do the FFT and n is an integer from 1 to the number of samples used in the FFT. Often the true period(s) may not be estimated directly, and its power will “leak” into the adjacent periods (or frequencies).

The shorter the sampling interval, the shorter the periods we can resolve. The more points sampled at the same rate, the finer the frequency resolution we can achieve.

The use of a window attempts to minimize the effects of leakage. The square window does nothing; the best choices are the Parzen or Welch (Press and others, 1985, p.425) with little practical difference between the two. Leakage refers to power spread over several adjacent frequencies, and occurs because we calculate power only at specified periods which may not exactly coincide with the true periods of the phenomena under study.

 Power Density Spectrum for a periodic series. There are a number of large spikes in the graph, and they occur at one period and even subdivisions of it.
 Power Density Spectrum for a series with no strong periodicity. The small regular oscillation of values on the left side of the diagram is a common artifact of the process.

Last revision 3/6/2005