	Although DSP has long been considered an EE topic, recent developments have also generated signifi cant interest from the computer science community. DSP applications in the consumer market, such as bioinformatics, the MP3 audio format, and MPEG-based cable/satellite television have fueled a desire to understand this technology outside of hardware circles. Designed for upper division engineering and computer science students as well as practicing engineers, Digital Signal Processing Using MATLAB and Wavelets emphasizes the practical applications of signal processing. Over 100 MATLAB examples and wavelet techniques provide the latest applications of DSP, including image processing, games, fi lters, transforms, networking, parallel processing, and sound. The book also provides the mathematical processes and techniques needed to ensure an understanding of DSP theory. Designed to be incremental in diffi culty, the book will benefi t readers who are unfamiliar with complex mathematical topics or those limited in programming experience. Beginning with an introduction to MATLAB programming, it moves through filters, sinusoids, sampling, the Fourier transform, the z-transform and other key topics. An entire chapter is dedicated to the discussion of wavelets and their applications. A CD-ROM (platform independent) accompanies the book and contains source code, projects for each chapter, and the fi gures contained in the book. FEATURES: Contains over 100 short examples in MATLAB used throughout the book Includes an entire chapter on the wavelet transform Designed for the reader who does not have extensive math and programming experience Accompanied by a CD-ROM containing MATLAB examples, source code, projects, and fi gures from the book Contains modern applications of DSP and MATLAB project ideas

Digital Signal Processing Using MATLAB and Wavelets

By Michael Weeks

Chapter 9.9 - Multiresolution

The above discussion is for a single pair of analysis filters. Multiresolution is the process of taking the output from one channel and putting it through another (or more) pair of analysis filters. For the wavelet transform, we do this with the lowpass filter's output. Wavelet packets, however, use an additional filter pair for each channel. We will examine multiresolution starting with the Daubechies four-coefficient wavelet transform, with down-sampling and up-sampling, for two levels of resolution (octaves), as shown in Figure 9.22.

**Figure 9.22:** Two levels of resolution.

Signals $w[n]$ , $w_d[n]$ , $z[n]$ , and $z_d[n]$ are the same as before.

$\begin{displaymath}w[n] = ax[n] + bx[n-1] + cx[n-2] + dx[n-3] \end{displaymath}$

$\begin{displaymath}z[n] = dx[n] - cx[n-1] + bx[n-2] - ax[n-3] \end{displaymath}$

$\begin{displaymath}w_d[n] = w[n], \;\; n\; \mathrm{is \; even, 0\;otherwise} \end{displaymath}$

$\begin{displaymath}z_d[n] = z[n], \;\; n\; \mathrm{is \; even, 0\;otherwise} \end{displaymath}$

To generate $w2[n]$ , $w2_d[n]$ , $z2[n]$ , and $z2_d[n]$ , we first notice that they have the same relationship to $w_d[n]$ as and $z_d[n]$ have to $x[n]$ . In other words, we can reuse the above equations, and replace $x[n]$ with . Also, since there is a down-sampler between $w2[n]$ and , every other value of $w2[n]$ will be eliminated. Signal $w2[n]$ , by definition, is based upon , a down-sampled version of $w[n]$ . Using the original $n$ , therefore, means that we must say that every other value from the even values of $n$ will be eliminated. In other words, the only values that will get through the second down-sampler are the ones where $n$ is evenly divisible by 4.

$\begin{displaymath}w2[n] = a w_d[n] + b w_d[n-1] + c w_d[n-2] + d w_d[n-3] \end{displaymath}$

$\begin{displaymath}z2[n] = d w_d[n] - c w_d[n-1] + b w_d[n-2] - a w_d[n-3] \end{displaymath}$

$\begin{displaymath}w2_d[n] = w2[n], \;\; n\;\mathrm{is\;divisible\;by\;4} \end{displaymath}$

$\begin{displaymath}z2_d[n] = z2[n], \;\; n\;\mathrm{is\;divisible\;by\;4} \end{displaymath}$

Looking now at the reconstruction (synthesis) part, $w2_u[n]$ and $z2_u[n]$ are up-sampled versions of $w2_d[n]$ and $z2_d[n]$ . We have to keep track of values of $n$ that are divisible by 4, and also values of $n$ that are even, but not divisible by 4, such as the number 6. Since we have taken a signal where all of the index terms are already even, the function of the down-sampler followed by the up-sampler is that the "even-even' (divisible by 4) indices are kept, but the "odd-even' indices (divisible by 2, but not divisible by 4, such as 2, 6, 10, etc.) are eliminated, then made to zero by the up-sampler.

$\begin{displaymath}w2_u[n] = w2_d[n] = w2[n], \;\; n\; \mathrm{is\;even}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}w2_u[n] = 0, \;\; n\; \mathrm{is\;odd}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}w2_u[n] \; \mathrm{is\;undefined, \; otherwise} \end{displaymath}$

$\begin{displaymath}z2_u[n] = z2_d[n] = z2[n], \;\; n\; \mathrm{is\;even}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}z2_u[n] = 0, \;\; n\; \mathrm{is\;odd}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}z2_u[n] \; \mathrm{is\;undefined, \; otherwise} \end{displaymath}$

Signals $w2_f[n]$ and $z2_f[n]$ are found as before:

$\begin{displaymath}w2_f[n] = d w2_u[n] + c w2_u[n-1] + b w2_u[n-2] + a w2_u[n-3] \end{displaymath}$

$\begin{displaymath}w2_f[n] = d w2[n] + 0 + b w2[n-2] + 0, \;\; n\; \mathrm{is\;even}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}w2_f[n] = 0 + c w2[n-1] + 0 + a w2[n-3], \;\; n\; \mathrm{is\;odd}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}z2_f[n] = -a z2_u[n] + b z2_u[n-1] - c z2_u[n-2] + d z2_u[n-3] \end{displaymath}$

$\begin{displaymath}z2_f[n] = -a z2[n] + 0 - c z2[n-2] + 0, \;\; n\; \mathrm{is\;even}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}z2_f[n] = 0 + b z2[n-1] + 0 + d z2[n-3], \;\; n\; \mathrm{is\;odd}\texttt{-}\mathrm{even.} \end{displaymath}$

We can finish the reconstruction for the second octave by looking at the result when $w2_f[n]$ and $z2_f[n]$ are added together to recreate $w_d[n]$ . We will call this recreated signal $w_d[n]'$ , until we are certain that it is the same as .

$\begin{displaymath}w_d[n]' = w2_f[n] + z2_f[n] \end{displaymath}$

$\begin{displaymath}w_d[n]' = d w2[n] + b w2[n-2] - a z2[n] - c z2[n-2], \;\; n\; \mathrm{is\;even}\texttt{-}\mathrm{even} \end{displaymath}$

$\begin{displaymath}w_d[n]' = c w2[n-1] + a w2[n-3] + b z2[n-1] + d z2[n-3], \;\; n\; \mathrm{is\;odd}\texttt{-}\mathrm{even} \end{displaymath}$

The important thing to do here is to show that the two signals marked $w_d[n]$ in Figure 9.22 are exactly the same. This means finding the previous expression in terms of $w[n]$ only. First, we will take the expressions for $w2[n]$ and $z2[n]$ , and find $w2[n-k]$ and $z2[n-k]$ .

$\begin{displaymath}w2[n] = a w_d[n] + b w_d[n-1] + c w_d[n-2] + d w_d[n-3] \end{displaymath}$

$\begin{displaymath}z2[n] = d w_d[n] - c w_d[n-1] + b w_d[n-2] - a w_d[n-3] \end{displaymath}$

$\begin{displaymath}w2[n-k] = a w_d[n-k] + b w_d[n-k-1] + c w_d[n-k-2] + d w_d[n-k-3] \end{displaymath}$

$\begin{displaymath}z2[n-k] = d w_d[n-k] - c w_d[n-k-1] + b w_d[n-k-2] - a w_d[n-k-3] \end{displaymath}$

Now, we can plug these into the previous $w_d[n]$ expressions.

$\begin{eqnarray*} w_d[n]' &=& d (a w_d[n] + b w_d[n-1] + c w_d[n-2] + d w_d[n-3... ... a w_d[n-6]), \;\; n \; \mathrm{is\;odd}\texttt{-}\mathrm{even} \end{eqnarray*}$

Rewriting these expressions and lining them up into columns gives us:

is even-even:

$\begin{displaymath} \begin{array}{ccccc} w_d[n]' = & & & & \ad w_d[n] & +\; ... ...] & -\; bc w_d[n-4] \+\; ac w_d[n-5]. & & & & \end{array} \end{displaymath}$

is odd-even:

$\begin{displaymath} \begin{array}{ccccc} w_d[n]' = & & & & \ac w_d[n-1] & +\;... ...4] & +\; bd w_d[n-5] \-\; ad w_d[n-6]. & & & & \end{array} \end{displaymath}$

Canceling out terms gives us:

is even-even:

$\begin{displaymath} \begin{array}{cccc} w_d[n]' = & bd w_d[n-1] & +\; dd w_d[n-3... ...-3] & \& & +\; cc w_d[n-3] & +\; ac w_d[n-5] . \end{array} \end{displaymath}$

is odd-even:

$\begin{displaymath} \begin{array}{cccc} w_d[n]' = & ac w_d[n-1] & +\; cc w_d[n-3... ...-3] & \& & +\; dd w_d[n-3] & +\; bd w_d[n-5] . \end{array} \end{displaymath}$

Examining the above equations, we see that we have the same expression for when $n$ is even-odd as when it is even-even. Therefore, we can rewrite the above expression, with the note that $n$ must be even. We know from the previous section that $ac = -bd$ , so the terms with $w_d[n-1]$ and $w_d[n-5]$ will cancel out. This leaves us with $w_d[n]' = (aa + bb + cc + dd) w_d[n-3]$ . As previously noted, $(aa + bb + cc + dd) = 1$ , so we get the final expression for $w_d[n]' = w_d[n-3]$ . The reconstructed $w_d[n]'$ is the same as a delayed version of the original $w_d[n]$ . This is no surprise, since we have simply inserted a copy of the 1-octave filter bank structure between the original and the reconstruction. When we looked at the filter bank structure for 1-octave, we saw that the result $y[n]$ was a delayed version of $x[n]$ .

The next step is to take the reconstructed signal, $w_d[n]$ , and recombine it with $z_d[n]$ to get $y[n]$ . Note that in the analysis (top part) of Figure 9.22 and the $w_d[n]'$ in the synthesis (bottom part) of this figure must be exactly the same. But we saw above that they are not exactly the same, since is a delayed version of . We can deal with this in a couple of ways. If we are designing hardware to perform the wavelet transform, we can simply add three (that is, length of filter $-1$ ) delay units to channel with the $z_d[n]$ signal. If we are writing software to do this, we can put three zeros before , or we could shift $w_d[n]'$ forward by three positions, getting rid of the first three values. The important thing is that and are properly aligned. We will assume that this second method has been used to "correct' to be exactly equal to $w_d[n]$ . If we were to use the first method of delaying $z_d[n]$ , then the output would be reconstructed using $w_d[n-3]$ and $z_d[n-3]$ , implying that the output would be delayed by an additional three units. That is, instead of having $y[n] = x[n-3]$ as the result, we would have $y[n] = x[n-3-3] = x[n-6]$ .

Tracing the path of $w_d[n]$ and $z_d[n]$ is very similar to that of $w2_d[n]$ and $z2_d[n]$ .

$\begin{displaymath}w_u[n] = w_d[n] = w[n], \;\; n\;\mathrm{is\;even} \end{displaymath}$

$\begin{displaymath}w_u[n] = 0, \;\; n\;\mathrm{is\;odd} \end{displaymath}$

$\begin{displaymath}z_u[n] = z_d[n] = z[n], \;\; n\;\mathrm{is\;even} \end{displaymath}$

$\begin{displaymath}z_u[n] = 0, \;\; n\;\mathrm{is\;odd} \end{displaymath}$

Notice that the "otherwise' case has been dropped, since $n$ is either odd or even. Finding $w_f[n]$ and $z_f[n]$ is just like finding $w2_f[n]$ and $z2_f[n]$ :

$\begin{displaymath}w_f[n] = d w_u[n] + c w_u[n-1] + b w_u[n-2] + a w_u[n-3] \end{displaymath}$

$\begin{displaymath}w_f[n] = d w[n] + 0 + b w[n-2] + 0, \;\; n\; \mathrm{is \; even} \end{displaymath}$

$\begin{displaymath}w_f[n] = 0 + c w[n-1] + 0 + a w[n-3], \;\; n\; \mathrm{is \; odd} \end{displaymath}$

$\begin{displaymath}z_f[n] = -a z_u[n] + b z_u[n-1] - c z_u[n-2] + d z_u[n-3] \end{displaymath}$

$\begin{displaymath}z_f[n] = -a z[n] + 0 - c z[n-2] + 0, \;\; n\; \mathrm{is \; even} \end{displaymath}$

$\begin{displaymath}z_f[n] = 0 + b z[n-1] + 0 + d z[n-3], \;\; n\; \mathrm{is \; odd.} \end{displaymath}$

Adding $w_f[n]$ to $z_f[n]$ produces $y[n]$ , just as we saw for the single-octave case. The important thing to notice is that the reconstruction is exactly the same as the single-octave case, provided that $w_d[n]$ is exactly the same in both the analysis and synthesis (top and bottom) parts of Figure 9.22.

Here we have seen that we can make the filter bank structure work recursively, and still get a perfectly reconstructed signal. While this section uses only two levels of recursion (octaves), it should be clear that we can use as many octaves as we want. The only limitation is that imposed by the length of the input signal, since every octave uses half the number of inputs as the octave above it. In other words, $w_d[n]$ exists only for even values of the index $n$ , while the input signal $x[n]$ has values for even and odd values of $n$ . If $x[n]$ has 16 samples, then would have 8, and $w2_d[n]$ would have 4, etc.

< Previous Excerpt Next Excerpt >

Purchase This Book

TABLE OF CONTENTS

Chapter 9.9 - Multiresolution

Contact Preferences

This is embarrasing...

Customize Your GlobalSpec Experience

Select Your Free Newsletters

Industry Newsletters

Select Your Free Product Alerts

This is embarrasing...