# Wavelet Coefficients Algorithm for Haar System

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.

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.

• Thanks for the suggestion! It's a really nice book it seems for an intro to wavelets. However, I couldn't find the algorithm I mentioned above. Is there perhaps another resource which has details on this algorithm?
– user64710
Commented Jun 3, 2023 at 7:19

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:

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

• Thanks for sharing this paper. I wonder why there is a slight difference between the algorithm I explained above and the algorithm explained in this paper. Did my professor teach it incorrectly?
– user64710
Commented Jun 3, 2023 at 21:06
• @Caporal Fourrier What do you mean by "a slight difference" ? Are you talking about the scaling constant difference: one is divided by $\sqrt{2}$ while another is divided by $2$ ? If this is your concern, you do not need to worry about it much. It is just a difference of scaling. Commented Jun 4, 2023 at 0:21
• @Caporal Fourrier $\sqrt{2}$ is used in the division is simply for the purpose of keeping the energy unchanged before and after each stage of HT, that is, to make $x(0)^2+x(1)^2=X(0)^2+X(1)^2$. In some applications where this is not critical, people may like to do the division with 2 for a simpler implementation (since dividing a number by 2 can be implemented by shifting the number by 1 bit in computers), which is much easier than the division with $\sqrt{2}$. Commented Jun 4, 2023 at 2:09
• Understood. Thanks a lot!
– user64710
Commented Jun 4, 2023 at 8:56