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)} \\ \om... ...sdef & 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.