9.3.3 Discrete Fourier Transform

The next step is to extract spectral information for our windowed signal; we need to know how much energy the signal contains at different frequency bands. The tool for

extracting spectral information for discrete frequency bands for a discrete-time (sampled) signal is the Discrete Fourier Transform or DFT.

The input to the DFT is a windowed signal $ x[n]...x[m] $, and the output, for each of N discrete frequency bands, is a complex number $ X[k] $ representing the magnitude and phase of that frequency component in the original signal. If we plot the magnitude against the frequency, we can visualize the spectrum that we introduced in Ch. 7. For example, Fig. 9.12 shows a 25 ms Hamming-windowed portion of a signal and its spectrum as computed by a DFT (with some additional smoothing).

We will not introduce the mathematical details of the DFT here, except to note that Fourier analysis in general relies on Euler's formula:

$$ e^{j\theta}=\cos\theta+j\sin\theta $$

As a brief reminder for those students who have already had signal processing, the DFT is defined as follows:

$$ X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\frac{\pi}{N}kn} $$

A commonly used algorithm for computing the DFT is the the Fast Fourier Transform or FFT. This implementation of the DFT is very efficient, but only works for values of N which are powers of two.