The Binary Filter Tree

Module by: Nick Kingsbury

Summary: This module introduces the binary filter tree.

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.

Figure 1: Extension of the 2-band filter bank into a binary filter tree.

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:

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.

Multi-rate filtering theorem

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.

Figure 2: Multi-rate filtering - the result of shifting a filter ahead of a downsampling operation or after an upsampling operation.

theorem 1

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 .

Proof

From Figure 2(a):

y ^ n= ∑ixn-2ihiif n is even 0ifn 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∑ixn-2ihiz-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=Hz212Xz+X-z=12Hz2Xz+H-z2X-z=12Yz+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=12Xz+X-zHz2= 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.

Transformation of the filter tree

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.)

Figure 3: Binary filter tree, transformed so that all downsampling operations occur at the outputs.

We can now calculate the transfer function to each output (before the downsamplers) as:

H01z=H0zH1z2 H01 z H0 z H1 z 2 (6)

H001z=H0zH0z2H1z4 H001 z H0 z H0 z 2 H1 z 4 (7)

H0001z=H0zH0z2H0z4H1z8 H0001 z H0 z H0 z 2 H0 z 4 H1 z 8 (8)

H0000z=H0zH0z2H0z4H0z8 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-2H0z2iH1z2k-1 H k , 1 i 0 k 2 H0 z 2 i H1 z 2 k 1 (10)

H k , 0 =∏i=0k-1H0z2i 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:

H01z=12z-3+z-2-z-1+1 H01 z 1 2 z -3 z -2 z -1 1 (12)

H001z=122z-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)

H0001z=14z-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)

H0000z=14z-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)

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the author of the module, The Binary Filter Tree

Footer

More about this content: Metadata | Version History

• How to reuse and attribute this content
• How to cite and attribute this content

This work is licensed by Nick Kingsbury under a Creative Commons Attribution License (CC-BY 1.0).

Last edited by Elizabeth Gregory on Jun 8, 2005 10:13 am GMT-5.