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 presents the definition of the transform, without derivation, as:

(Eq.1)

Here we take the view that the DFT is motivated by a desire to study continuous functions or waveforms and their continuous Fourier transforms using only a finite amount of data. When the sequence {x} represents a subset of the samples of a waveform x(t), we can model the process that created {x} as applying a window function to x(t), followed by sampling (or vice versa). It is instructive to envision how those operations affect our ability to observe the Fourier transform, X(ƒ). The window function widens every frequency component of X(ƒ) 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(ƒ) to blur... thus a loss of resolution. The sampling operation causes the Fourier transform to become periodic. More precisely, what happens is that {x} has no Fourier transform. It is undefined. But using the Poisson summation formula a periodic function of continuous frequency can be constructed from the samples, and it comprises copies of the blurred X(ƒ) repeated at regular multiples of the sampling frequency (F_s = 1/T) and summed together where they overlap (called periodic summation):

(Eq.2)

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(ƒ) (if F_s is not sufficiently large enough to prevent it). But if the windowing and sampling are done with sufficient care, the Poisson summation still contains a reasonable semblance of X(ƒ). It is therefore a common practice to compute an arbitrary number of samples (N) of one cycle of the periodic function :

Since the kernel, is N-periodic, it can readily be shown that this is equivalent to the following DFT:

(Eq.3)

where is a summation over any interval of length N, and is another periodic summation:

Eq.1 (the standard DFT) is just a simplification of Eq.3 when the x sequence is zero outside the interval . But regardless of the duration of the x sequence, the inverse DFT produces the periodic sequence. That can be thought of as a consequence of substituting a discrete set of frequencies for the continuous .