The Discrete Fourier Transform (DFT)

• Given a discrete-time signal $x[n]$, we can determine its frequency response using the Discrete Fourier Transform (DFT):
  $$X[k] \ensuremath{\stackrel{\Delta}{=}}\sum^{N-1}_{n=0}x[n] e^{-j 2 \pi k n / N}, \hspace{0.2in} k = 0, 1, 2, \ldots, N - 1.$$

• The complementary inverse DFT is given by:
  $$x[n] = \frac{1}{N} \sum^{N-1}_{k=0}X[k] e^{j 2 \pi k n / N}, \hspace{0.2in} n = 0, 1, 2, \ldots, N - 1.$$

• The DFT can be interpreted as the sum of projections of $x[n]$ onto a set of $N$ sampled complex sinusoids or sinusoidal basis functions at (normalized) radian frequencies given by $\omega_k = 2 \pi k / N$ with $k = 0, 1, 2, \ldots, N - 1$.

• In this way, the DFT and its inverse provide a “recipe” for reconstructing a given discrete-time signal in terms of sampled complex sinusoids.

• Various computational tools exist that allow for the transformation of a discrete-time signal into its frequency-domain representation.