Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » DSPA » Finite-Length Sequences and the DWT Matrix

Navigation

Table of Contents

Recently Viewed

This feature requires Javascript to be enabled.
 

Finite-Length Sequences and the DWT Matrix

Module by: Phil Schniter. E-mail the author

Summary: 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 Figure 1.

Figure 1
Figure 1 (wavelet_2channel.png)

First consider a very long (i.e., practically infinite-length) sequence c k m mZ c k m m . For every pair of input samples c k 2n c k 2n1 c k 2 n c k 2 n 1 that enter the k th k th filterbank stage, exactly one pair of output samples c k + 1 n d k + 1 n 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. This property is convenient from a real-time processing perspective.

For a short sequence c k m m0M1 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

c k m=0  ,   m0M1    m m 0 M 1 c k m 0
(1)
In this case, the linear convolution implies that MM nonzero inputs yield M+N21 M N 2 1 outputs from each branch, for a total of 2(M+N21)=M+N2>M 2 M N 2 1 M N 2 M outputs. Here we have assumed that both Hz-1 H z and Gz-1 G z have impulse response lengths of N>2 N 2 , and that MM and NN are both even. The fact that each filterbank stage produces more outputs than inputs is very disadvantageous in many applications.

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

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

It is instructive to write the circular-convolution analysis fiterbank operation in matrix form. In Equation 3 we give an example for filter length N=4 N 4 , sequence length N=8 N 8 , and causal synthesis filters Hz H z and Gz 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=( h0h1h2h30000 00h0h1h2h300 0000h0h1h2h3 h2h30000h0h1 g0g1g2g30000 00g0g1g2g300 0000g0g1g2g3 g2g30000g0g1 ) c k 0 c k 1 c k 2 c k 3 c k 4 c k 5 c k 6 c k 7 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
(3)
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 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 =( h0h1h2h30000 00h0h1h2h300 0000h0h1h2h3 h2h30000h0h1 g0g1g2g30000 00g0g1g2g300 0000g0g1g2g3 g2g30000g0g1 ) 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 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 H M and G M G M have interesting properties. For example, the conditions δm=nnhnhn2m δ m n n h n h n 2 m gn=-1nhN1n g n -1 n h N 1 n imply that H M G M T H M G M = H M G M H M G M T= I M H M G M H M G M H M G M H M G M I M where I M I M denotes the MMxMM identity matrix. Thus, it makes sense to define the MMxMM DWT matrix as
T M = H M G M T M H M G M
(4)
whose transpose constitutes the MMxMM inverse DWT matrix:
T M -1= T M T T M T M
(5)
Since the synthesis filterbank (Figure 2)

Figure 2
Figure 2 (syn_filterbank.png)

gives perfect reconstruction, and since the cascade of matrix operations T M T T M T M T M also corresponds to perfect reconstruction, we expect that the matrix operation T M T T M describes the action of the synthesis filterbank. This is readily confirmed by writing the upsampled circular convolutions 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=( h000h2g000g2 h100h3g100g3 h2h000g2g000 h3h100g3g100 0h2h000g2g00 0h3h100g3g10 00h2h000g2g0 00h3h100g3g1 ) 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 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
(6)
where H M T G M T= T M T=( h000h2g000g2 h100h3g100g3 h2h000g2g000 h3h100g3g100 0h2h000g2g00 0h3h100g3g10 00h2h000g2g0 00h3h100g3g1 ) 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 Figure 3.

Figure 3
Figure 3 (wavelet_decomp.png)

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 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
(7)
Similarly, a three-stage analysis could be implemented via
c k + 3 d k + 3 d k + 2 d k + 1 =( T M 4 00 0 I M 4 0 00 I M 2 )( T M 2 0 0 I M 2 ) T M c k 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
(8)
It should now be evident how to extend this procedure to 3 3 stages. As noted earlier, the corresponding synthesis operations are accomplished by transposing the matrix products used in the analysis.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks