Review Problems 3 Four FIR Filter Types Four types of FIR linear phase digital filters have coefficients h(n) for 0 n M. They are defined as follows: Type I: h(n) = h(M-n) and M even. Type II: h(n) = h(M-n) and M odd. Type III: h(n) = -h(M-n) and M even. Type IV: h(n) = -h(M-n) and M odd. 1. Two type II filters H1(ejw) and H2(ejw) can be expressed as R1(w)exp(j1(w)) and R2(w)exp(j2(w)) respectively. H3(ejw) is formed as H1(ejw) H2(ejw). (a) For H1(ejw), give expressions for R1(w) and 1(w). (b ) Express the impulse response h3(n) in terms of h1(n) and h2(n). (c) Associated with H3(ejw) and h3(n) are the quantities M3, R3(w), and 3(w). Express 3(w) and M3 in terms of M. Is M3 even or odd ? (d) Express R3(w) in terms of R1(w) and R2(w). Is R3(w) even or odd ? (e) What type of filter is h3(n) ? 2. Linear phase windows for FIR digital filters can have the same four types as the impulse responses described above problem 1. Assume that hd(n) is truncated to have (M+1) coefficients, and has any of the four types described above. (a) If hd(n) is type II, what type of window (type I, II, III, or IV) should be applied, if we want the resulting h(n) to also be type II ? (b) If hd(n) is type III, what type of window (type I, II, III, or IV) should be applied, if we want the resulting h(n) to also be type III ? (c) If hd(n) is a type I lowpass filter and w(n) is type III, what is the DC gain of h(n) ? Does windowing approximately preserve the shape of the passband of hd(n) ? 3. Consider the type II filter. (a) H(ejw) can be expressed as R(w)exp(j(w)) for all w, where R(w) and (w) are real functions of w and R(w) can be positive or negative. Give R(w) and (w). (b) Give the zeroes of H(z) (c) If H(ejw) = H(ejw)exp(j(w)), give H(ejw) in terms of the symbol R(w). (d) Continuing part (c), give a valid phase (w) in terms of the symbols R(w) and (w) such that (w) is an odd function. (e) What types of windows (I, II, III, and/or IV) can be applied to the type II filter ? 4. Consider the type II filter. (a) Is h(n) a shifted version of a zero-phase impulse response ? (b) H(ejw) can be expressed as R(w)exp(j(w)) for all w, where R(w) and (w) are real functions of w and R(w) can be positive or negative. Give R(w) and (w). (c) Give the zeroes of H(z) (d) If H(ejw) = H(ejw)exp(j(w)), give H(ejw) in terms of the symbol R(w). (e) If H(ejw) = H(ejw)exp(j(w)), give a valid phase (w) in terms of the symbols R(w) and (w) such that (w) is an odd function. (f) What types of windows (I, II, III, and/or IV) can be applied to the type II filter ? 5. Given the type II filter of problem 4, (a) Find an efficient expression for y(n) in terms of x(n), by making use of the symmetry condition: h(n) = h(M-n) and M is odd. (b) In the convolution pseudocode below for this filter, allowed values for n in x(n) range from 0 to Nx. Allowed values for n in y(n) range from 0 to Ny. Give Ny in terms of Nx and M. (c) Give A and B (d) Give expressions for C and D. For 0 n Ny y(n) = A For 0 k B C= D= If(0 C Nx) y(n) = y(n) + h(k)x(C ) If(0 D Nx) y(n) = y(n) + h(k)x(D ) End End 6. A highpass type II filter H1(ejw) with parameter M1 has cut-off frequency w1 and can be expressed as H1(ejw) = R1(w)exp(j1(w)). A lowpass type III filter H2(ejw) with parameter M2 has cut-off frequency w2 can be expressed as H2(ejw) = jR2(w)exp(j2(w)). H3(ejw) is formed as H1(ejw) H2(ejw). (a) For H1(ejw), give expressions for R1(w) and 1(w) in terms of M1 . (b) For H2(ejw), give expressions for R2(w) and 2(w) in terms of M2 . (c) Associated with H3(ejw) and h3(n) are the quantities M3, R3(w), and 3(w). Express 3(w) and M3 in terms of M1 and M2 . Is M3 even or odd ? (d) Express R3(w) in terms of symbols R1(w) and R2(w). Is R3(w) even or odd ? (e) What type of filter (LP, BP, HP, or BR) is h3(n) if w1 < w2 ? 7. Given the type IV filter impulse response, h(n), (a) Find an efficient expression for y(n) in terms of x(n), by making use of the symmetry condition: h(n) = -h(M-n) and M is odd. (b) In the convolution pseudocode below for this filter, allowed values for n in x(n) range from 0 to Nx. Allowed values for n in y(n) range from 0 to Ny. Give Ny in terms of Nx and M. (c ) Give A and B (d) Give expressions for C and D. (e) Give an expression for E For 0 n Ny y(n) = A For 0 k B C= D= If(0 C Nx) y(n) = y(n) + h(k)x(C ) If(0 D Nx) y(n) = y(n) + Ex(D ) End End 8. The output y(n) is found as y(n) = h(n)*x(n) where h(n) is a type II filter. (a) Find an efficient expression for y(n) in terms of x(n), by making use of the symmetry condition: h(n) = h(M-n) and M is odd. (b) In the convolution pseudocode below for this filter, allowed values for n in x(n) range from 0 to Nx. Allowed values for n in y(n) range from 0 to Ny. Give Ny in terms of Nx and M. (c ) Give A and B (d) Give expressions for C and D. For 0 k Ny y(n) = A End For 0 k (M-1)/2 For 0 m Nx Z = h(B)x(C) y(k+m) = y(k+m) + Z y(D) = y(D) + Z End End 9. Linear phase windows for FIR digital filters can have the same four types as the impulse responses described above problem 2. Assume that hd(n) is truncated to have (M+1) coefficients, and has any of the four types described above. (a) If hd(n) is type II, what type of window (type I, II, III, or IV) should be applied, if we want the resulting h(n) to also be type II ? (b) If hd(n) is type III, what type of window (type I, II, III, or IV) should be applied, if we want the resulting h(n) to also be type III ? (c) If hd(n) is a type I lowpass filter and w(n) is type III, what is the DC gain of h(n) ? Does windowing approximately preserve the shape of the passband of hd(n) ? FIR Filter Design Using Windows 1. An FIR filter impulse response can be found through windowing as h(n) = hd(n)w(n). (a) Give an expression for H(ejw) in terms of Hd(ejw) and W(ejw). (b) Find h(n) in terms of hd(n) if P is even and P/2 W( e jw ) = 1 + 2 cos(2 n/P) cos(wn) n=1 (c) How many coefficients does h(n) have ? (d) What kind of phase is H(ejw) likely to have ? ( linear or zero) 2. A chirp signal has the form x(n) = sin(an2) for 0 n Nx .For large n, we can write n = no + i where no is constant, i varies, and i << no . (a) If we want to rewrite x(n) as sin(wo(n)n), give an expression for wo(n) in terms of a and n. (b) A zero-phase FIR lowpass filter with cut-off frequency wc is applied to x(n), yielding y(n). If y(n) 0 for n > Nx /2, give wc in terms of a and Nx . (c) If h(n) is non-zero for |n| M/2, give an appropriate Hamming window for the filter of part (b). 3. A type I FIR filter impulse response can be found through windowing as h(n) = hd(n)w(n). (a) Give an expression for H(exp(jw)) in terms of Hd(ejw) and W(ejw). (b) Hd(ejw) can be expressed as R(w)exp(j(w)) and W(ejw) can be expressed as S(w)exp(j(w)). If hd(n) = hd(M-n) and w(n) = w(M-n), find expressions for (w) and (w). R(w) and S(w) may be positive or negative. (c). Using the results of part (b), simplify your expression from part (a). 4. A causal, linear-phase bandpass FIR digital filter h(n) is to be designed with cut-off frequencies of .3 radian and 2.3 radians, and with a phase of -23w. (a) Find an expression for hd(n) using the inverse DTFT. (b) Find the filter's time delay in samples. (c) If hd(n) is windowed to get h(n), find the largest possible value for N. (d) Give the appropriate Hamming window for the length-N causal filter of part (c). 5. For w , the desired amplitude and phase responses, for a causal FIR digital filter with N coefficients, are as follows: | H d (e jw ) |= 1 4 r (| w | 4 ) + 4 r (| w | 2 ) d ( w) = 64 w + 2 sin(5w) Here, r() is the continuous ramp function. (a) Looking at the linear part of the desired phase, what is an appropriate value for N? (b) What is the filter's cut-off frequency ? (c) The pseudocode below uses the inverse DFT or FFT to generate h(n). Give the correct value for W, in the first line of code. (d) Give the correct expression for X, in terms of N, in the second line of code. (e) Give the correct expression for Y, in the third line of code. (f) Give the correct expression for Z, in the fifth line of code. H(0) = H(exp(jW)) For 1 k X w(k) = Y H(k) = H(exp(jw(k))) H(N-k) = Z End h(n) = DFT-1{H(k)} IIR Frequency Selective Filter Design 1. A prototype Butterworth lowpass filter, with a cut-off frequency of 1 radian/sec, has the transfer function, 1 2 s + 2s + 1 (a) Find the impulse response of H1(s). (b) Using impulse invariance and assuming T=1, find H(z) so that the digital filter cut-off frequency is 1 radian. (c) Find H(z) from H1(s) as a function of the sampling period T, using the bilinear transform, assuming no pre-warping. (d) For the filter H(z) of part (c), give the cut-off frequency in radians as a function of T. H 1 (s) = 2. A prototype Butterworth lowpass filter H1(s) with even order m has no real poles. The poles therefore come in complex conjugate pairs. The first m/2 stable poles are sk= ej(k). (a) Give an expression for bk in terms of (k) if H1(s) is written as m/2 H 1(s) = k=1 1 ( s 2 + bk s + 1 ) (b) For the corresponding Chebyshev version of H1(s), which is m/2 H '1(s) = k=1 ck ( s 2 + d k s + ek ) give expressions for dk and ek in terms of and (k), remembering that multiplies the real part of ej(k). (c) H'1(s) from part (b) above can be transformed into the lowpass filter m/2 H a(s) = k=1 fk ( s 2 + g k s + hk ) Give expressions for fk, gk, and hk in terms of ck , dk , ek , and the desired Ha(s) cut-off frequency c. 3. A 4th order prototype Butterworth lowpass filter H1(s) has no real poles. The poles therefore come in complex conjugate pairs. The first two stable poles are sk= ej(k) for k = 1 and 2. (a) Give an expression for ak in terms of (k) if H1(s) is written as 2 H 1(s) = k=1 1 ( s 2 + ak s + 1 ) (b) For the corresponding Chebyshev version of H1(s), which is 2 bk 2 k=1 ( s + d k s + ck ) give expressions for ck and dk in terms of and (k), remembering that multiplies the real part of ej(k). H '1(s) = (c) H'1(s) from part (b) above can be transformed into the bandpass filter 2 ek s H a(s) = 4 3 2 k=1 ( s + ik s + hk s + g k s + f k ) 2 Give expressions for ek fk, gk, hk , and ik in terms of the symbols bk ,ck , dk , Bw , and (o)2 . Give expressions for Bw and (o)2 in terms of the desired Ha(s) cut-off frequencies c1 and c2 . 4. A prototype Butterworth lowpass filter H1(s) with even order n has no real poles. The poles therefore come in complex conjugate pairs. The first n/2 stable poles are sk= ej(k). (a) Give an expression for (k), for k=1 to n/2. (b) Give an expression for bk if H1(s) can be written as n/2 1 k =1 ( s + b k s + 1 ) (c) H1(s) can be transformed into the bandpass filter n/2 2 ck s H a (s) = 4 3 2 k =1 ( s + d k s + ek s + f k s + g k ) H 1 (s) = 2 Assume that Ha(s) is to be transformed to H(z) using the bilinear transform, and that H(z) is to have cut-off frequencies wc1 and wc2, in radians. Find expressions for Ha(s) cut-off frequencies c1 and c2 in terms of wc1, wc2, and T. Give expressions for o2 and Bw in terms of c1 and c2 . 5. We want to explore an approach for generating the poles of the bandpass filter Ha(s) from the poles of H1(s). Assume that the poles of H1(s) have the form exp(j(k)) where (k) = o + (k-1). (a) Give expressions for o and if H1(s) is a Butterworth prototype filter with an integer order n. (b) Given the kth pole of H1(s), what equation must be solved to get the resulting two poles of Ha(s) ? The equation's coefficients must be functions of Bw and o. (c) If Ha(s) is to be an odd-ordered Butterworth bandpass filter, what can we say about the order of H1(s) ? (d) Is it possible to design an odd-ordered Butterworth bandpass filter, using a prototype filter H1(s) ? 6. A prototype Butterworth lowpass filter H1(s) with odd order n can be transformed into the bandpass filter co s H a (s) = 2 ( s + f o s + go ) (n -1)/2 k =1 ck s 4 3 ( s + d k s + ek s 2 + f k s + g k ) 2 which can then be transformed into the filter H(z) = ( j o z -2 + mo z -1 + no ) (n-1)/2 ( hk z -4 + i k z -3 + j k z -2 + mk z -1 + n k ) ( q o z - 2 + r o z -1 + s o ) k=1 ( ok z -4 + p k z -3 + q k z - 2 + r k z -1 + s k ) using the bilinear transform with T=2. (a) Give expressions for jo, mo, no, qo, ro, and so in terms of co, fo, and go. (b) Give expressions for hk, ik, jk, mk, and nk. IIR Frequency Selective Filter Specifications 1. A Butterworth bandpass digital filter is to be designed with an upper cut-off of wd2 radians and a lower cut-off of wd1 radians, using the bilinear transform. We want the amplitude response of the filter to be down by X db at a frequency of wd3 radians. (a) Express c1, c2, c3, Bw, and o for Ha(s) as functions of wd1, wd2, wd3, and T. (b) Express 1, 2, and 3, for the prototype filter H1(s), in terms of c1, c2, c3, Bw, and o. (c) Find the order n of the filter H(z), as a function of X and any other relevant quantities from part (b). 2. A Butterworth lowpass digital filter is to be designed with a cut-off of wd1 radians, using the bilinear transform. We want the amplitude response of the filter to be down by at least X db at a frequency of wd2 radians. (a) Express c1 and c2 for Ha(s) as functions of wd1, wd2, and T. (b) Find the minimum order n of the filter H(z), as a function of X and any other relevant quantities from part (a). 3. An IIR Butterworth lowpass digital filter is to be designed with a cut-off frequency of dc = 5 radians/sec. Its amplitude response is to be down at least 40 db at a frequency of d1 = 510 radians/sec. (a) Find the corresponding frequencies c and c1 for the lowpass filter Ha(s) if the sampling rate in radians per second satisfies s >> d1. (b) Given the assumption of part (a), what minimum order should the filter have ? IIR Filters 1. H(z) is written as (lk z -4 + k k z -3 + j k z -2 + m k z -1 + n k ) H(z) = -4 -3 -2 -1 k=1 ( o k z + p k z + q k z + r k z + s k ) 2 where H(z) can be factored initially as H1(z)H2(z) and s1 = s2 = 1. H1(z) is the part of H(z) with k=1. As written above, H(z) is causal and stable, with H1(ejw) = |H1(ejw)| ej1(w) and H2(ejw) = |H2(ejw)| ej2(w). However, we will replace z-1 by z in H2(z) to get H2(z-1). H2(z-1) is now stable and anti-causal. (a) Assuming that H1(z) has input x(n) and output y1(n), write the difference equation for y1(n) in terms of x(n). (b) Assuming that H2(z-1) has input y1(n) and output y(n), write the difference equation for y(n) in terms of y1(n). (c ) Give the phase of the non-causal filter H(z) = H1(z)H2(z-1), in terms 1(w) and 2(w). 2. A digital filter h(n) is to be designed as h(n) = h1(n)h2(n), where all three impulse responses are real. (a) Express H(ejw) in terms of H1(ejw) and H2(ejw) (b) If H1(ejw) and H2(ejw) have the same ideal lowpass amplitude response with cut-off frequency wc < /2, and phases 1(w) = 2(w) = -.5(N-1)w, sketch the magnitude response and give the phase response (w) of the filter H(ejw) . (c) Suppose that H1(ejw) and H2(ejw) exist, and are described as 1 1 jw jw , (e ) = H 1(e ) = H 2 1 .5e jw 1 .5e jw Assuming again that h(n) = h1(n)h2(n), give the impulse response h(n). (d) Continuing part (c ), give the frequency response H(ejw). 3. The transfer function H(z) of problem 5 can be written as Ho(z)H1(z)H2(z) H(n-1)/2(z) where Ho(z) is the second order section and the Hk(z) sections are 4th order. (a) The 0-order denominator coefficients so and sk must equal 1 before the filter can be applied. Give the constant K which, when multiplied by all numerator and denominator coefficients in Ho(z), converts so to 1. Give the coefficient K which does the same thing for sk in Hk(z). (b) The input and output transforms for the cascade section Hk(z) can be denoted as Xk(z) and Yk(z) respectively. Give the difference equation that relates xo(n) and yo(n). Give the difference equation that relates xk(n) and yk(n). (c) Give xo(n) in terms of x(n) and xk(n) in terms of ym(n), and the final output y(n) in terms of yi(n). 4. H(z) is designed by applying the bilinear transform to Ha(s), where T=2. (a) Give the expression for in terms of w. (b) If Ha(j) can be expressed as |Ha(j)|exp(ja()), give the phase response (w) of H(z). (c) Assuming that an allpass digital filter A(z) has the phase response ap(w) and an amplitude response of 1 for all w, give the allpass filter's frequency response. (d) If A(z) corrects the phase of H(z) so that the phase response of A(z)H(z) is d(w), give ap(w) in terms of d(w) and a(). 5. The impulse response of an analog filter is hc(t) = e-tsin(t)u(t). A digital filter H(z) is to be designed using impulse invariance. (a) Give h(n) as a function of T. (b) Give H(z) in its final form such that all coefficients are real. Bilinear Transform 1. The standard bilinear transformation, s = 2 T 1 z 1 1 + z 1 can map circles in one domain to circles in the other domain. Given values on the unit circle in the s-domain, we want to find parameters of the resulting z-domain circle. (a) Give z as a function of T and s. (b) Give two real values of s which are on the unit circle in the s-plane. (c) Given the two values of s in part (b), find the corresponding values of z. (d) Assume that a line, connecting the two z values of part (c), passes through the z-plane circle's center. Find the z value at the circle's center. (e) Assume that a line, connecting the two z values of part (c), passes through the z-plane circle's center. Find the radius of the z-plane's circle. 2. The transformation, z=(d+s)/(1-s), can map a digital filter H(z) into an analog filter Ha(s). (a) Solve for s in terms of d and z. (b) What part of the s-plane is mapped to the unit circle of the z-plane by the transformation? (c) If d=1/2, does this transformation map stable digital filters into stable analog filters ? (answer always, never, or sometimes ) (d) If d=2, does this transformation map stable digital filters into stable analog filters ? (answer always, never, or sometimes ) 3. The transformation, z=(5+s)/(1-s), can map a digital filter H(z) into an analog filter Ha(s). (a) What part of the s-plane is mapped to the unit circle of the z-plane by the transformation? (b) Does this transformation map stable digital filters into stable analog filters ? (answer always, never, or sometimes ) 4. The continuous-time lowpass filter Hc(s) has cut-off frequency c. This filter is transformed to a lowpass discrete-time filter with cut-off wp1 by substituting (1-z-1)/(1+z-1) for s. Hc(s) is transformed to a highpass discrete-time filter with cut-off wp2 by substituting (1+z-1)/(1-z-1) for s. (a) Find c in terms of wp1. (b) Find c in terms of wp2. (c) Find a simple relationship between wp2 and wp1. 5. The standard bilinear transformation, s = 2 T 1 z 1 1 + z 1 can map circles in one domain to circles in the other domain. Given values on a circle of radius R in the s-domain, as s = Rej, we want to find parameters of the resulting z-domain circle. (a) Give z as a function of T and s. (b) If s = Rej , where can vary, give two real values of s. (c) Given the two values of s in part (b), find the corresponding values of z. (d) Assume that a line, connecting the two z values of part (c), passes through the z-plane circle's center. Find the z value at the circle's center. (e) Assume that a line, connecting the two z values of part (c), passes through the z-plane circle's center. Find the radius of the z-plane's circle. Advanced Material 1. A straight line y = a + bx is to be fit to some data points {( xp , tp ) } where 1 p Nv . The mean-squared error to be minimized is 1 Nv E= (t p (a + bx p ))2 N v p =1 (a) Give expressions for ga = E/a and gb = E/b. (b) Given symbols mt , mx , r , and c defined as 1 mt = Nv mx = c= 1 Nv 1 Nv Nv t p , x p , p p , p =1 Nv p =1 Nv x t p =1 1 Nv r= xp xp N v p =1 refine your expressions for ga and gb in terms of these symbols. (c ) If steepest descent is used to update estimates for a and b, give the equations for the updates in terms of symbols ga , gb and B2