In this post I summarize some useful properties of Walsh functions. These functions were introduced by Joseph Walsh in

Another paper where many ideas can be found is by Nathan Fine

In this exposition here we only concentrate on the simplest case of base and dimension .

We write for the set of natural numbers and for the set of nonnegative integers .

A table of contents for the posts on Walsh functions can be found here.

**Definition of Walsh functions**

Definition(Walsh function)

Let be a nonnegative integer and be a real number. Let the binary representation of and be given bywhere . Then the th Walsh function

is given by

and further .

The following image shows the graph of for

First note that Walsh functions are piecewise constant. For we have for all . Let with binary representation . For for some with binary representation we have

Then

and hence is constant on intervals of the form .

**Walsh functions are orthonormal**

We now show that Walsh functions are orthogonal with respect to the inner product

where are real-valued functions. In the following we write instead of .

Let , then

Now let with have binary representations

Without loss of generality assume that . Then

Since , there is an such that (where we set if ) and therefore . This implies that

Proposition

The Walsh functions , where , are orthonormal with respect to the inner product, i.e. for all we have

**Walsh functions are complete**

We now show that the Walsh functions form a complete orthonormal system in (see the post on the mean square convergence of Fourier series for an analoguous result for Fourier series).

Definition(Walsh polynomial)

Let and be real numbers. The functionis called a

Walsh polynomial.

As in the Fourier case, see here, we define the Dirichlet kernel for Walsh functions.

Definition(Dirichlet kernel for Walsh functions)

The Walsh polynomialis called the

Walsh-Dirichlet kernel.

Lemma

For any we have

**Proof**

Let . If , then . Using the definition of the Dirichlet kernel we have

If , then there is an such that . Then

since

For with and we define the digit-wise addition and subtraction by

where are given by and .

An immediate extension of the above lemma is that for any where for some we have

The following result is equivalent to the completeness of the Walsh function system.

Lemma

Let be Lebesgue integrable such thatThen for almost all .

*Proof*

Let

Then by the fundamental theorem of calculus, is continuous and differentiable almost everywhere with . Then implies that .

We proceed by induction on . Assume that for a given integer we have shown already that for all . For any we have

since and therefore

Since for even we have , it follows that for all .

Hence for all and all . Since is continuous and the numbers are dense in the interval it follows that is everywhere. Further, almost everywhere, and hence for almost all .

Definition

Let . Thenare called the

Walsh coefficientsof the function . The formal sumis the

Walsh seriesof . Further we define the partial sumsof the Walsh series of .

We define the -norm by

Theorem(Bessel’s inequality)

Let . Then

**Proof**

Let , then

Therefore is orthogonal to and we can use Pythagoras theorem to obtain

Since the result follows by considering the limit of .

Note that for any , Bessel’s inequality implies that is a Cauchy sequence ( for ) and therefore converges to a function with .

Theorem

Let . Then

**Proof**

Let . Then for all we have

If , then set . Then is orthogonal to all functions , and . But this contradicts the lemma above and hence .

Theorem(Parseval’s identity)

Let . Then

**Proof**

We have

Since as the result follows.

The next post on Walsh functions deals with generalizations of Walsh functions to arbitrary base and, more generally, to Walsh functions over groups.

This entry printed to pdf can be downloaded here

Pingback: Walsh functions | Biofirecorp