Fast Fourier Transform (FFT)

The Fast Fourier Transform is used in linear systems analysis, antenna studies, optics, random process modeling, probability theory, quantum physics, and boundary-value problems (Brigham, 2-3) and has been very successfully applied to restoration of astronomical data (Brault and White).

Mathematically speaking...

The mathematician Fourier recognized that a periodic function could be described as an infinite sum of periodic functions. In particular, he described the formulas for transforming such periodic functions into sums of harmonics of Sine or Cosine functions.

Real world use of these transforms considers discrete data points rather than continuous functions. The data is sampled at regular periods (the sampling rate or interval) over the interval at which the data repeats (the sampling period). The equations or algorithms for these calculations are called Discrete Fourier Transforms (DFT).

The number of computations it takes to calculate the DFT increases dramatically as more data points are considered. For the past 50 years or so, mathematicians have exploited redundancies and symmetries in the DFT to reduce the number of computations needed for N points from 2N² to 2N ln N. The result of this reduction is a significant reduction in computation time. It is these computations that are collectively known as Fast Fourier Transforms (FFT). The fastest of these FFTs are based on equations when the number of data points happens to be an integral power of 2.

In Origin...

Fast Fourier Transforms can be performed on Origin datasets by using the FFT Tool.

Other analyses in Origin which use the FFT are:

• Correlation
• Convolution
• Deconvolution
• FFT Filters:
  • Low Pass
  • High Pass
  • Band Pass
  • Band Block
  • Threshold

References

Brault, J. W. and White, O. R., 1971, The analysis and restoration of astronomical data via the fast Fourier transform, Astron. & Astrophys., 13, pp. 169-189.

Brigham, E. Oren, 1988, The Fast Fourier Transform and Its Applications, Englewood Cliffs, NJ: Prentice-Hall, Inc., 448 pp.