Essentials of Digital Signal Processing

In this chapter, we introduce the discrete Fourier transform (DFT), which may be viewed as an economy class DTFT and is applicable when x[n] is of finite length (or made finite length by windowing). The DFT is one of the most important tools for digital signal processing, especially when we implement it using the efficient fast Fourier transform (FFT) algorithm, discussed in Sec. 9.7. The development of the FFT algorithm in the mid-sixties gave a huge impetus to the area of DSP. The DFT, using the FFT algorithm, is truly the workhorse of modern digital signal processing, and it is nearly impossible to exaggerate its importance. A solid understanding of the DFT is a must for anyone aspiring to work in the digital signal processing field. Not only does the DFT provide a frequency-domain representation of DT signals, it is also useful to numerous other tasks such as FIR filtering, spectral analysis, and solving partial differential equations.

Computation of the Direct and Inverse DTFT

As we saw in Ch. 6, frequency analysis of discrete-time signals involves determination of the discretetime Fourier transform (DTFT) and its inverse (IDTFT). The DTFT analysis equation of Eq. (6.1) yields the frequency spectrum X(Ω) from the time-domain signal x[n], and the synthesis equation of Eq. (6.2) reverses the process and constructs x[n] from X(Ω). There are, however, two difficulties in the implementation of these equations on a digital processor or computer.