7.13 Finite-length sequences and the dwt matrix

Digital signal processing (ohio 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, 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

	Socialism Command Economy By Robert Murphy Start Test
	Respiratory System Drugs By CB Biern Start Quiz
	25 AP 25 Urinary System MCQ By OpenStax Start Quiz
	Neuropsychology Midterm By Kimberly Nichols Start Test
	Financial Intelligence Quiz By Yasser Ibrahim Start Quiz
	Does your crush like you? By Hoy Wen Start Quiz
	Chemistry Final By Briana Hamilton Start Flashcards
	11 Clin Sci I - GI Twedt quiz 2 By Brooke Delaney Start Exam
	14 Sociology 14 Marriage and Family MCQ By OpenStax Start Quiz
	Engineering Communication MCQ By Steve Gibbs Start Quiz