Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Appendix A

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Appendix A

Module by: C. Sidney Burrus. E-mail the author

This appendix contains outline proofs and derivations for the theorems and formulas given in early part of Chapter: The Scaling Function and Scaling Coefficients, Wavelet and Wavelet Coefficients . They are not intended to be complete or formal, but they should be sufficient to understand the ideas behind why a result is true and to give some insight into its interpretation as well as to indicate assumptions and restrictions.

Proof 1 The conditions given by (Reference) and (Reference) can be derived by integrating both sides of

φ ( x ) = n h ( n ) M φ ( M x - n ) φ ( x ) = n h ( n ) M φ ( M x - n )
(1)

and making the change of variables y=Mxy=Mx

φ ( x ) d x = n h ( n ) M φ ( M x - n ) d x φ ( x ) d x = n h ( n ) M φ ( M x - n ) d x
(2)

and noting the integral is independent of translation which gives

= n h ( n ) M φ ( y ) 1 M d y . = n h ( n ) M φ ( y ) 1 M d y .
(3)

With no further requirements other than φL1φL1 to allow the sum and integral interchange and φ(x)dx0φ(x)dx0, this gives (Reference) as

n h ( n ) = M n h ( n ) = M
(4)

and for M=2M=2 gives (Reference). Note this does not assume orthogonality nor any specific normalization of φ(t)φ(t) and does not even assume MM is an integer.

This is the most basic necessary condition for the existence of φ(t)φ(t) and it has the fewest assumptions or restrictions.

Proof 2 The conditions in (Reference) and (Reference) are a down-sampled orthogonality of translates by MM of the coefficients which results from the orthogonality of translates of the scaling function given by

φ ( x ) φ ( x - m ) d x = E δ ( m ) φ ( x ) φ ( x - m ) d x = E δ ( m )
(5)

in (Reference). The basic scaling equation Equation 1 is substituted for both functions in Equation 5 giving

n h ( n ) M φ ( M x - n ) k h ( k ) M φ ( M x - M m - k ) d x = E δ ( m ) n h ( n ) M φ ( M x - n ) k h ( k ) M φ ( M x - M m - k ) d x = E δ ( m )
(6)

which, after reordering and a change of variable y=Mxy=Mx, gives

n k h ( n ) h ( k ) φ ( y - n ) φ ( y - M m - k ) d y = E δ ( m ) . n k h ( n ) h ( k ) φ ( y - n ) φ ( y - M m - k ) d y = E δ ( m ) .
(7)

Using the orthogonality in Equation 5 gives our result

n h ( n ) h ( n - M m ) = δ ( m ) n h ( n ) h ( n - M m ) = δ ( m )
(8)

in (Reference) and (Reference). This result requires the orthogonality condition Equation 5, MM must be an integer, and any non-zero normalization EE may be used.

Proof 3 (Corollary 2) The result that

n h ( 2 n ) = n h ( 2 n + 1 ) = 1 / 2 n h ( 2 n ) = n h ( 2 n + 1 ) = 1 / 2
(9)

in (Reference) or, more generally

n h ( M n ) = n h ( M n + k ) = 1 / M n h ( M n ) = n h ( M n + k ) = 1 / M
(10)

is obtained by breaking Equation 4 for M=2M=2 into the sum of the even and odd coefficients.

n h ( n ) = k h ( 2 k ) + k h ( 2 k + 1 ) = K 0 + K 1 = 2 . n h ( n ) = k h ( 2 k ) + k h ( 2 k + 1 ) = K 0 + K 1 = 2 .
(11)

Next we use Equation 8 and sum over nn to give

n k h ( k + 2 n ) h ( k ) = 1 n k h ( k + 2 n ) h ( k ) = 1
(12)

which we then split into even and odd sums and reorder to give:

n k h ( 2 k + 2 n ) h ( 2 k ) + k h ( 2 k + 1 + 2 n ) h ( 2 k + 1 ) = k n h ( 2 k + 2 n ) h ( 2 k ) + k n h ( 2 k + 1 + 2 n ) h ( 2 k + 1 ) = k K 0 h ( 2 k ) + k K 1 h ( 2 k + 1 ) = K 0 2 + K 1 2 = 1 . n k h ( 2 k + 2 n ) h ( 2 k ) + k h ( 2 k + 1 + 2 n ) h ( 2 k + 1 ) = k n h ( 2 k + 2 n ) h ( 2 k ) + k n h ( 2 k + 1 + 2 n ) h ( 2 k + 1 ) = k K 0 h ( 2 k ) + k K 1 h ( 2 k + 1 ) = K 0 2 + K 1 2 = 1 .
(13)

Solving Equation 11 and Equation 13 simultaneously gives K0=K1=1/2K0=K1=1/2 and our result (Reference) or Equation 9 for M=2M=2.

If the same approach is taken with (Reference) and (Reference) for M=3M=3, we have

n x ( n ) = n x ( 3 n ) + n x ( 3 n + 1 ) + n x ( 3 n + 2 ) = 3 n x ( n ) = n x ( 3 n ) + n x ( 3 n + 1 ) + n x ( 3 n + 2 ) = 3
(14)

which, in terms of the partial sums KiKi, is

n x ( n ) = K 0 + K 1 + K 2 = 3 . n x ( n ) = K 0 + K 1 + K 2 = 3 .
(15)

Using the orthogonality condition Equation 13 as was done in Equation 12 and (Reference) gives

K 0 2 + K 1 2 + K 2 2 = 1 . K 0 2 + K 1 2 + K 2 2 = 1 .
(16)

Equation Equation 15 and Equation 16 are simultaneously true if and only if K0=K1=K2=1/3K0=K1=K2=1/3. This process is valid for any integer MM and any non-zero normalization.

Proof 3 If the support of φ(x)φ(x) is [0,N-1][0,N-1], from the basic recursion equation with support of h(n)h(n) assumed as [N1,N2][N1,N2] we have

φ ( x ) = n = N 1 N 2 h ( n ) 2 φ ( 2 x - n ) φ ( x ) = n = N 1 N 2 h ( n ) 2 φ ( 2 x - n )
(17)

where the support of the right hand side of Equation 17 is [N1/2,(N-1+N2)/2)[N1/2,(N-1+N2)/2). Since the support of both sides of Equation 17 must be the same, the limits on the sum, or, the limits on the indices of the non zero h(n)h(n) are such that N1=0N1=0 and N2=NN2=N, therefore, the support of h(n)h(n) is [0,N-1][0,N-1].

Proof 4 First define the autocorrelation function

a ( t ) = φ ( x ) φ ( x - t ) d x a ( t ) = φ ( x ) φ ( x - t ) d x
(18)

and the power spectrum

A ( ω ) = a ( t ) e - j ω t d t = φ ( x ) φ ( x - t ) d x e - j ω t d t A ( ω ) = a ( t ) e - j ω t d t = φ ( x ) φ ( x - t ) d x e - j ω t d t
(19)

which after changing variables, y=x-ty=x-t, and reordering operations gives

A ( ω ) = φ ( x ) e - j ω x d x φ ( y ) e j ω y d y A ( ω ) = φ ( x ) e - j ω x d x φ ( y ) e j ω y d y
(20)
= Φ ( ω ) Φ ( - ω ) = | Φ ( ω ) | 2 = Φ ( ω ) Φ ( - ω ) = | Φ ( ω ) | 2
(21)

If we look at Equation 18 as being the inverse Fourier transform of Equation 21 and sample a(t)a(t) at t=kt=k, we have

a ( k ) = 1 2 π - | Φ ( ω ) | 2 e j ω k d ω a ( k ) = 1 2 π - | Φ ( ω ) | 2 e j ω k d ω
(22)
= 1 2 π 0 2 π | Φ ( ω + 2 π ) | 2 e j ω k d ω = 1 2 π 0 2 π | Φ ( ω + 2 π ) | 2 e j ω k d ω = 1 2 π 0 2 π | Φ ( ω + 2 π ) | 2 e j ω k d ω = 1 2 π 0 2 π | Φ ( ω + 2 π ) | 2 e j ω k d ω
(23)

but this integral is the form of an inverse discrete-time Fourier transform (DTFT) which means

, a ( k ) e j ω k = | Φ ( ω + 2 π ) | 2 . , a ( k ) e j ω k = | Φ ( ω + 2 π ) | 2 .
(24)

If the integer translates of φ(t)φ(t) are orthogonal, a(k)=δ(k)a(k)=δ(k) and we have our result

| Φ ( ω + 2 π ) | 2 = 1 . | Φ ( ω + 2 π ) | 2 = 1 .
(25)

If the scaling function is not normalized

| Φ ( ω + 2 π ) | 2 = | φ ( t ) | 2 d t | Φ ( ω + 2 π ) | 2 = | φ ( t ) | 2 d t
(26)

which is similar to Parseval's theorem relating the energy in the frequency domain to the energy in the time domain.

Proof 6 Equation (Reference) states a very interesting property of the frequency response of an FIR filter with the scaling coefficients as filter coefficients. This result can be derived in the frequency or time domain. We will show the frequency domain argument. The scaling equation Equation 1 becomes (Reference) in the frequency domain. Taking the squared magnitude of both sides of a scaled version of

Φ ( ω ) = 1 2 H ( ω / 2 ) Φ ( ω / 2 ) Φ ( ω ) = 1 2 H ( ω / 2 ) Φ ( ω / 2 )
(27)

gives

| Φ ( 2 ω ) | 2 = 1 2 | H ( ω ) | 2 | Φ ( ω ) | 2 | Φ ( 2 ω ) | 2 = 1 2 | H ( ω ) | 2 | Φ ( ω ) | 2
(28)

Add kπkπ to ωω and sum over kk to give for the left side of Equation 28

k | Φ ( 2 ω + 2 π k ) | 2 = K = 1 k | Φ ( 2 ω + 2 π k ) | 2 = K = 1
(29)

which is unity from (Reference). Summing the right side of Equation 28 gives

k 1 2 | H ( ω + k π ) | 2 | Φ ( ω + k π ) | 2 k 1 2 | H ( ω + k π ) | 2 | Φ ( ω + k π ) | 2
(30)

Break this sum into a sum of the even and odd indexed terms.

k 1 2 | H ( ω + 2 π k ) | 2 | Φ ( ω + 2 π k ) | 2 + k 1 2 | H ( ω + ( 2 k + 1 ) π ) | 2 | Φ ( ω + ( 2 k + 1 ) π ) | 2 k 1 2 | H ( ω + 2 π k ) | 2 | Φ ( ω + 2 π k ) | 2 + k 1 2 | H ( ω + ( 2 k + 1 ) π ) | 2 | Φ ( ω + ( 2 k + 1 ) π ) | 2
(31)
= 1 2 | H ( ω ) | 2 k | Φ ( ω + 2 π k ) | 2 + 1 2 | H ( ω + π ) | 2 k | Φ ( ω + ( 2 k + 1 ) π ) | 2 = 1 2 | H ( ω ) | 2 k | Φ ( ω + 2 π k ) | 2 + 1 2 | H ( ω + π ) | 2 k | Φ ( ω + ( 2 k + 1 ) π ) | 2
(32)

which after using Equation 29 gives

= 1 2 | H ( ω ) | 2 + 1 2 | H ( ω + π ) | 2 = 1 = 1 2 | H ( ω ) | 2 + 1 2 | H ( ω + π ) | 2 = 1
(33)

which gives (Reference). This requires both the scaling and orthogonal relations but no specific normalization of φ(t)φ(t). If viewed as an FIR filter, h(n)h(n) is called a quadrature mirror filter (QMF) because of the symmetry of its frequency response about ππ.

Proof 10 The multiresolution assumptions in (Reference) require the scaling function and wavelet satisfy (Reference) and (Reference)

φ ( t ) = n h ( n ) 2 φ ( 2 t - n ) , ψ ( t ) = n h 1 ( n ) 2 φ ( 2 t - n ) φ ( t ) = n h ( n ) 2 φ ( 2 t - n ) , ψ ( t ) = n h 1 ( n ) 2 φ ( 2 t - n )
(34)

and orthonormality requires

φ ( t ) φ ( t - k ) d t = δ ( k ) φ ( t ) φ ( t - k ) d t = δ ( k )
(35)

and

ψ ( t ) φ ( t - k ) d t = 0 ψ ( t ) φ ( t - k ) d t = 0
(36)

for all kZkZ. Substituting Equation 34 into Equation 36 gives

n h 1 ( n ) 2 φ ( 2 t - n ) h ( ) 2 φ ( 2 t - 2 k - ) d t = 0 n h 1 ( n ) 2 φ ( 2 t - n ) h ( ) 2 φ ( 2 t - 2 k - ) d t = 0
(37)

Rearranging and making a change of variables gives

n , h 1 ( n ) h ( ) 1 2 φ ( y - n ) φ ( y - 2 k - ) d y = 0 n , h 1 ( n ) h ( ) 1 2 φ ( y - n ) φ ( y - 2 k - ) d y = 0
(38)

Using Equation 35 gives

n , h 1 ( n ) h ( ) δ ( n - 2 k - ) = 0 n , h 1 ( n ) h ( ) δ ( n - 2 k - ) = 0
(39)

for all kZkZ. Summing over gives

n h 1 ( n ) h ( n - 2 k ) = 0 n h 1 ( n ) h ( n - 2 k ) = 0
(40)

Separating Equation 40 into even and odd indices gives

m h 1 ( 2 m ) h ( 2 m - 2 k ) + h 1 ( 2 + 1 ) h ( 2 + 1 - 2 k ) = 0 m h 1 ( 2 m ) h ( 2 m - 2 k ) + h 1 ( 2 + 1 ) h ( 2 + 1 - 2 k ) = 0
(41)

which must be true for all integer kk. Defining he(n)=h(2n)he(n)=h(2n), ho(n)=h(2n+1)ho(n)=h(2n+1) and g˜(n)=g(-n)g˜(n)=g(-n) for any sequence gg, this becomes

h e h ˜ 1 e + h o h ˜ 1 o = 0 . h e h ˜ 1 e + h o h ˜ 1 o = 0 .
(42)

From the orthonormality of the translates of φφ and ψψ one can similarly obtain the following:

h e h ˜ e + h o h ˜ o = δ . h e h ˜ e + h o h ˜ o = δ .
(43)
h 1 e h ˜ 1 e + h 1 o h ˜ 1 o = δ . h 1 e h ˜ 1 e + h 1 o h ˜ 1 o = δ .
(44)

This can be compactly represented as

h e h o h 1 e h 1 o h ˜ e h ˜ 1 e h ˜ o h ˜ 1 o = δ 0 0 δ . h e h o h 1 e h 1 o h ˜ e h ˜ 1 e h ˜ o h ˜ 1 o = δ 0 0 δ .
(45)

Assuming the sequences are finite length Equation 45 can be used to show that

h e h 1 o - h o h 1 e = ± δ k , h e h 1 o - h o h 1 e = ± δ k ,
(46)

where δk(n)=δ(n-k)δk(n)=δ(n-k). Indeed, taking the Z-transform of Equation 45 we get using the notation of Chapter: Filter Banks and Transmultiplexers Hp(z)HpT(z-1)=IHp(z)HpT(z-1)=I. Because, the filters are FIR Hp(z)Hp(z) is a (Laurent) polynomial matrix with a polynomial matrix inverse. Therefore the determinant of Hp(z)Hp(z) is of the form ±zk±zk for some integer kk. This is equivalent to Equation 46. Now, convolving both sides of Equation 46 by h˜eh˜e we get

± h ˜ e δ k = h e h 1 o - h o h 1 e h ˜ e = h e h ˜ e h 1 o - h 1 e h ˜ e h o = h e h ˜ e h 1 o + h 1 o h ˜ o h o = h e h ˜ e + h o h ˜ o h 1 o = h 1 o . ± h ˜ e δ k = h e h 1 o - h o h 1 e h ˜ e = h e h ˜ e h 1 o - h 1 e h ˜ e h o = h e h ˜ e h 1 o + h 1 o h ˜ o h o = h e h ˜ e + h o h ˜ o h 1 o = h 1 o .
(47)

Similarly by convolving both sides of Equation 46 by h˜oh˜o we get

h ˜ o δ k = h 1 e . h ˜ o δ k = h 1 e .
(48)

Combining Equation 47 and Equation 48 gives the result

h 1 ( n ) = ± ( - 1 ) n h ( - n + 1 - 2 k ) . h 1 ( n ) = ± ( - 1 ) n h ( - n + 1 - 2 k ) .
(49)

Proof 11 We show the integral of the wavelet is zero by integrating both sides of (Equation 34b) gives

ψ ( t ) d t = n h 1 ( n ) 2 φ ( 2 t - n ) d t ψ ( t ) d t = n h 1 ( n ) 2 φ ( 2 t - n ) d t
(50)

But the integral on the right hand side is A0A0, usually normalized to one and from (Reference) or Equation 9 and Equation 49 we know that

n h 1 ( n ) = 0 n h 1 ( n ) = 0
(51)

and, therefore, from Equation 50, the integral of the wavelet is zero.

The fact that multiplying in the time domain by (-1)n(-1)n is equivalent to shifting in the frequency domain by ππ gives H1(ω)=H(ω+π)H1(ω)=H(ω+π).

Content actions

Download 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 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