Discrete Fourier Transform

The Fourier Transform is defined as

 (1)

Now consider generalization to the case of a discrete function, by letting , where , with , ..., . Choose the frequency step such that
 (2)

with , ..., 0, ..., . There are values of , so there is one relationship between the frequency components. Writing this out as per Press et al. (1989)
 (3)

and
 (4)

The inverse transform is
 (5)

Note that , , 2, ..., so an alternate formulation is
 (6)

where the Negative frequencies have , Positive frequencies have , with zero frequency . corresponds to both and . The discrete Fourier transform can be computed using a Fast Fourier Transform.

The discrete Fourier transform is a special case of the z-Transform.

Arfken, G. Discrete Orthogonality--Discrete Fourier Transform.'' §14.6 in Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 787-792, 1985.
Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Fourier Transform of Discretely Sampled Data.'' §12.1 in Numerical Recipes in C: The Art of Scientific Computing. Cambridge, England: Cambridge University Press, pp. 494-498, 1989.