The DFT

For a length $N$ complex sequence $x(n)$ , $n=0,1,2,\ldots,N-1$ , the discrete Fourier transform (DFT) is defined by

$$X(\omega_k) \isdef \sum_{n=0}^{N-1}x(n) e^{-j\omega_k t_n} = \sum_{n=0}^{N-1}x(n) e^{-j 2\pi kn/N}, \quad k=0,1,2,\ldots N-1$$

$$\begin{eqnarray*} t_n &\isdef & nT = \mbox{$n$th sampling instant (sec)} \\ \omega_k &\isdef & k\Omega = \mbox{$k$th frequency sample (rad/sec)} \\ T &\isdef & 1/f_s = \mbox{time sampling interval (sec)} \\ \Omega &\isdef & 2\pi f_s/N = \mbox{frequency sampling interval (rad/sec)} \end{eqnarray*}$$

We are now in a position to have a full understanding of the transform kernel:

$$e^{-j\omega_k t_n} = \cos(\omega_k t_n) - j \sin(\omega_k t_n)$$

The kernel consists of samples of a complex sinusoid at $N$ discrete frequencies $\omega_k$ uniformly spaced between 0 and the sampling rate $\omega_s \isdeftext 2\pi f_s$ . All that remains is to understand the purpose and function of the summation over $n$ of the pointwise product of $x(n)$ times each complex sinusoid. We will learn that this can be interpreted as an inner product operation which computes the coefficient of projection of the signal $x$ onto the complex sinusoid $\cos(\omega_k t_n) + j \sin(\omega_k t_n)$ . As such, $X(\omega_k)$ , the DFT at frequency $\omega_k$ , is a measure of the amplitude and phase of the complex sinusoid which is present in the input signal $x$ at that frequency. This is the basic function of all linear transform summations (in discrete time) and integrals (in continuous time) and their kernels.