Signals and Systems - Electrical Engineering

720 CHAPTER 12: Applications of Discrete-Time Signals and Systems

FIGURE 12.3

CPU times for thefftand the

dftfunctions used in

computing the DFT of

sequences of ones of lengths

N= 256 to 2048

(corresponding ton=8,... 11 ).

The CPU time for the FFT is

multiplied by 104.

8 8.5 9 9.5 10 10.5 11

0

100

200

300

400

500

600

700

800

n=log 2 (N)

CPU Time (sec)

104 fft time

dft time

W = ones(1,N);

for k = 1:N - 1,

W = [W; exp(-j∗ 2 ∗pi∗n∗k/N)];

end

X = W∗x;

The results of the comparison are shown in Figure 12.3. Notice that to make the Computer Pro-

cessing Unit (CPU) time for the FFT comparable with that of thedftalgorithm, it is multiplied

by 10^4 , illustrating how much faster the FFT is compared to the computation of the DFT from its

definition. n

nExample 12.4

The convolution sum is computationally very expensive. Compare the CPU time used by the MAT-

LAB functionconv, which is used to compute the convolution sum in the time domain, with the

CPU time used by an implementation of the convolution sum in frequency using the FFT. Recall

that the frequency implementation requires computing the DFT of the signals being convolved,

their multiplication, and finally the computation of the IDFT to the final convolution result.

Solution

To illustrate the efficiency in computation provided by the FFT in computing the convolu-

tion sum we compare the CPU times used by theconvfunction and the implementation of

the convolution sum using the FFT. As indicated before, the convolution of two signalsx[n],