CE 734 Project Proposal  

Fast Algorithms for Discrete Wavelet Transform: 

Review and Implementation

Dan Li

The wavelet transform is a signal-processing tool that decomposes a
signal in terms of a set of basis functions generated by translation and
dilation/compression of a localized mother wavelet.  The discrete
version of wavelet transform, known as the discrete wavelet transform
(DWT), has found a large variety of signal processing applications.  In
addition to many appealing features following DWT such as
multi-resolution analysis and time-scale representation, a key factor
that makes the DWT become practical is the availability of fast
algorithm--fast wavelet transform (FWT).  The importance of this issue
is a direct result of the intensive computation and large space
requirement of DWT.  The first fast algorithm was proposed by Mallet in
1988.  Mallet's classical "pyramidal" FWT is essentially the two-channel
subband coder.  In 90s a good deal of research focusing on
implementation of DWT brought about some fast algorithms and efficient
implementations on VLSI architectures. 

This project is intended to be a review and implementation type of
project.  Focus will be on fast implementation on algorithm (software)
level, while architectural level may also be brought up and remarked. 
In the first part, a comprehensive review on the fast DWT algorithms
will be given based on results from several research papers.  Meanwhile,
following fast algorithms will be discussed:

- Polyphase structure based transversal filter: By using the Noble
identity, the fundamental DWT cell is re-arranged and the filtering
process can be implemented by using FFT-based circular convolution
technique.  This algorithm is reported to be efficient for medium to
large wavelet prototypes. 

- Polyphase structure based efficient transversal FIR filter
realization: Also we start with Noble identity.  But for the filtering
part, a short-length "fast running FIR" algorithm is applied to compute
DWT.  Also based on FFT techniques, this algorithm is more suitable for
small to medium wavelet prototypes. 

- Lattice filter: Lattice structure of two-channel FIR filter banks can
further reduce the number of multiplication, and has several attractive
properties (e.g.  linear phase response). 

- Binomial quadrature mirror filters (QMF): It is applicable for
orthogonal wavelet (e.g.  Daubechies’s wavelets). 

- CORDIC lattice filters: This approach uses the smallest number of
adders compared with the other methods, thus is often chosen as the
architecture for VLSI implementations. 

In the second part, the polyphase structure based fast DWT algorithms
will be implemented in software level.  Experiments such as signal/image
compression will be conducted to test the effectiveness of the
implemented methods and to evaluate the efficiency as appose to Mallet’s
fast DWT algorithm in terms of computation time, accuracy etc.  An
in-depth discussion will be followed the experiment results. 

References

[1] O.  Rioul and P.  Duhamel, Fast Algorithms for Discrete and
Continuous Wavelet Transforms, IEEE Trans.  Info.  Tech.  38(2):569-586,
1992

[2] S.  Simon, P.  Rieder and J.  A.  Nossek, Efficient VLSI suited
architectures for discrete wavelet transforms, Workshop on VLSI Signal
Processing, IX: 388-397, 1996

[3] S.  Simon, P.  Rieder, C.  Schimpfle and J.  A.  Nossek,
CORDIC-based Archietecutres for the Efficient Implementations of DWTs,
ISCAS, 1995

[4] G.  Strang and T.  Nguyen, Wavelet and Filter Banks, Wellesley
Cambridge Press, 1996. 

[5] R.  Yin and W.  Ma, The Fast Algorithm for the Finite Length
Discrete Wavelet Transform, 1994 Int.  Sympo.  Speech, Image Proc. 
Neural Networks, Hong Kong.  13-16, 1994

[6] S.  Oraintara, Regular Linear Phase Perfect Reconstruction Filter
Banks for Image Compression, Ph.D.  Dissertation, Boston University,
2000.