Fourier Transform Computation Methods
editThe Fourier Transform is widely used in many areas of science and engineering. Since a Fourier transform converts a mathematical function from one domain (often time) to another function in another domain (often frequency),[1] the appropriate computation method largely depends how the original mathematical function is represented and the desired form of the output function.
Analytical Integration of Closed-form Functions
editSince the fundamental definition of a Fourier transform is an integral, functions that can be expressed as closed-form expressions are commonly computed by working the integral analytically to yield a closed-form expression in the Fourier transform conjugate variable as the result. This is the method used to generate tables of Fourier transforms, [2] including those found in the table below (Fourier transform#Tables of important Fourier transforms).
Many computer algebra systems such as Matlab and Mathematica that are capable of symbolic integration are capable of computing Fourier transforms analytically. For example, to compute the Fourier transform of f(t) = cos(6πt) e−πt2 one might enter the command "integrate cos(6*pi*t) exp(−pi*t^2) exp(-i*2*pi*f*t) from -inf to inf" into Wolfram Alpha.
Numerical Integration of Closed-form Functions
editIf the input function is in closed-form and the desired output function is a series of ordered pairs (for example a table of values from which a graph can be generated) over a specified domain, then the Fourier transform can be generated by numerical integration at each value of the Fourier conjugate variable (frequency, for example) for which a value of the output variable is desired.[3] Note that this method requires computing a separate numerical integration for each value of frequency for which a value of the Fourier transform is desired.[4][5] The numerical integration approach works on a much broader class of functions than the analytic approach, because it yields resuls for functions that do not have closed form Fourier transform integrals.
Numerical Integration of a Series of Ordered Pairs
editIf the input function is a series of ordered pairs (for example, a time series from measuring an output variable repeatedly over a time interval) then the output function must also be a series of ordered pairs (for example, a complex number vs. frequency over a specified domain of frequencies), unless certain assumptions and approximations are made allowing the output function to be approximated by a closed-form expression. In the general case where the available input series of ordered pairs are assumed be samples representing a continuous function over an interval (amplitude vs. time, for example), the series of ordered pairs representing the desired output function can be obtained by numerical integration of the input data over the available interval at each value of the Fourier conjugate variable (frequency, for example) for which the value of the Fourier transform is desired.[6]
Explicit numerical integration over the ordered pairs can yield the Fourier transform output value for any desired value of the conjugate Fourier transform variable (frequency, for example), so that a spectrum can be produced at any desired step size and over any desired variable range for accurate determination of amplitudes, frequencies, and phases corresponding to isolated peaks. Unlike limitations in DFT and FFT methods, explicit numerical integration can have any desired step size and compute the Fourier transform over any desired range of the congugate Fourier transform variable (for example, frequency).
Discrete Fourier Transforms and Fast Fourier Transforms
editIf the ordered pairs representing the original input function are equally spaced in their input variable (for example, equal time steps), then the Fourier transform is known as a discrete Fourier transform (DFT), which can be computed either by explicit numerical integration, by explicit evaluation of the DFT definition, or by fast Fourier transform (FFT) methods. In contrast to explicit integration of input data, use of the DFT and FFT methods produces Fourier transforms described by ordered pairs of step size equal to the reciprocal of the original sampling interval. For example, if the input data is sampled for 10 seconds, the output of DFT and FFT methods will have a 0.1 Hz frequency spacing.
- ^ Papoulis, Athanasios. Signal analysis. Vol. 191. McGraw-Hill, 1977.
- ^ Gradshteyn and Ryzhik's Table of Integrals, Series, and Products Daniel Zwillinger and Victor Moll (eds.) Eighth edition (Oct 2014)
- ^ Press, William H., et al. Numerical recipes in C. Vol. 2. Cambridge: Cambridge university press, 1996.
- ^ Bailey, David H., and Paul N. Swarztrauber. "A fast method for the numerical evaluation of continuous Fourier and Laplace transforms." SIAM Journal on Scientific Computing 15.5 (1994): 1105-1110.
- ^ Lado, F. "Numerical fourier transforms in one, two, and three dimensions for liquid state calculations." Journal of Computational Physics 8.3 (1971): 417-433.
- ^ Simonen, P., and H. Olkkonen. "Fast method for computing the Fourier integral transform via Simpson's numerical integration." Journal of biomedical engineering 7.4 (1985): 337-340.