The Wavelet Digest Homepage
Return to the homepage
Search the complete Wavelet Digest database
Help about the Wavelet Digest mailing list
About the Wavelet Digest
The Digest The Community
 Latest Issue  Back Issues  Events  Gallery
The Wavelet Digest
   -> Volume 3, Issue 17


Reply: WD 3.16 (#9) (Parallel Discrete Wavelet Transform)
 
images/spacer.gifimages/spacer.gif Reply into Digest
Previous :: Next  
Author Message
lyall@dc.aaec.com (Mike Lyall)
Guest





PostPosted: Mon Dec 02, 2002 1:27 pm    
Subject: Reply: WD 3.16 (#9) (Parallel Discrete Wavelet Transform)
Reply with quote

Reply: WD 3.16 (#9) (Parallel Discrete Wavelet Transform)

Hi,

I think I may have a simple answer for your question.

The algorithm you described in Wavelet Digest is known as the
tree algorithm, and uses a tree-structered filter bank to accomplish
this. This can be re-drawn into an M-channel filter bank by finding
the transfer function along each brach of the tree. This will
create an M=J+1 channel filter bank, where J is the number of levels in
the tree.

For example, take a J=3 level tree. The eqivalent M=4 channel FB
will have the transfer functions:

A3(z) = H1(z) --> H
A2(z) = H0(z) H1(z^2) --> LH
A1(z) = H0(z) H0(z^2) H1(z^4) --> LLH
A0(z) = H0(z) H0(z^2) H0(z^4) --> LLL

where H0(z) is the lowpass analysis filter and H1(z) is the highpass
analysis filter. The sequence after the arrow denotes the path
through the filter bank. Each of the above filters Ai(z) are
octave band filters and will perform a DWT. The downsampling rate after
each of this filters is calculated by multiplying together the
downsamplers found along the particular branch. For the example above,
the downsampling rates would be 2,4,8,8 for A3(z) to A0(z) respectively.
All of this comes from the "noble multirate identities" discussed in
much of the FB literature.

A good source to find this is P.P. Vaidyanathan's book "Multirate
Systems and Filter Banks", Prentice-Hall, 1993. The information
I just gave you is in section 11.3.3, pp. 491-496.

I've done some computational analysis of these structures and the
tree algorithm is more efficient than this "composite", as I call
it, structure. The reason lies behind the sampling rate at which the
filtering operations take place. Overall, there are about the same
number of filter taps for each configuration. However, in the
tree-structure, many of these operations are performed at a lower
rate, thus creating a savings. With the composite structure, all
operations are done at the highest rate. Hence, there is a lot of
redundancy involved. Polyphase implementations eliminate redundancies
that exist in both structures. In the tree algorithm, the number of
computations is reduced by 1/2. I'm not sure what the polyphase
composite does yet, but it still looks like the polyphase tree beats it,
especially for large trees.

Hope this helps you out.

Michael J. Lyall lyall@dc.aaec.com
Atlantic Aerospace Electronics Corp.
6404 Ivy Lane, Ste. 300 12534 Woodstock Dr.
Greenbelt, MD 20770 Upper Marlboro, MD 20772
Phone: (301) 982-5202 (301) 627-3228
FAX: (301) 982-5278
All times are GMT + 1 Hour
Page 1 of 1

 
Jump to: 
 


disclaimer - webmaster@wavelet.org
Powered by phpBB

This page was created in 0.025330 seconds : 18 queries executed : GZIP compression disabled