Signals and Systems - Electrical Engineering

624 C H A P T E R 10: Fourier Analysis of Discrete-Time Signals and Systems

Givenx[n]andh[n]of lengthsMandK, the linear convolution sumy[n]of lengthN=M+K− 1 can be found

by following these three steps:

n Compute DFTsX[k]andH[k]of lengthL≥Nforx[n]andh[n].

n Multiply them to getY[k]=X[k]H[k].

n Find the inverse DFT ofY[k]of lengthLto obtainy[n].

Although it seems computationally more expensive than performing the direct computation of the convolution

sum, the above approach implemented with the FFT can be shown to be much more efficient.

The above procedure could be implemented by acircular convolution sumin the time domain,

although in practice it is not done due to the efficiency of the implementation with FFTs. A circu-

lar convolution uses circular rather than linear representation of the signals being convolved. The

periodic convolution sumintroduced before is a circular convolution of fixed length—the period of the

signals being convolved. When we use the DFT to compute the response of an LTI system the length

of the circular convolution is given by the possible length of the linear convolution sum. Thus, if the

system input is a finite sequencex[n] of lengthMand the impulse response of the systemh[n] has

a lengthK, then the outputy[n] is given by a linear convolution of lengthM+K−1. The length

L≥M+K−1 of the DFTY[k]=X[k]H[k] corresponds to a circular convolution of lengthLof the

x[n] andh[n] padded with zeros so that both have lengthL. In such a case the circular and the linear

convolutions coincide.

Ifx[n]of lengthMis the input of an LTI system with impulse responseh[n]of lengthK, then

Y[k]=X[k]H[k]⇔y[n]=(x⊗Lh)[n] (10.55)

whereX[k],H[k], andY[k]are, respectively, DFTs of lengthLof the input, the impulse response, and the

output of the LTI system, and⊗Lstands for the circular convolution of lengthL.

IfLis chosen so thatL≥M+K− 1 , the circular and the linear convolution sums coincide—that is,

y[n]=(x⊗Lh)[n]=(x∗h)[n] (10.56)

RemarkIf we consider the periodic expansions of x[n]and h[n]with period L=M+K− 1 , we can use

their circular representations and implement the circular convolution as shown in Figure 10.16. Since the

length of the linear convolution or convolution sum, M+K− 1 , coincides with the length of the circular

convolution, the two convolutions coincide. Given the efficiency of the FFT algorithm in computing the DFT,

the convolution is typically done using the DFT as indicated above.

nExample 10.22

To illustrate the connection between the circular and the linear convolution, compute using MAT-

LAB the circular convolution of a pulse signalx[n]=u[n]−u[n−21] of lengthN=20 with itself

for different values of its length. Determine the length for which the circular convolution coincides

with the linear convolution ofx[n] with itself.