5.6 Discrete fourier transforms (dft)

The discrete-time Fourier transform (and the continuous-time transform as well) can be evaluated when we havean analytic expression for the signal. Suppose we just have a signal, such as the speech signal used in the previous chapter,for which there is no formula. How then would you compute the spectrum? For example, how did we compute a spectrogram such asthe one shown in the speech signal example ? The Discrete Fourier Transform (DFT) allows the computation of spectra fromdiscrete-time data. While in discrete-time we can exactly calculate spectra, for analog signals no similar exact spectrum computation exists. Foranalog-signal spectra, use must build special devices, which turn out in most cases to consist of A/D converters anddiscrete-time computations. Certainly discrete-time spectral analysis is more flexible than continuous-time spectralanalysis.

The formula for the DTFT is a sum, which conceptually can be easily computed save for twoissues.

• Signal duration . The sum extends over the signal's duration, which must befinite to compute the signal's spectrum. It is exceedingly difficult to store an infinite-length signal in any case, sowe'll assume that the signal extends over $\left[0 , N-1\right]$ .
• Continuous frequency . Subtler than the signal duration issue is the fact that the frequencyvariable is continuous: It may only need to span one period, like $\left[-\left(\frac{1}{2}\right) , \frac{1}{2}\right]$ or $\left[0 , 1\right]$ , but the DTFT formula as it stands requires evaluating thespectra at all frequencies within a period. Let's compute the spectrum at a few frequencies; themost obvious ones are the equally spaced ones $f=\frac{k}{K}$ , $k\in \{0, \dots , K-1\}$ .

We thus define the discrete Fourier transform (DFT) to be

We can compute the spectrum at as many equally spaced frequencies as we like. Note that you can think about thiscomputationally motivated choice as sampling the spectrum; more about this interpretation later. The issue nowis how many frequencies are enough to capture how the spectrum changes with frequency. One way of answering this question isdetermining an inverse discrete Fourier transform formula: given $S(k)$ , $k=\{0, \dots , K-1\}$ how do we find $s(n)$ , $n=\{0, \dots , N-1\}$ ? Presumably, the formula will be of the form $s(n)=\sum_{k=0}^{K-1} S(k)e^{\frac{i\times 2\pi nk}{K}}$ . Substituting the DFT formula in this prototype inverse transformyields

Another way to understand this requirement is to use the theoryof linear equations. If we write out the expression for the DFT as a set of linear equations,

By convention, the number of DFT frequency values $K$ is chosen to equal the signal's duration $N$ . The discrete Fourier transform pair consists of