<< Chapter < Page Chapter >> Page >
Discrete-time implementation of the DWT.

The wavelet transform, viewed from a filterbank perspective, consists of iterated 2-channel analysis stages like the one in .

First consider a very long (i.e., practically infinite-length) sequence c k m m . For every pair of input samples c k 2 n c k 2 n 1 that enter the k th filterbank stage, exactly one pair of output samples c k + 1 n d k + 1 n are generated. In other words, the number of output equals the number of input during a fixed time interval. Thisproperty is convenient from a real-time processing perspective.

For a short sequence c k m m 0 M 1 , however, linear convolution requires that we make an assumption about the tails of our finite-length sequence.One assumption could be

m m 0 M 1 c k m 0
In this case, the linear convolution implies that M nonzero inputs yield M N 2 1 outputs from each branch, for a total of 2 M N 2 1 M N 2 M outputs. Here we have assumed that both H z and G z have impulse response lengths of N 2 , and that M and N are both even. The fact that each filterbank stage produces more outputs than inputs isvery disadvantageous in many applications.

A more convenient assumption regarding the tails of c k m m 0 M 1 is that the data outside of the time window 0 M 1 is a cyclic extension of data inside the time window. In other words, given alength- M sequence, the points outside the sequence are related to points inside the sequences via

c k m c k m M
Recall that a linear convolution with an M -cyclic input is equivalent to a circular convolution with one M -sample period of the input sequences. Furthermore, the output of this circularconvolution is itself M -cyclic, implying our 2-downsampled branch outputs are cyclic withperiod M 2 . Thus, given an M -length input sequence, the total filterbank output consists of exactly M values.

It is instructive to write the circular-convolution analysis fiterbank operation in matrix form. In we give an example for filter length N 4 , sequence length N 8 , and causal synthesis filters H z and G z .

c k + 1 0 c k + 1 1 c k + 1 2 c k + 1 3 d k + 1 0 d k + 1 1 d k + 1 2 d k + 1 3 h 0 h 1 h 2 h 3 0 0 0 0 0 0 h 0 h 1 h 2 h 3 0 0 0 0 0 0 h 0 h 1 h 2 h 3 h 2 h 3 0 0 0 0 h 0 h 1 g 0 g 1 g 2 g 3 0 0 0 0 0 0 g 0 g 1 g 2 g 3 0 0 0 0 0 0 g 0 g 1 g 2 g 3 g 2 g 3 0 0 0 0 g 0 g 1 c k 0 c k 1 c k 2 c k 3 c k 4 c k 5 c k 6 c k 7
where c k + 1 d k + 1 c k + 1 0 c k + 1 1 c k + 1 2 c k + 1 3 d k + 1 0 d k + 1 1 d k + 1 2 d k + 1 3 H M G M h 0 h 1 h 2 h 3 0 0 0 0 0 0 h 0 h 1 h 2 h 3 0 0 0 0 0 0 h 0 h 1 h 2 h 3 h 2 h 3 0 0 0 0 h 0 h 1 g 0 g 1 g 2 g 3 0 0 0 0 0 0 g 0 g 1 g 2 g 3 0 0 0 0 0 0 g 0 g 1 g 2 g 3 g 2 g 3 0 0 0 0 g 0 g 1 c k c k 0 c k 1 c k 2 c k 3 c k 4 c k 5 c k 6 c k 7 The matrices H M and G M have interesting properties. For example, the conditions δ m n n h n h n 2 m g n -1 n h N 1 n imply that H M G M H M G M H M G M H M G M I M where I M denotes the M x M identity matrix. Thus, it makes sense to define the M x M DWT matrix as
T M H M G M
whose transpose constitutes the M x M inverse DWT matrix :
T M T M
Since the synthesis filterbank ( )

gives perfect reconstruction, and since the cascade of matrix operations T M T M also corresponds to perfect reconstruction, we expect that the matrix operation T M describes the action of the synthesis filterbank. This is readily confirmed by writing the upsampled circularconvolutions in matrix form:

c k 0 c k 1 c k 2 c k 3 c k 4 c k 5 c k 6 c k 7 h 0 0 0 h 2 g 0 0 0 g 2 h 1 0 0 h 3 g 1 0 0 g 3 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 0 0 0 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 0 0 0 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 c k + 1 0 c k + 1 1 c k + 1 2 c k + 1 3 d k + 1 0 d k + 1 1 d k + 1 2 d k + 1 3
where H M G M T M h 0 0 0 h 2 g 0 0 0 g 2 h 1 0 0 h 3 g 1 0 0 g 3 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 0 0 0 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 0 0 0 h 2 h 0 0 0 g 2 g 0 0 0 h 3 h 1 0 0 g 3 g 1 So far we have concentrated on one stage in the wavelet decomposition; a two-stage decomposition is illustrated in .

The two-stage analysis operation (assuming circular convolution) can be expressed in matrix form as

c k + 2 d k + 2 d k + 1 T M 2 0 0 I M 2 c k + 1 d k + 1 T M 2 0 0 I M 2 T M c k
Similarly, a three-stage analysis could be implemented via
c k + 3 d k + 3 d k + 2 d k + 1 T M 4 0 0 0 I M 4 0 0 0 I M 2 T M 2 0 0 I M 2 T M c k
It should now be evident how to extend this procedure to 3 stages. As noted earlier, the corresponding synthesis operations are accomplished by transposing thematrix products used in the analysis.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital signal processing (ohio state ee700). OpenStax CNX. Jan 22, 2004 Download for free at http://cnx.org/content/col10144/1.8
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing (ohio state ee700)' conversation and receive update notifications?

Ask