Lecture 10 Solutions: Circular Convolution

CIRCULAR CONVOLUTION Solution 10.1 It is straightforward to see graphically that the maximum possible length of the linear convolution is 2N-l. Alternatively, (a) h(n - y(n) = Ex(k) k) k=-o x(k) is zero outside the range 0 < k < N - 1 and h(n - k) is zero outside the range -N + 1 + n < k < n. These two intervals overlap only for 0 < n < 2N - 2, and consequently y(n) must be zero outside that range. (b) The circular convolution of two sequences of length N has a maximum length of N. This can be seen in a number of ways. For example, the circular convolution corresponds to extracting one period of the Since the periodic convolution periodic convolution of x(n) and h(n). is periodic with period N, each period is of maximum length N. Solution 10.2 (a) 21 2 0 1 2 3 4 5 6 x 1 (n) = x(n) I a4 7 8 * x(n) 9 Figure SlO.2-1 We can obtain the four-point circular convolution by "aliasing" the linear convolution. Thus (b) x(n) x1 (n + 4r)] R4 (n) x(n) =[[ r=-o x (n) @ x(n) 21 2 27 2 14 21 -l 0 1 2 3 4 Figure S10.2-2 S10.1 (c) The ten-point circular convolution can be obtained in the same way. In this case, however, since x 1 (n) is of length 7, the delayed replicas of x1 (n) in the "aliasing" equation do not overlap. Thus x(n) (0 x(n) is identical to the linear convolution as obtained in (a). The circular convolution will be identical to the linear convolution if the delayed replicas of the linear convolution have no non-zero values overlapping. For this specific example that will be the case for N > 9. More generally, from problem 10.1 (a) we know that the linear (d) convolution of an N 1 point sequence with itself will have a maximum length (2N - 1) and consequently the (2N - 1) point circular convolution of an N-point sequence with itself will be identical to the N-point linear convolution. Solution 10.3 This is most easily done by again considering circular convolution In the figure below we indicate as "linear convolution plus aliasing." Since x(n) is of length 8 the linear convolution of x(n) and y(n). and y(n) is of length 20, the linear convolution, which we'll denote by w(n) is of length 27. w(n) a p 0 26 Figure S10.3-1 The 20-point circular convolution can be obtained by adding w(n) delayed by integer multiples of 20, and then extracting the first 20 points. From Figure S10.3-2 we observe that in the interval 0 < n < 19 there is aliasing only in the first seven points. The remaining thirteen points, i.e. for 8 < n < 20 the points in the linear convolution remain undisturbed. Thus it is these points in r(n) that correspond to points that would be obtained in a linear convolution of x(n) and y(n). S10.2 -.. w(n) 0 26 w(n -20) 20 a a a 1 -20 6 46 w(n + 20) . . Figure S10.3-2 Solution 10.4* The linear convolution of the unit-sample response with an input section is of length 149. In the 128-point circular convolution the first 49 points are "aliased" and the remaining 79 points correspond to a linear convolution of the unit-sample response and the input section. However because the length of the DFT was greater than the length of the input section, the section was augmented with 28 zeros. Thus the last 28 points could not simply be abutted with the results from previous sections. Hence in the circular convolution the first 49 points and the last 28 points must be discarded. The input sections are then overlapped by 49 points and the 51 points indexed from 49 through 99 are abutted with the corresponding points from the preceding section. Solution 10.5* (a) H(k) = 1 (b) Hk(k) letting k = (k) * WN 0 1--- W 2 N n + 4r, 0 k=0 H1 (k) can be rewriten as + ()n+4r = n=0 or, since _kn0 1 N 1 kn = 3 H - WN kn (n+4r) 0 r=0 N = 4n 0 , WNknO4r = 1 and S10.3 WNknn H (k) = n 1 4r 0 r=O n=0 3 kn n 1 )WN n=o Therefore h (n) = [6 (n) + 6(n - n0 ) + 1 6(n - 3n (c) and (d) It is straightforward to see that the linear convolution of h(n) with h1 (n) is not a unit-sample and hence h1 (n) is not the unit-sample response of the inverse system. The circular convolutiun H(k) of h(n) with h (n) is however a unit-sample since H (k) _1 1 (e) H(z) = 1 - 1 n z-n n0 -nO_ H (z) 1- z -n) 0 n=0 6(n - Therefore h (n) = kn 0 ktto (f) h (n) as determined in part (b) is an aliased version of h (n), 1 1 h h 1 (n) = (n - rN)1 RN(n) r=-o This can be interpreted in terms of the fact that H1 (k) corresponds to sampling H (z) on the unit circle. This sampling in the frequency domain corresponds to aliasing in the time domain. S10. 4 i.e.