The DFT

• In the second week of the semester, the following formula for the Discrete Fourier Transform (DFT) was given:
    $$X[k] \ensuremath{\stackrel{\Delta}{=}}\sum^{N-1}_{n=0}x[n] e^{-j ... ... N) -j \sin(2 \pi k n / N)\right\}, \hspace{0.2in} k = 0, 1, 2, \ldots, N - 1.$$ (11)

• From the previous discussion, you should now have some intuition on how the DFT works.

• In effect, an inner product is computed of a given discrete-time signal $x[n]$ and $N$ complex exponential signals representing sine and cosine terms at discrete frequencies $2 \pi k / N$. Each of these inner product computations produces a single complex valued “weight” that indicates the relative strength of a specific sinusoidal frequency in the signal.

• Figure 4 shows the first 5 cosine and sine terms of the complex exponential signals used in a length $N=32$ DFT.

  Figure 4: The first 5 cosine and sine terms used in a length $N=32$ DFT.

  

• The frequencies evaluated by the DFT are directly related to the size $N$ of the signal $x[n]$. These frequencies are evenly distributed from 0 to $f_s\frac{N-1}{N}$, so that the larger the value of $N$, the more precise the estimate of frequency content in the signal. However, from the sampling theorem, only those frequency components less than or equal to $f_s/2$ are unique.

• As mentioned earlier in this section, sinusoids are periodic functions. Thus, for a DFT result to perfectly “match” a given signal, the signal $x[n]$ would have to be periodic and only contain frequency components that are integral multiples of $2\pi/N$.

• Remembering that periodic signals must have harmonic spectra, we see that the DFT computes the amplitudes and phases of a harmonic set of sinusoidal components, each having an integer number of periods in $N$ samples.

• If the signal $x[n]$ is not periodic in $N$, the DFT will only provide an approximation of its actual frequency content.