A derivation of the discrete Fourier transform

From Wikipedia, the free encyclopedia

The article discrete Fourier transform simply defines the transform as:

$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i \frac{2 \pi}{N} k n} \quad \quad k = 0, \dots, N-1$

In the context of signal processing, the motivation for the DFT is usually based on its close relationship to the actual Fourier transform of a signal that has been digitized. This article explores that relationship. The derivation below is an abbreviated and modified version of discrete-time Fourier transform.

When the sequence $\{x_n\}\,$ represents a subset of the samples of a waveform $x(t)\,$ , we can model the process that created $\{x_n\}\,$ as applying a window function to $x(t)\,$ , followed by sampling (or vice versa). It is instructive to envision what those operations do to the Fourier transform, $X(f)\,$ . The window function widens every frequency component of $X(f)\,$ in a way that depends on the type of window used. That effect is called spectral leakage. We can think of it as causing $X(f)\,$ to blur... thus a loss of resolution. The sampling operation causes the Fourier transform to become periodic. Copies of the blurred $X(f)\,$ are repeated at regular multiples of the sampling frequency, $F_s\,$ , and summed together where they overlap. The copies are aliases of the original frequency components. In particular, due to the overlap, aliases can significantly distort the region containing the original $X(f)\,$ (if $F_s\,$ is not sufficiently large enough to prevent it). But if the windowing and sampling are done with sufficient care, the Fourier transform still contains a reasonable semblance of $X(f)\,$ . The transform is defined as:

$S(f)\,$	$= \int\limits_{-\infty}^{\infty} \; e^{-i 2 \pi f t}\cdot \Bigg [\sum_{n=0}^{N-1} x_n\cdot \delta (t -\frac{n}{F_s})\Bigg ] d t\,$
	$= \sum_{n=0}^{N-1} x_n\cdot \Bigg [\int\limits_{-\infty}^{\infty} \; e^{-i 2 \pi f t}\cdot \delta (t -\frac{n}{F_s}) d t\Bigg ]\,$
	$= \sum_{n=0}^{N-1} x_n\cdot e^{-i 2 \pi \begin{matrix} \frac{f}{F_s} \end{matrix} n}\,$

This continuous Fourier transform is valid for all frequencies, including the discrete subset:

$f_k = \frac{k}{N}{F_s} \quad \quad k = 0, \dots, N-1$

One thing to note about this subset is that the width of the region it spans is $F_s\,$ , which is the periodicity of $S(f)\,$ . So there is no need for more frequencies at this spacing $(\frac{F_s}{N})\,$ .

Another thing to notice is that: $S(f_k) = X_k\,$ . So the DFT coefficients are a subset of the actual (continuous) Fourier transform of the windowed and sampled waveform. And we note that periodicity of the time-samples has not been assumed. In fact up to this point, it is specifically in contradiction with the assumed window function.

Obviously, the original $x_n\,$ sequence can be recovered from $S(f)\,$ by doing an inverse Fourier transform. But remarkably, it can also be shown that:

$x_n = \frac{1}{N}\cdot\sum_{k=0}^{N-1} X_k \cdot e^{i \frac{2 \pi}{N} k n} \quad \quad n = 0, \dots, N-1$

which is the inverse discrete Fourier transform. Thus, the DFT coefficients preserve all of the original information, except one thing:

The original $x_n\,$ sequence was windowed, whereas this function is periodic (if we were to allow values of n outside the range shown). In the frequency domain it is the difference between a continuous function, $S(f)\,$ , and a discrete one, $X_k\,$ .

These are all good reasons why we are normally content to work with $\{X_k\} = \{S(f_k)\}\,$ instead of the more cumbersome $S(f)\,$ . We just have to be careful about the significance we attach to the apparent periodicity of the inverse transform. If the original $x_n\,$ sequence was periodic (and of course not windowed), then $S(f)\,$ would be zero in between the DFT frequencies, and the periodicity of the inverse DFT would have significance. Otherwise it is just an artifact of substituting $\{S(f_k)\}\,$ for $S(f).\,$

[edit] Discrete Time Fourier Transform

For completeness, we note that with this definition:

$\omega = {2 \pi f \over F_s}\,$

we can also write $S(f)\,$ (now a function of $\omega\,$ ) as:

$X_{dtft}(\omega )\,$	$= \sum_{n=0}^{N-1} x_n\cdot e^{-i \omega n}\,$
	$= \sum_{n=-\infty}^{\infty} x_n\cdot e^{-i \omega n}\,$ , (because of the window function)

which is now recognizable as the discrete-time Fourier transform.

In conclusion, rather than simply presenting the DFT and the DTFT as definitions, we have shown how they can be related back to the continuous Fourier transform of the original continuous signal $x(t).\,$ .