18.327 Handout 3

Course 18.327 and 1.130 Wavelets and Filter Banks Filter Banks: time domain (Haar example) and frequency domain; conditions for alias cancellation and no distortion Haar Filter Bank Simplest (non-trivial) example of a two channel FIR perfect reconstruction filter bank. v0[n] r0[n] t0[n] å 2 é 2 h0[n] f0[n] y0[n] ^ x[n] x[n] Synthesis Analysis t1[n] r1[n] v [n] å2 f1[n] 1 é2 h1[n] y1[n] h0[n] = 0 1 1 µ2 1 µ2 1 µ2 1 µ2 f0[n] = -1 0 2 1 1 µ2 1 µ2 h1[n] = 0 1 f1[n] = -1 µ2 -1 -1 µ2 0 Analysis: 1 r0[n] = µ2 (x[n] + x[n œ 1]) lowpass filter y0[n] = r0[2n] 1 y0[n] = (x[2n] + x[2n œ 1]) µ2 Similarly 1 y1[n] = (x[2n] œ x[2n œ 1]) µ2 downsampler -----------------j j ------------------k k 3 Matrix form 4 y0[0] y0[1] : : y1[0] y1[1] 4 4 3 1 3 0 = 1 µ2 1 0 0 1 0 3 1 3 0 -1 0 3 1 3 : x[-1] x[0] x[1] 4 3 -1 1 3 0 0 4 yo y1 x[2] : : L = B x -------------------l l 4 2 t0[n] = &)')( Synthesis y0[n/2] upsampler 0 1 µ2 v0[n] = &)')( = n even n odd ( t0[n + 1] + t0[n]) 1 µ2 y0[n/2] n even 1 µ2 y0[ n + 1 ] n odd 2 lowpass filter 5 v1[n] = &)')( Similarly 1 µ2 y1[n/2] n even 1 µ2 y1[ n + 1 ] n odd - 2 So, the reconstructed signal is ^ x[n] = v0[n] + v1[n] &)')( = 1 µ2 (y0[n/2] + y1[n/2]) n even 1 µ2 (y0[ n + 1] - y1[ n + 1 ]) n odd 2 2 6 3 i.e. ^ x[2n-1] = 1 µ2 ^ x[2n] 1 µ2 µ (y0[n] œ y1[n]) = x[2n-1] from j and k = ^ So x[n] = (y0[n] + y1[n]) = x[2n] Ω Perfect reconstruction! x[n] In general, we will make all filters causal, so we will have ^ x[n] = x[n œ n0] Ω PR with delay 7 Matrix form 4 ^ x[-1] ^ x[0] 1 = ^ µ2 x[1] ^ x[2] 4 ^ x 4 4 -1 0 1 1 4 4 1 0 1 0 3 3 3 0 1 0 1 4 4 0 -1 -1 1 4 4 3 4 y0[0] y0[1] 4 4 y1[0] y1[1] 4 y0 = LT ----------------m m BT y1 8 4 Perfect reconstruction means that the synthesis bank is the inverse of the analysis bank. L ^ = x Ω x LT BT = I B &'( &'( W-1 W ≈ Wavelet transform ’ ÷ Δ matrix ◊ « In the Haar example, we have the special case Wœ1 = WT ç orthogonal matrix So we have an orthogonal filter bank, where Synthesis bank = Transpose of Analysis bank f0[n] = h0[- n] = h1[- n] f1[n] 9 Perfect Reconstruction Filter Banks General two-channel filter bank H0(z) r0[n] é2 y0[n] 3 å2 t0[n] v0[n] F0(z) x[n] H1(z) r1[n] é2 y1[n] 3 å2 t1[n] F1(z) ^ x[n] § v1[n] z-transform definition: Ñ X(z) = ƒ x[n]z-n n=-Ñ Ñ Put z = ei w to get DTFT 10 5 Perfect reconstruction requirement: ^ x[n] = x[n - ?] ^ X(z) = z- ? X(z) (?? time delays) H0(z) and H1(z) are normally lowpass and highpass, but not ideal H1(w w) 1 w) H1(w w) H0(w p w 0 -p p p 2 2 Ω Downsampling operation in each channel can produce aliasing -p p 11 Let‘s see why: Lowpass channel has Y0(z) = ²{R0(z²) + R0(-z²)} (downsampling) = ²{H0(z²) X (z²) + H0(-z²)X(-z²)} In frequency domain: X(z) ç X(w) w X(-z) ç X(w w + p) p w ² X(z ) ç X( 2 ) Y0(w) w = ²{H0( w ) 2 X( w ) 2 or X(eiww) + H0( w 2 + p)X( p w 2 + p)} p 12 6 Suppose X(w w) = 1 (input has all frequencies) w) = H0(w w), so that after downsampling we have Then R0(w ²R0( w 2 + p) ²R0( w ) ² 2 ²R0( w 2 + p) Y0(w w) = -p p 0 p w aliasing Goal is to design F0(z) and F1(z) so that the overall system is just a simple delay - with no aliasing term: V0(z) + V1(z) = z- ? X(z) 13 V0(z) = F0(z) T0(z) = F0(z) Y0(z2) (upsampling) = ²F0(z){ H0(z) X(z) + H0(-z) X(-z)} V1(z) = ²F1(z){ H1(z) X(z) + H1(-z) X(-z)} So we want ² {F0(z) H0(z) + F1(z) H1(z) } X(z) + = z- ? X(z) ² {F0(z) H0(-z) + F1(z) H1(-z) } X(-z) 14 7 Compare terms in X(z) and X(-z): 1) Condition for no distortion (terms in X (z) amount to a delay) F0(z) H0(z) + F1(z) H1(z) = 2z- ? --------------j j 2) Condition for alias cancellation (no term in X(-z)) F0(z) H0(-z) + F1(z) H1(-z) = 0 --------------k k To satisfy alias cancellation condition, choose F0(z) = H1(-z) F1(z) = -H0(-z) ----------------------l l 15 What happens in the time domain? F0(z) = H1(-z) F0(w) w = H1(w w + p) p = ƒ h1[n] (-z)-n n = ƒ (-1)n h1[n] z-n n So the filter coefficients are f0[n] = (-1)n h1[n] f1[n] = (-1)n+1 h0[n] Example h0[n] = { a0, a1, a2} h1[n] = { b0, b1, b2} alternating signs rule f0[n] = { b0, -b1, b2 } f1[n] = {-a0, a1, -a2} 16 8 Product Filter Define P0(z) = F0(z) H0(z) ------------------------------m m Substitute F1(z) = -H0(-z) , H1(z) = F0(-z) in the zero distortion condition (Equation j) j F0(z) H0(z) - F0(-z) H0(-z) = 2z- ? P0(z) - P0(-z) = 2z-?? ----------------------------n n i.e. Note: ? must be odd since LHS is an odd function. 17 Normalized Product Filter Define P(z) = z? P0(z) ----------------------------o o P(-z) = -z? P0(-z) since ? is odd So we can rewrite Equation n as z- ? P(z) + z- ? P(-z) = 2z- ? i.e. P(z) + P(-z) = 2 ---------------------------p p This is the condition on the normalized product filter for Perfect Reconstruction. 18 9 Design Process 1. Design P(z) to satisfy Equation p p. This gives P0(z). Note: P(z) is designed to be lowpass. 2. Factor P0(z) into F0(z) H0(z). Use Equations l to find H1(z) and F1(z). Note: Equation p requires all even powers of z (except z0) to be zero: ƒ p[n]z-n + ƒ p[n](-z)-n = 2 n n &'( Ω p[n] = 1 ; 0 ; n=0 all even n (n ò 0) 19 For odd n, p[n] and œp[n] cancel. The odd coefficients, p[n], are free to be designed according to additional criteria. Example: Haar filter bank 1 H0(z) = µ2 (1 + z-1) 1 H1(z) = µ2 (1 œ z-1) 1 (1 + z-1) µ2 1 F1(z) = -H0(-z) = µ2 (1- z-1) 1 P0(z) = F0(z) H0(z) = 2 (1 + z-1)2 F0(z) = H1(-z) = 20 10 So the Perfect Reconstruction requirement is P0(z) œ P0(-z) = 1 1 + 2z-1 + z-2) 2 Ω = 2z-1 P(z) = z? P0(z) = 1 1 œ2z-1 + z-2) 2 ? = 1 1 -1 2 (1 + z)(1 + z ) lm z Zeros of P(z): 1+z = 0 1 + z-1 = 0 1 2nd order zero at z = -1 Re 21 11