12.13 Finite-length sequences and the dwt matrix

Dspa Page 1 / 1

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 0000 00 h 0 h 1 h 2 h 3 00 0000 h 0 h 1 h 2 h 3 h 2 h 3 0000 h 0 h 1 g 0 g 1 g 2 g 3 0000 00 g 0 g 1 g 2 g 3 00 0000 g 0 g 1 g 2 g 3 g 2 g 3 0000 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 0000 00 h 0 h 1 h 2 h 3 00 0000 h 0 h 1 h 2 h 3 h 2 h 3 0000 h 0 h 1 g 0 g 1 g 2 g 3 0000 00 g 0 g 1 g 2 g 3 00 0000 g 0 g 1 g 2 g 3 g 2 g 3 0000 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

M

identity matrix. Thus, it makes sense to define the

M

M

DWT matrix as

T_{M} H_{M} G_{M}

whose transpose constitutes the

M

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 00 h 2 g 0 00 g 2 h 1 00 h 3 g 1 00 g 3 h 2 h 0 00 g 2 g 0 00 h 3 h 1 00 g 3 g 1 00 0 h 2 h 0 00 g 2 g 0 0 0 h 3 h 1 00 g 3 g 1 0 00 h 2 h 0 00 g 2 g 0 00 h 3 h 1 00 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 00 h 2 g 0 00 g 2 h 1 00 h 3 g 1 00 g 3 h 2 h 0 00 g 2 g 0 00 h 3 h 1 00 g 3 g 1 00 0 h 2 h 0 00 g 2 g 0 0 0 h 3 h 1 00 g 3 g 1 0 00 h 2 h 0 00 g 2 g 0 00 h 3 h 1 00 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_{\frac{M}{2}} 0 0 I_{\frac{M}{2}} c_{k + 1} d_{k + 1} T_{\frac{M}{2}} 0 0 I_{\frac{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_{\frac{M}{4}} 00 0 I_{\frac{M}{4}} 0 00 I_{\frac{M}{2}} T_{\frac{M}{2}} 0 0 I_{\frac{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.

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, Dspa. OpenStax CNX. May 18, 2010 Download for free at http://cnx.org/content/col10599/1.5

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Dspa' conversation and receive update notifications?

Ask

	Anthropology Aesthetics Culture By Richley Crapo Start Assignment
	26 AP 26 Fluid, Electrolyte, Acid-Base Balance Essay By OpenStax Start Flashcards
	Microeconomics Practice MCQ By Frank Levy Start Test
	Worldport Outside By Rachel Carlisle Start Quiz
	5 BOD Reproductive System quiz By Brooke Delaney Start Quiz
	2 Physiotherapy Flashcards Set 2 By Rhodes Start Flashcards
	Chemistry Final By Briana Hamilton Start Flashcards
©flickr: Mike	Examples of Wiffle IQ By Sean WiffleBoy Start Quiz
	20 Sociology 20 Population Urbanization Environment By OpenStax Start Quiz
	19 AP 19 Cardiovascular System Heart Essay By OpenStax Start Flashcards