Discrete Fourier transform - Continuous and Discrete Time Signals and Systems - page 525

CHAPTER

12

Discrete Fourier transform

In Chapter 11, we introduced the discrete-time Fourier transform (DTFT) that
provides us with an alternative representation for DT sequences. The DTFT
transforms a DT sequence x [ k ] into a function X ( Ω ) in the DTFT frequency
domain Ω . The independent variable Ω is continuous and is confined to the
range - π ≤ Ω <π . With the increased use of digital computers and special-
ized hardware in digital signal processing (DSP), interest has focused around
transforms that are suitable for digital computations. Because of the continuous
nature of Ω , direct implementation of the DTFT is not suitable on such digital
devices. This chapter introduces the discrete Fourier transform (DFT), which
can be computed efficiently on digital computers and other DSP boards.
The DFT is an extension of the DTFT for time-limited sequences with an
additional restriction that the frequency Ω is discretized to a finite set of values
given by Ω = 2 π r / M , for 0 ≤ r ≤ ( M − 1). The number M of the frequency
samples can have any value, but is typically set equal to the length N of the time-
limited sequence x [ k ]. If M is chosen to be a power of 2, then it is possible to
derive highly efficient implementations of the DFT. These implementations are
collectively referred to as the fast Fourier transform (FFT) and, for an M -point
DFT, have a computational complexity of O( M log 2 M ). This chapter discusses
a popular FFT implementation and extends the theoretical DTFT results derived
in Chapter 11 to the DFT.
The organization of this chapter is as follows. Section 12.1 motivates the
discussion of the DFT by expressing it as a special case of the continuous-time
Fourier transform (CTFT). The formal definition of the DFT is presented in
Section 12.2, including its matrix-vector representation. Section 12.3 applies the
DFT to estimation of the spectra of both DT and CT signals. Section 12.4 derives
important properties of the DFT, while Section 12.5 uses the DFT as a tool to
convolve two DT sequences in the frequency domain. A fast implementation of
the DFT based on the decimation-in-time algorithm is presented in Section 12.6.
Finally, Section 12.7 concludes the chapter with a summary of the important
concepts.

525