Course 18.327 and 1.
130
Wavelets and Filter Banks
Filter Banks (contd.): perfect reconstruction; halfband filters and possible factorizations.
Product Filter
Example: Product filter of degree 6 P0(z) =
P0(z) 1 16
(-1 + 9z-2 + 16z-3 + 9z-4 - z-6)
P0(- z) = 2z-3
Expect perfect reconstruction with a 3 sample delay Centered form: P(z) = z3P0(z) =
P(z) + P(- z) = 2
1 16
(- z3 + 9z + 16 + 9z-1 z-3)
i.e. even part of P(z) = const
In the frequency domain: P(w) + P(w + p) = 2
Halfband Condition
2
P(w) Note antisymmetry about w = p/2
P(w) is said to be a halfband filter. How do we factor P0(z) into H0(z) F0(z)? P0(z) = 1/16(1 + z-1)4(-1 + 4z-1 - z-2) = -1/16(1 + z-1)4(2 + 3 z-1)(2 - 3 z-1)
3
So P0(z) has zeros at z = -1 (4th order) z = 2 3
Im
Note: 2 + 3 =
1 2 - 3
P0(z) 4th order zero at z = -1 -1 2-3 1
2 + 3
Re
Some possible factorizations
H0(z) (a) (b) (c) (d) (e) (f) (g) (or F0(z) ) F0(z) (or H0(z) )
1 (1 + z-1) (1 + z-1)2 (1 + z-1)(2 + 3 - z-1) 1/8(1 + z-1)3
(3 1)
4 2
-1/16(1 + z-1)4(2 + 3 - z-1)(2 - 3 - z-1) -1/8(1 + z-1)3(2 + 3 - z-1)(2 - 3 - z-1) -1/4(1 + z-1)2(2 + 3 - z-1)(2 - 3 - z-1) -1/8(1 + z-1)3(2 - 3 - z-1) -1/2(1 + z-1)(2 + 3 - z-1)(2 - 3 - z-1)
-2
4 (3 1)
(1 + z-1)2(2 + 3 - z-1)
(1 + z-1)2(2 - 3 - z-1)
1/16(1 + z-1)4
-(2 + 3 - z-1)(2 - 3 - z-1)
Case (b) -- Symmetric filters (linear phase)
3rd order
-1
-1
2-3
2 + 3
filter length = 2 { 1, 1 }
filter length = 6 /8 {-1, 1, 8, 8, 1, -1}
Case (c) -- Symmetric filters (linear phase)
2nd order -1
2nd order -1 2-3
2 + 3
filter length = 3 { 1, 2, 1 }
filter length = 5 { -1, 2, 6, 2, -1}
Case (f) -- Orthogonal filters (minimum phase/maximum phase)
2nd order
2nd order
2-3
-1
-1
2 + 3
filter length = 4 filter length = 4 1 1 1+3, 3+3, 3-3, 1-3 4 2 1-3, 3-3, 3+3, 1+3 4 2 Note that, in this case, one filter is the flip (transpose) of the other: f0[n] = h0[3 - n] F0(z) = z-3 H0(z-1)
*+,
*+,
*+,
*+,
8
General form of product filter (to be derived later): P(z) = 2( 1 +2z )p(
P0(z) =
1 + z-1 p ) 2 p-1 - 1)( 1 - z )k( 1 z )k ( p+k 2 k 2
-1
k=0
z-(2p 1) P(z)
p-1
-1 2k
- 1 )(-1)k z -(p - 1) + k( 1 z ) = (1 + z-1)2p 2 1 (p+k 2p-1 k 2 k=0 &'( &))))))')))))))( Q(z) Binomial Cancels all odd powers (spline) except z(2p-1) filter
P0(z) has 2p zeros at p (important for stability of iterated
filter bank.)
Q(z) factor is needed to ensure perfect reconstruction.
p = 1 P0(z) has degree 2 leads to Haar filter bank.
1, 1, 1, 1
1+ 2 z-1
2
2
1, 1
1 + z-1 2
1 - z-1
2
2
1 0
1 - z-1
0, 0
1 + z-1 2
F0(z) = 1 + z-1 , H0(z) =
Synthesis lowpass filter has 1 zero at p Leads to cancellation of constant signals in analysis highpass channel. Additional zeros at p would lead to cancellation of higher order polynomials.
10
p = 2 P0(z) has degree 4p 2 = 6 P0(z) = (1 + z-1)4 = =
1 16
1 8
{ (1 ) z-1 ( 2 )( 1 z )2} 0 1
2
-1
(1 + z-1)4( - 1 + 4z-1 - z-2) 1 + 9z-2 + 16z-3 + 9z-4 z-6}
Possible factorizations 1/8 trivial 2/6 linear phase 3/5 4/4 orthogonal 2 + 3 (Daubechies-4)
*+,
1 16 {-
-1 4th order 2-3 1
11
p = 4 P0(z) has degree 4p 2 = 14
8th order -1
12
Common factorizations (p = 4): (a) 9/7
Known in Matlab as bior4.4
4th order -1
4th order -1
13
(b) 8/8 (Daubechies 8) -- Known in Matlab as db4
4th order -1
4th order -1
14
Why choose a particular factorization? Consider the example with p = 2: i. One of the factors is halfband The trivial 1/8 factorization is generally not desirable, since each factor should have at least one zero at p. However, the fact that F0(z) is halfband is interesting in itself. V(z)
2
X(z)
F0(z)
Y(z)
Let F0(z) be centered, for convenience. Then F0(z) = 1 + odd powers of z Now X(z) = V(z2) = even powers of z only
15
So Y(z) = F0(z) X(z) = X(z) + odd powers y[n] = x[n] ; n even *+, f0[k]x[n k] ; n odd
k odd
f0[n] is an interpolating filter p sin ( 2 ) n Another example: f0[n] = pn (ideal bandlimited interpolating filter)
-2
x[n] 4 n 0 2 y[n] 0 2 4 n
16
ii. Linear phase factorization e.g. 2/6, 5/3 Symmetric (or antisymmetric) filters are desirable for many applications, such as image processing. All frequencies in the signal are delayed by the same amount i.e. there is no phase distortion. h[n] linear phase A(w)ei(w a + q)
real delays all frequencies by a samples 0 if symmetric p if antisymmetric 2
Linear phase may not necessarily be the best choice for audio applications due to preringing effects.
17
iii. Orthogonal factorization This leads to a minimum phase filter and a maximum phase filter, which may be a better choice for applications such as audio. The orthogonal factorization leads to the Daubechies family of wavelets a particularly neat and interesting case. 4/4 factorization: H0(z) =
3 - 1 4 2
1
(1 + z-1)2[(2 + 3) z-1]
= 42 {(1 + 3) + (3 + 3)z-1 + (3 -3)z-2 + (1- 3)z-3} F0(z) = =
- 2 4(3-1)
3-1
4 2
(1 + z-1)2[(2 - 3) z-1]
z-3 (1 + z2)[(2 + 3) - z]
= z-3 H0 (z-1)
18
P(z) = z?P0(z) = H0(z) H0(z-1) From alias cancellation condition: H1(z) = F0(-z) = -z-3 H0(-z-1) F1(z) = -H0(-z) = z-3 H1(z-1)
19
Special Case: Orthogonal Filter Banks Choose H1(z) so that
H1(z) = - z-N H0(- z-1)
N odd
Time domain h1[n] = (- 1)n h0[N n]
F0(z) = H1 (- z) = z-N H0(z1)
f0[n] = h0[N n]
F1(z) = - H0(- z) = z-N H1(z-1)
f1[n] = h1[N n]
So the synthesis filters, fk[n], are just the time-reversed
versions of the analysis filters, hk[n], with a delay.
20
10
Why is the Daubechies factorization orthogonal? Consider the centered form of the filter bank:
H0[z]
2
y0[n]
2
H0(z-1)
x[n]
H1[z]
y1[n]
Analysis bank causal only negative powers of z
x[n] no delay H0(z-1) in centered 2 form Synthesis bank anticausal only positive powers of z
21
In matrix form: Analysis
yo y1
L = B
&'(
Synthesis
y0
LT
BT
y1
WT
&'(
W So x = WTW x for any x WTW = I = WWT
An important fact: symmetry prevents orthogonality
22
11
Matlab Example 2
1. Product filter examples
23
Degree-2 (p=1): pole-zero plot
24
12
Degree-2 (p=1): Freq. response
25
Degree-6 (p=2): pole-zero plot
26
13
Degree-6 (p=2): Freq. response
27
Degree-10 (p=3): pole-zero plot
28
14
Degree-10 (p=3): Freq. response
29
Degree-14 (p=4): pole-zero plot
30
15
Degree-14 (p=4): Freq. response
31
16
