Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341:DISCRETE-TIME SIGNAL PROCESSING OpenCourse Ware 2006 Lecture 16 Linear Filtering with the DET Reading:Sections 8.6 and 8.7 in Oppenheim,Schafer Buck (OSB). Circular Convolution xIn]and h[n]are two finite sequences of length N with DFTs denoted by X[k]and H[k], respectively.Let us form the product W [k=X [k]H[k], and determine the sequence wn]of length N for which the DFT is W[k]. First,extend x[n]and h[n]to periodic sequences with period N,n]and hin],respectively. Then,the periodic convolution of n]and hn corresponds to multiplication of the correspond- ing periodic sequences of Fourier series coefficients(see OSB section 8.2.5). N-1 m=∑mn-m[因=X因因 m=0 The periodic sequence wn]for which the DFS coefficients are W[k]corresponds to the periodic extension of the finite length sequence wln]with period N.We can recover w[n]by extracting one period of wn]: win]wn RNIn] N-1 imlhin-m] m=0 N ∑mh(n-m)N m=0 This operation is called circular convolution and denoted wln]=xin]hinj. 1
� Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing OpenCourseWare 2006 Lecture 16 Linear Filtering with the DFT Reading: Sections 8.6 and 8.7 in Oppenheim, Schafer & Buck (OSB). Circular Convolution x[n] and h[n] are two finite sequences of length N with DFTs denoted by X[k] and H[k], respectively. Let us form the product W[k] = X[k]H[k], and determine the sequence w[n] of length N for which the DFT is W[k]. First, extend x[n] and h[n] to periodic sequences with period N, x h ˜[n] and [n], respectively. ˜ Then, the periodic convolution of x h ˜[n] and [n] corresponds to multiplication of the correspond- ˜ ing periodic sequences of Fourier series coefficients (see OSB section 8.2.5). N−1 w ˜ ˜ ˜ ˜ [n] = � ˜ ˜[ x n]h[n − m] ↔ W[k] = X[k]H[k] m=0 The periodic sequence ˜[n] for which the DFS coefficients are w W˜ [k] corresponds to the periodic extension of the finite length sequence w[n] with period N. We can recover w[n] by extracting one period of w˜[n]: w[n] = w˜[n]RN [n] N−1 ˜ = � x ˜ [m]h[n − m] m=0 N−1 = � x[m]h[((n − m))N ] m=0 This operation is called circular convolution and denoted w[n] = x[n] N h[n]. 1
Example: Consider two constant sequences of length N,1[n]=z2[n],depicted in OSB Figure 8.15(a) and (b). The N-point DFT of z1[n]is, x内=∑w-w=-w N-1 W-1 1-W =0k卡0 =Nk=0 where WN=e-i(2/N).Since ri[n]z2[n], X3[=X[X2附=N26[=NX[ Using linearity,we can see that x3m=xm回x2n=Nxln=N0≤n≤N-1 =0 otherwise The N-point circular convolution of i[n]and z2[n]is depicted in OSB Figure 8.15(c). Example: Now,consider z1In]=r2[n]as 2L-point sequences by augmenting them with L zeros as shown in OSB Figure 8.16(a)and (b). Performing a 2L-point circular convolution of the sequences,we get the sequence in OSB Figure 8.16(e),which is equal to the linear convolution of i[n]and z2[n]. Circular Convolution as Linear Convolution with Aliasing We know that convolution of two sequences corresponds to multiplication of the corresponding Fourier transforms: y[n]=x[n]*h[n]Y(ex)=X(e)H(ej) If we define a DFT Y[=Y(e(2πk/N),0≤k≤N-1, it follows that Y[=X(e2mkN)H(eJ2mkN)=X[H[,0≤k≤N-1. 2
� Example: Consider two constant sequences of length N, x1[n] = x2[n], depicted in OSB Figure 8.15(a) and (b). The N-point DFT of x1[n] is, N−1 N−1 1 − WNK Wkn = � Wkn = X N 1[k] = � x1[n] N N = 0 k = 0 1 − Wk � 0 0 N = N k = 0 = e−j(2π/N) where WN . Since x1[n] = x2[n], X3[k] = X1[k]X2[k] = N2δ[k] = NX1[k] Using linearity, we can see that x3[n] = x1[n] N x2[n] = Nx1[n] = N 0 ≤ n ≤ N − 1 = 0 otherwise. The N-point circular convolution of x1[n] and x2[n] is depicted in OSB Figure 8.15(c). Example: Now, consider x1[n] = x2[n] as 2L-point sequences by augmenting them with L zeros as shown in OSB Figure 8.16(a) and (b). Performing a 2L-point circular convolution of the sequences, we get the sequence in OSB Figure 8.16(e), which is equal to the linear convolution of x1[n] and x2[n]. Circular Convolution as Linear Convolution with Aliasing We know that convolution of two sequences corresponds to multiplication of the corresponding Fourier transforms: jω)H(ejω y[n] = x[n] [n] Y (e ) jω ∗ h ↔ ) = X(e If we define a DFT Y [k] = Y (ej(2πk/N) ), 0 ≤ k ≤ N − 1, it follows that Y [k] = X(ej(2πk/N) )H(ej(2πk/N) ) = X[k]H[k], 0 ≤ k ≤ N − 1. 2
From our definition of the circular convolution w[n],Wk]=Xk H[k],so W [k]=Y [k]. If xIn]and hin]are sequences of length N,then wIn]has length N,but yn]has the maximum length of(2N-1).In order to calculate the N-point DFT ofyn],we first form a periodic sequence of period N as follows: 00 m=∑n-rN] T=-00 From the last lecture on the DFT,it follows that Yk](=W[k])is the DFT of one period of n].Thus,the circular convolution of two finite-length sequences is equivalent to the linear convolution of the two sequences,followed by time aliasing. wl=i(n]Rw(n]=∑ln-rW 0≤n≤N-1 =0 otherwise Example: Consider two identical sequences 1n]and x2n]of length L in OSB Figure 8.18(a).The linear convolution of the two sequences is shown in OSB Figure 8.18(b).OSB Figure 8.18(c) and(d)show two of the shifted versions of(b).The L-point circular convolution of iln] and z2[n]is shown in OSB Figure 8.18(e),which can be formed by summing (b),(c),and (d)in the interval0≤n≤L-1. Since the length of the linear convolution is(2L-1),the result of the 2L-point circular con- volution in OSB Figure 8.18(f)is identical to the result of linear convolution. Now,consider two finite-duration sequences i[n]and z2[n],with zi[n]of length L,and x2[n] of length P<L as illustrated in OSB Figure 8.19.Let z3[n]be the linear convolution of [n] and z2nj. To determine the L-point circular convolution z3[n],we use the time-aliasing interpretation: 3pm=xm⊙x2nl=∑x3m-r,0≤n≤L-1, r=-00 =0, otherwise. OSB Figure 8.20 shows the terms for (a)r =0,(b)r=-1,and (c)r =1.When the terms are summed to calculate the circular convolution in OSB Figure 8.20(d),the last (P-1)points 3
� From our definition of the circular convolution w[n], W[k] = X[k]H[k], so W[k] = Y [k]. If x[n] and h[n] are sequences of length N, then w[n] has length N, but y[n] has the maximum length of (2N-1). In order to calculate the N-point DFT of y[n], we first form a periodic sequence of period N as follows: ∞ y˜[n] = � y[n − rN] r=−∞ From the last lecture on the DFT, it follows that Y [k] (= W[k]) is the DFT of one period of y˜[n]. Thus, the circular convolution of two finite-length sequences is equivalent to the linear convolution of the two sequences, followed by time aliasing. ∞ w[n] = y˜[n]RN [n] = � y[n − rN] 0 ≤ n ≤ N − 1 r=−∞ = 0 otherwise Example: Consider two identical sequences x1[n] and x2[n] of length L in OSB Figure 8.18(a). The linear convolution of the two sequences is shown in OSB Figure 8.18(b). OSB Figure 8.18(c) and (d) show two of the shifted versions of (b). The L-point circular convolution of x1[n] and x2[n] is shown in OSB Figure 8.18(e), which can be formed by summing (b), (c), and (d) in the interval 0 ≤ n ≤ L − 1. Since the length of the linear convolution is (2L-1), the result of the 2L-point circular convolution in OSB Figure 8.18(f) is identical to the result of linear convolution. Now, consider two finite-duration sequences x1[n] and x2[n], with x1[n] of length L, and x2[n] of length P < L as illustrated in OSB Figure 8.19. Let x3[n] be the linear convolution of x1[n] and x2[n]. To determine the L-point circular convolution x3p [n], we use the time-aliasing interpretation: ∞ x3p [n] = x1[n] L x2[n] = � x3[n − rL], 0 ≤ n ≤ L − 1, r=−∞ = 0, otherwise. OSB Figure 8.20 shows the terms for (a) r = 0, (b) r = −1, and (c) r = 1. When the terms are summed to calculate the circular convolution in OSB Figure 8.20(d), the last (P-1) points 3
of x3[n+L]will be added to the first (P-1)points of x3[n]. We can alternatively view the process of forming the circular convolution x3[n as wrapping the linear convolution x3[n around a cylinder of circumference L.As shown in OSB Figure 8.21,the first (P-1)points are corrupted by time aliasing,and the points from n=P-1 to n =L-1 are identical to the corresponding points of the linear convolution. As shown in OSB Figure 8.21,it is clear that time aliasing in the circular convolution can be avoided if N,the length of the DFT,is larger than or equal to (L+P-1). Block Convolution In lecture 19,we will learn highly efficient algorithms for computing the DFT.Because of these algorithms,it is computationally efficient to implement a linear convolution of two sequences by computing the DFTs,multiplying them,and computing the IDFT.Since multiplying the DFTs corresponds to circular convolution of the corresponding sequences,we must avoid time aliasing to recover linear convolution from the result of the IDFT. Consider an input data xn]of length N,and an FIR filter h[n]of length P.The linear convolu- tion of the two sequences has length(N+P-1).To avoid time aliasing,the DFT length must be at least (N+P-1).However,in many applications,such as filtering a speech waveform,the length of the input data is of indefinite duration as depicted in OSB Figure 8.22.Computing the DFT of the entire input signal in this case can be impractical,and will cause a long delay since we need all samples of the input before filtering.The solution is to use block convolution, in which the input signal is segmented into sections of length L.Then,we can use the DFT to convolve each section with the FIR.and get the desired linear convolution by fitting the filtered sections. Overlap-add Method First,segment the input signal into sections of L,and convolve each section with the FIR of length P.The linear convolution of one section of the input and the FIR will result in a sequence y[n]of length (L+P-1).Therefore,we can use the DFT of length (L+P-1)to compute the convolution without time aliasing.As shown in OSB Figure 8.23,the nonzero points in the filtered sections will overlap by (P-1)points,and these overlap points should be added together to construct the output.This procedure is called overlap-add method. Overlap-save Method In the overlap-add method,after computing each section,we need to store (P-1)values of y[n]and and wait for the next data segment to add overlapped points.In cases this is not 4
of x3[n + L] will be added to the first (P − 1) points of x3[n]. We can alternatively view the process of forming the circular convolution x3p [n] as wrapping the linear convolution x3[n] around a cylinder of circumference L. As shown in OSB Figure 8.21, the first (P − 1) points are corrupted by time aliasing, and the points from n = P − 1 to n = L − 1 are identical to the corresponding points of the linear convolution. As shown in OSB Figure 8.21, it is clear that time aliasing in the circular convolution can be avoided if N, the length of the DFT, is larger than or equal to (L + P − 1). Block Convolution In lecture 19, we will learn highly efficient algorithms for computing the DFT. Because of these algorithms, it is computationally efficient to implement a linear convolution of two sequences by computing the DFTs, multiplying them, and computing the IDFT. Since multiplying the DFTs corresponds to circular convolution of the corresponding sequences, we must avoid time aliasing to recover linear convolution from the result of the IDFT. Consider an input data x[n] of length N, and an FIR filter h[n] of length P. The linear convolution of the two sequences has length (N +P −1). To avoid time aliasing, the DFT length must be at least (N +P −1). However, in many applications, such as filtering a speech waveform, the length of the input data is of indefinite duration as depicted in OSB Figure 8.22. Computing the DFT of the entire input signal in this case can be impractical, and will cause a long delay since we need all samples of the input before filtering. The solution is to use block convolution, in which the input signal is segmented into sections of length L. Then, we can use the DFT to convolve each section with the FIR, and get the desired linear convolution by fitting the filtered sections. Overlap-add Method First, segment the input signal into sections of L, and convolve each section with the FIR of length P. The linear convolution of one section of the input and the FIR will result in a sequence y[n] of length (L + P − 1). Therefore, we can use the DFT of length (L + P − 1) to compute the convolution without time aliasing. As shown in OSB Figure 8.23, the nonzero points in the filtered sections will overlap by (P − 1) points, and these overlap points should be added together to construct the output. This procedure is called overlap-add method. Overlap-save Method In the overlap-add method, after computing each section, we need to store (P − 1) values of y[n] and and wait for the next data segment to add overlapped points. In cases this is not 4
desirable,we can use an alternative method,overlap-save method. In OSB Figure 8.21,we saw that in a circular convolution not all points are corrupted by time aliasing.The first(P-1)points of each segment are time aliased,but we have L-(P-1)= (L-P+1)points that are equal to the linear convolution.Therefore,as shown in OSB Figure 8.24,the portion of each output section in the region 0<n P-2 is discarded,and the remaining samples are saved to construct the final filtered output
desirable, we can use an alternative method, overlap-save method. In OSB Figure 8.21, we saw that in a circular convolution not all points are corrupted by time aliasing. The first (P − 1) points of each segment are time aliased, but we have L − (P − 1) = (L − P + 1) points that are equal to the linear convolution. Therefore, as shown in OSB Figure 8.24, the portion of each output section in the region 0 ≤ n ≤ P − 2 is discarded, and the remaining samples are saved to construct the final filtered output. 5
