A derivation of the discrete Fourier transform

In mathematics, computer science, and electrical engineering, the discrete Fourier transform (DFT), occasionally called the finite Fourier transform, is a transform for Fourier analysis of finite-domain discrete-time signals. As with most Fourier analysis, it expresses an input function in terms of a sum of sinusoidal components by determining the amplitude and phase of each component. Unlike the Fourier Transform, which operates upon continuous functions assumed to extend to infinity, the DFT operates upon "discrete" and "finite" sets of values: the input to the DFT is a finite sequence of real or complex numbers, which makes the DFT ideal for processing information stored in computers. In particular, the DFT is widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, to solve partial differential equations, and to perform other operations such as convolutions.

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$

but does not explain how the equations were derived.

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:

:

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\}cdotsum\_\{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).,$

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:

:

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).,$.

References

* [http://ccrma.stanford.edu/~jos/mdft/mdft.html Mathematics of the Discrete Fourier Transform by Julius O. Smith III ]