Discrete Fourier Transform

The Fourier Transform is defined as

$$f(\nu)={\mathcal F} [f(t)] =\int_{-\infty}^\infty f(t)e^{-2\pi i\nu t}\,dt.$$ (1)

Now consider generalization to the case of a discrete function, $f(t)\to f(t_k)$ by letting $f_k\equiv f(t_k)$, where $t_k\equiv k\Delta$, with $k=0$, ..., $N-1$. Choose the frequency step such that

$$\nu_n={n\over N\Delta},$$ (2)

with $n=-N/2$, ..., 0, ..., $N/2$. There are $N+1$ values of $n$, so there is one relationship between the frequency components. Writing this out as per Press et al. (1989)

$${\mathcal F}[f(t)] =\sum_{k=0}^{N-1} f_ke^{-2\pi i(n/N\Delta)k\Delta}\Delta = \Delta\sum_{k=0}^{N-1} f_k e^{-2\pi i nk/N},$$ (3)

and

$$F_n\equiv \sum_{k=0}^{N-1} f_ke^{-2\pi i nk/N}.$$ (4)

The inverse transform is

$$f_k={1\over N}\sum_{n=0}^{N-1} F_n e^{2\pi ink/N}.$$ (5)

Note that $F_{-n}=F_{N-n}$, $n=1$, 2, ..., so an alternate formulation is

$$\nu_n={n\over N\Delta},$$ (6)

where the Negative frequencies $-\nu_c<\nu<0$ have $N/2+1\leq n\leq N-1$, Positive frequencies $0<\nu<\nu_c$ have $1\leq n\leq N/2-1$, with zero frequency $n=0$. $n=N/2$ corresponds to both $\nu=\nu_c$ and $\nu=-\nu_c$. The discrete Fourier transform can be computed using a Fast Fourier Transform.

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

See also Fast Fourier Transform, Fourier Transform, Hartley Transform, Winograd Transform, z-Transform

References

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.