Derivation of the Discrete Fourier Transform (DFT)

The Discrete Fourier Transform (DFT) is a fundamental tool in digital signal processing, enabling the analysis of a finite, discrete-time signal in the frequency domain. Its derivation logically follows from the Discrete-Time Fourier Transform (DTFT) by sampling the continuous frequency spectrum.

The Discrete-Time Fourier Transform (DTFT)

Let us begin with a discrete-time signal, denoted as $x[n]$, where $n$ is an integer. The DTFT of this signal maps the discrete-time domain to a continuous and periodic frequency domain. The DTFT, $X(e^{j\omega})$, is defined by the analysis equation:

$$X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}$$

The resulting spectrum $X(e^{j\omega})$ is a continuous function of the frequency variable $\omega$ and is periodic with a period of $2\pi$.

Sampling in the Frequency Domain

For computation using digital systems, the continuous nature of the frequency variable $\omega$ in the DTFT is impractical. We need a discrete representation of the spectrum. This is achieved by taking a finite number of samples of $X(e^{j\omega})$.

We perform a uniform sampling of one period of the DTFT spectrum, typically over the interval $[0, 2\pi]$. Let’s take $N$ samples, where $N$ is a positive integer. The sampling points for the frequency $\omega$ are given by:

$$\omega_k = \frac{2\pi k}{N}, \quad \text{for } k = 0, 1, 2, \ldots, N-1$$

By evaluating the DTFT at these discrete frequency points, we obtain the discrete frequency samples, which we denote as $X[k]$:

$$X[k] = X(e^{j\omega}) \Big|_{\omega = \omega_k} = \sum_{n=-\infty}^{\infty} x[n] e^{-j \left(\frac{2\pi k}{N}\right) n}$$

Assumption of Finite-Length Signals

The summation in the above equation still runs from $n = -\infty$ to $\infty$. For a practical transform, we must operate on a finite-length signal. We assume that the signal $x[n]$ is of finite length $N$, i.e., $x[n]$ is non-zero only for $n = 0, 1, 2, \ldots, N-1$.

If the original signal is longer than $N$, it can be truncated or windowed. If it is shorter, it can be zero-padded to length $N$. This assumption allows us to change the limits of the summation:

$$\sum_{n=-\infty}^{\infty} \quad \longrightarrow \quad \sum_{n=0}^{N-1}$$

The DFT Formula

By applying this finite-length assumption to the sampled DTFT, we arrive at the definition of the $N$-point Discrete Fourier Transform (DFT):

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi k n}{N}}, \quad \text{for } k = 0, 1, \ldots, N-1$$

This is the final analysis equation for the DFT. It transforms an $N$-point sequence in the time domain, $x[n]$, into an $N$-point sequence in the frequency domain, $X[k]$.

The Inverse DFT (IDFT)

To complete the transform pair, we can also derive the Inverse Discrete Fourier Transform (IDFT), which reconstructs the time-domain signal $x[n]$ from its frequency-domain representation $X[k]$. The IDFT is given by:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi k n}{N}}, \quad \text{for } n = 0, 1, \ldots, N-1$$

This synthesis equation is derived using the orthogonality property of the complex exponential basis functions. Together, these equations form the DFT pair, which is central to many digital signal processing algorithms.