Hi,
I have a little question. Why Walsh functions are orthonormal basis in L2[0,1] ?
Apart from the first Walsh function, which is identically 1, all the others are equal to +1 on half of the interval [0,1] and –1 on the remaining half. Also, the product of any two Walsh functions is again a Walsh function (the first 2^n functions form a multiplicative group. It follows that the integral over [0,1] of the product of two Walsh functions is zero. Hence they form an orthogonal set.
The mathematical definition is complicated, using something called the Gray code. But there is a reasonably understandable inductive way to define these functions, taking them in blocks of 2^n at a time.
Start with W_1, which is the constant function 1. To get W_2, you split the unit interval in two, and define W_2(x) = W_1(x) on the first half of the interval and W_2(x) = –W_1(x) on the second half. (I'm ignoring what happens at the point x=1/2, because the value at a single point is irrelevant when it comes to integration. If you want to be fussy, replace closed intervals by half-open intervals in what follows.)
To get W_3 and W_4, you apply the same process to W_2 and W_1 respectively. (Note the reversal of the ordering: W_3 comes from W_2, and W_4 from W_1.) In more detail, here's how you construct W_3 from W_2. Take each of the two intervals on which W_2 is constant, split it in half, and define W_3 to be the same as W_2 on the first of each pair of half-intervals, and –W_2 on the second one.
The inductive step works like this. Suppose that W_k has been defined for 1≤k≤2^n, and that it is constant on each interval $\displaystyle \left[\tfrac{j-1}{2^n},\tfrac{j}{2^n}\right]\ (1\leqslant j\leqslant2^n)$. For 1≤k≤2^n, define $\displaystyle W_{2^n+k}$ to be equal to $\displaystyle W_{2^n+1-k}$ on each interval $\displaystyle \left[\tfrac{2j-2}{2^{n+1}},\tfrac{2j-1}{2^{n+1}}\right]$, and equal to $\displaystyle -W_{2^n+1-k}$ on each interval $\displaystyle \left[\tfrac{2j-1}{2^{n+1}},\tfrac{2j}{2^{n+1}}\right]$, for $\displaystyle 1\leqslant j\leqslant2^n$. In that way, W_k is defined for all k up to and including $\displaystyle k=2^{n+1}$.
Notice again the reversal of the ordering: $\displaystyle W_{2^n+1}$ comes from $\displaystyle W_{2^n}$, and so on until $\displaystyle W_{2^{n+1}}$ comes from $\displaystyle W_1$.