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 4of 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 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