7
Fast Fourier Transform and Its
Applications
Frequency analysis of digital signals and systems was discussed in Chapter 4. To per-
form frequency analysis on a discrete-time signal, we converted the time-domain
sequence into the frequency-domain representation using the z-transform, the
discrete-time Fourier transform (DTFT), or the discrete Fourier transform (DFT). The
widespread application of the DFT to spectral analysis, fast convolution, and data
transmission is due to the development of the fast Fourier transform (FFT) algorithm
for its computation. The FFT algorithm allows a much more rapid computation of the
DFT, was developed in the mid-1960s by Cooley and Tukey.
It is critical to understand the advantages and the limitations of the DFT and how to
use it properly. We will discuss the important properties of the DFT in Section 7.1. The
development of FFT algorithms will be covered in Section 7.2. In Section 7.3, we will
introduce the applications of FFTs. Implementation considerations such as computa-
tional issues and finite-wordlength effects will be discussed in Section 7.4. Finally,
implementation of the FFT algorithm using the TMS320C55x for experimental purposes
will be given in Section 7.5.
7.1 Discrete Fourier Transform
As discussed in Chapter 4, we perform frequency analysis of a discrete-time signal x(n)
using the DTFT defined in (4.4.4). However, X! is a continuous function of frequency
! and the computation requires an infinite-length sequence x(n). Thus the DTFT cannot
be implemented on digital hardware. We define the DFT in Section 4.4.3 for N samples
of x(n) at N discrete frequencies. The input to the N-point DFT is a digital signal
containing N samples and the output is a discrete-frequency sequence containing N
samples. Therefore the DFT is a numerically computable transform and is suitable for
DSP implementations.
Real-Time Digital Signal Processing. Sen M Kuo, Bob H Lee
Copyright # 2001John Wiley & Sons Ltd
ISBNs: 0-470-84137-0 (Hardback); 0-470-84534-1 (Electronic)