Wavelet Coefficients Algorithm for Haar System

Question

In my DSP class a few lectures ago my professor shared a basic algorithm with us for computing wavelet coefficients when the wavelet basis belong to the Haar system. He also shared a circuit with us which looks something like this:

(I made it in tikz rather than having to post a picture of my scribbled notes)

Here is also an example of how the algo works:

Here is a sample input sequence: $$x[n] = 8,2,3,-1,0,4,-2,3$$

Step 1: $$ \underbrace{8 \quad 2}_{\text{Add & divide by 2}} \quad \quad \text{for all four pairs}$$

New Sequence: $$ 5, 1, 2, \frac 12, \color{green} {3,2,-2,-\frac 52}$$

Here the values in green come from subtracting $5$ from $8$, $1$ from $3$ and so on.

Now we repeat step 1 to get:

$$ 3, \frac 54, \color{green} {2, \frac 34}$$

Again values in green come from subtracting $3$ from $5$ and so on.

Now repeat step 1 again:

$$\frac{17}{8}, \color{green} {\frac 78}$$

And now we have our coefficients in order as follows:

$$\textbf{Coefficients} = \{\frac{17}{8}, \frac 78, 2, \frac 34, 3, 2, -2, -\frac 52 \} $$

Now the thing is, I cannot find this circuit or algorithm anywhere. Our course textbook is FSP 2014 by Vetterli but I also use O&S to study. And these topics are not discussed in any of these books. So I was just wondering if anyone had any resource which I could use to get a basic level understanding of wavelets as well as such algorithms and circuits.

Also I was wondering if something similar exists for when our input is continuous-time:

$$x(t) = \sum_{k=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} c_{k,n} \phi_{k,n}$$

where $c_{k,n}$'s are the coefficients and $\phi_{k,n}$'s are the wavelet basis functions (Haar system).

As such I would appreciate if someone could either point to a source or themselves give a basic understanding of why the specific algorithm and circuit work.

Answer 1

I'd suggest

Burrus, C., Gopinath, R. & Guo, H. (1998) Introduction to Wavelets and Wavelet Transforms - A Primer, Prentice Hall International, Inc., Houston, Texas

that seems to be available as a PDF in the link.

Chapter 4 has the following picture which is a slight evolution from the diagram in the OP.

Answer 2

The algorithm you have mentioned is present in many documents but here is a good piece of signal processing literature in terms of an introduction of Wavelets: Wavelets for Computer Graphics: A Primer

As for the circuit you can find it here: Wavelets and Filter Banks, by Gilbert Strang and Truong Nguyen and in Chapter 11 here: Multirate Systems and Filter Banks, P. P. Vaidyanathan.

For the continuous-time case intuitively we should be sampling. But before I share the circuit, you should know that since the Haar System has orthonormal basis (proof), the coefficients can be easily found as such:

$$c_{k,n} = \langle x(t),\phi_{n,k}\rangle$$

And as for the circuit, here is a figure from the Chapter 11 that I mentioned above:

You can find more information on this circuit in Section 11.3 of Vaidyanathan's book linked above.

Answer 3

In short, Haar transform (HT) actually is the simplest form of the discrete Fourier transform (DFT) with the DFT size $N=2$. That is, with $N=2$, every 2 numbers of $x(n)$ are transformed to 2 numbers of $X(k)$, where $n=0,1$ and $k=0,1$. That is,

$X(0) = \frac{x(0)+x(1)}{\sqrt2}$,

and

$X(1) = \frac{x(0)-x(1)}{\sqrt2}$.

Intuitively, $X(0)$ provides the lower frequency band information because it is a summation of $x(0)$ and $x(1)$ corresponding to the DC component, while $X(1)$ provides the higher frequency band information because it is the difference between $x(0)$ and $x(1)$ representing the change between $x(0)$ and $x(1)$.

The HT-based discrete wavelet transform (HT-DWT) is a good starting point to learn DWT. Matlab Wavelet Toolbox has a function 'wavedec' to do DWT, as well as a function 'waverec' to do inverse DWT (IDWT). You may type 'help wavedec' in Matlab command window to see how to use these functions.

Finally, you may like to read the PDF written by Duraisamy Sundararajan, entitled "Fundamentals of the Discrete Haar Wavelet Transform", 2011, which is available at: https://www.dsprelated.com/Documents/d_sundararajan_lpaper.pdf