Signals and Systems - Electrical Engineering

12.2 Application to Digital Signal Processing 721

andy[n] of lengthsNandMis obtained in the frequency domain by following these three

steps:

n Compute the DFTsX[k],Y[k] ofx[n], andy[n] of lengthM+N−1.

n Multiply these complex DFTs to getX[k]Y[k]=U[k].

n Compute the IDFT ofU[k] corresponding to the convolutionx[n]∗y[n].

Implementing the DFT and the IDFT with the FFT algorithm it can be shown that the computa-

tional complexity of the above three steps is much smaller than that of computing the convolution

sum directly using theconvfunction.

To demonstrate the efficiency of the FFT implementation we consider the convolution of a signal,

for increasing lengths, with itself. The signal is a sequence of ones of increasing length of 1000 to

10,000 samples. The CPU times used by the functionsconvand the FFT three-step procedure are

measured and compared for each of the lengths. The CPU time used byconvis divided by 10 to be

able to plot it with the CPU of the FFT-based procedure shown in the following script. The results

are shown in Figure 12.4.

%%%%%%%%%%%%%

% example 12.4

% conv vs fft

%%%%%%%%%%%%%

time1 = zeros(1,10);time2 = time1;

for i = 1:10,

NN = 1000∗i;

x = ones(1,NN);

FIGURE 12.4
CPU times for thefftand
theconvfunctions when
computing the convolution of
sequences of ones of lengths
N= 1000 to10,000. The CPU
time used byconvis divided
by 10.

0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

× 104

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

Length of Convolution Sum

CPU Time (sec)

fft time

conv time / 10