Recall that for image compression (see The 2-band Filter Bank), the
purpose of the 2-band filter bank in the Haar transform is to
compress most of the signal energy into the low-frequency band.
We may achieve greater compression if the low brand is further
split into two. This may be repeated a number of times to give
the binary filter tree, shown with 4 levels in Figure 1.
In 1-D, this is analogous to the way the 2-D Haar transform was extended to the multi-level Haar transform.
For an NN-sample input vector
xx, the sizes and
bandwidths of the signals of the 4-level filter tree are:
Table 1
|
Signal
|
No. of samples
|
Approximate pass band
|
|
xx
|
NN
|
0→12
fs
0
1
2
fs
|
|
y1
y1
|
N2
N
2
|
14→12
fs
1
4
1
2
fs
|
|
y01
y01
|
N4
N
4
|
18→14
fs
1
8
1
4
fs
|
|
y001
y001
|
N8
N
8
|
116→18
fs
1
16
1
8
fs
|
|
y0001
y0001
|
N16
N
16
|
132→116
fs
1
32
1
16
fs
|
|
y0000
y0000
|
N16
N
16
|
0→132
fs
0
1
32
fs
|
Because of the downsampling (decimation) by 2 at each level, the
total number of output samples =
NN, regardless of the number of
levels in the tree.
The
H
0
H
0
filter is normally designed to be a lowpass filter
with a passband from 0 to approximately
14
1
4
of the input sampling frequency for that stage; and
H1
H1
is a highpass (bandpass) filter with a pass band
approximately from
14
1
4
to
12
1
2
of the input sampling frequency.
When formed into a 4-level tree, the filter outputs have the
approximate pass bands given in Table 1. The final output
y0000
y0000
is a lowpass signal, while the other outputs are all
bandpass signals, each covering a band of approximately one
octave.
An inverse tree, mirroring Figure 1, may be constructed using filters
G0
G0
and
G1
G1
instead of
H0
H0
and
H1
H1
, as shown for just one level in part (b) of this figure. If the PR
conditions of this previous equation and this previous
equation are satisfied, then the output of each level
will be identical to the input of the equivalent level in Figure 1, and the final output will be a
perfect reconstruction of the input signal.
To calculate the impulse and frequency responses for a
multistage network with downsampling at each stage, as in
Figure 1, we must first derive an
important theorem for multirate filters.
The downsample-filter-upsample operation of Figure 2(a) is equivalent to either
the filter-downsample-upsample operation of Figure 2(b) or the
downsample-upsample-filter operation of Figure 2(c), if the filter is
changed from
Hz
H
z
to
Hz2
H
z
2
.
From Figure 2(a):
y
^
n={∑ix(n−2i)hi if n is even0 if n is odd
y
^
n
i
x
n
2
i
h
i
n is even
0
n is odd
(1)
Take z-transforms:
Y
^
z=∑n
y
^
nz−n=∑even n∑ix(n−2i)hiz−n
Y
^
z
n
y
^
n
z
n
even n
i
x
n
2
i
h
i
z
n
(2)
Reverse the order of summation and let
m=n−2i
m
n
2
i
: therefore,
Y
^
z=∑ihi∑even mxmz−mz-2i=∑ihiz-2i∑even mxmz−m=Hz212(Xz+X−z)=12(Hz2Xz+H−z2X−z)=12(Yz+Y−z)
Y
^
z
i
h
i
even m
x
m
z
m
z
-2
i
i
h
i
z
-2
i
even m
x
m
z
m
H
z
2
1
2
X
z
X
z
1
2
H
z
2
X
z
H
z
2
X
z
1
2
Y
z
Y
z
(3)
where
Yz=Hz2Xz
Y
z
H
z
2
X
z
This describes the operations of Figure 2(b). Hence the first result is proved.
The result from line 3 in Equation 3
Y
^
z=12(Xz+X−z)Hz2=
X
^
zHz2
Y
^
z
1
2
X
z
X
z
H
z
2
X
^
z
H
z
2
(4)
shows that the filter
Hz2
H
z
2
may be placed after the down/up-sampler as in
Figure 2(c), which proves the
second result.
It can be shown that:
-
Hz
H
z
becomes
HzM
H
z
M
if shifted ahead of an M:1 downsampler or
following an M:1 upsampler.
-
M:1 down/up-sampling of a signal
Xz
X
z
produces:
X
^
z=1M∑m=0M−1Xzej2πmM
X
^
z
1
M
m
0
M
1
X
z
2
m
M
(5)
Using the result of Equation 3, Figure 1 can be redrawn as in Figure 3 with all downsamplers moved to
the outputs. (Note Figure 3
requires much more computation than Figure 1.)
We can now calculate the transfer function to each output
(before the downsamplers) as:
H01
z=
H0
z
H1
z2
H01
z
H0
z
H1
z
2
(6)
H001
z=
H0
z
H0
z2
H1
z4
H001
z
H0
z
H0
z
2
H1
z
4
(7)
H0001
z=
H0
z
H0
z2
H0
z4
H1
z8
H0001
z
H0
z
H0
z
2
H0
z
4
H1
z
8
(8)
H0000
z=
H0
z
H0
z2
H0
z4
H0
z8
H0000
z
H0
z
H0
z
2
H0
z
4
H0
z
8
(9)
In general the transfer functions to the two outputs at level
kk of the tree are given by:
H
k
,
1
=∏i=0k−2
H0
z2i
H1
z2k−1
H
k
,
1
i
0
k
2
H0
z
2
i
H1
z
2
k
1
(10)
H
k
,
0
=∏i=0k−1
H0
z2i
H
k
,
0
i
0
k
1
H0
z
2
i
(11)
For the Haar filters of
this equation and
this equation from our
discussion of the 2-band filter bank, the transfer functions
to the outputs of the 4-level tree become:
H01
z=12(z-3+z-2−z-1+1)
H01
z
1
2
z
-3
z
-2
z
-1
1
(12)
H001
z=12×2(z-7+z-6+z-5+z-4−z-3+z-2+z-1+1)
H001
z
1
2
2
z
-7
z
-6
z
-5
z
-4
z
-3
z
-2
z
-1
1
(13)
H0001
z=14(z-15+z-14+z-13+z-12+z-11+z-10+z-9+z-8−z-7+z-6+z-5+z-4+z-3+z-2+z-1+1)
H0001
z
1
4
z
-15
z
-14
z
-13
z
-12
z
-11
z
-10
z
-9
z
-8
z
-7
z
-6
z
-5
z
-4
z
-3
z
-2
z
-1
1
(14)
H0000
z=14(z-15+z-14+z-13+z-12+z-11+z-10+z-9+z-8+z-7+z-6+z-5+z-4+z-3+z-2+z-1+1)
H0000
z
1
4
z
-15
z
-14
z
-13
z
-12
z
-11
z
-10
z
-9
z
-8
z
-7
z
-6
z
-5
z
-4
z
-3
z
-2
z
-1
1
(15)
