In a previous post we introduced Walsh functions. We showed that this set of functions is orthogonal and complete. In this post we generalize the Walsh function system such that the orthonormality and completeness of the new Walsh function system still holds. A table of contents for the posts on Walsh functions can be found here.

The definition of the Walsh functions from the previous post

is based on the dyadic expansion of and Using a -adic expansion for some integer then yields generalized Walsh functions.

**1. Walsh functions in base **

Let now be an integer and The Walsh functions in base are functions

where We define

Let the base expansion of be given by

where Further, let the base expansion of be given by

where Then the th Walsh function in base is given by

For any given base it can be shown that the system

is a complete orthonormal system of

Further generalizations of Walsh functions in base can be obtained by considering other representations of nonnegative integers and real numbers in We do not pursue this direction here.

There is another way of generalizing Walsh functions which is based on groups. Before we introduce Walsh functions over groups we consider group characters. For our purposes it is sufficient to consider only finite abelian groups. (The material below requires some knowledge of elementary abstract algebra.)

Definition(Group character)

Let be a finite abelian group and let Then a function is called a group character if

Let be the identity element in i.e. we have for all Then for any we have

By dividing this equation by we obtain

**Example**

Let be an integer and let be the cyclic group of order where the operation is addition modulo (Here we identify the element with the nonnegative integer ) Let Then, for each we can define a character by

(Here, by we simply mean the product of the integers and For we obtain the trivial character for all

The characters of the finite cyclic group defined above are also all possible characters. Assume that is a character on Then for some This defines the character completely, since

Since it follows that

Therefore and hence Let such that i.e. for some integer Then it follows that

The function for all is a character. It is called the trivial character, which we denote by in the following. Another property of characters is the following. Let be a finite abelian group and let and be two characters on Then the function

is again a character on That is, the product of two characters is again a character. (The proof is left as exercise.)

Further, if is a character on then the complex conjugate i.e. the function for all is also a character. Notice that the trivial character. Hence it follows that the set of all characters of a finite abelian group which we denote by is again a group. The group is called the dual group.

**Example**

The dual group of the finite cyclic group is the set of characters

For with we have

Hence we can define a mapping

This defines a group isomorphism, since is bijective and

Let be a finite abelian group. By the fundamental theorem of finitely generated abelian groups it follows that is isomorphic to

where are prime numbers (not necessarily distinct) and

**Example**

Consider This is a finite abelian group which is isomorphic to We can identify the elements by

That is, the rule here is and For instance and in See also the chinese remainder theorem.

**Remark**

Notice that the group is different from the group . For instance, the group is cyclic, since On the other hand, the group is not cyclic. We have Further, the additive group of a finite field where is a prime and is isomorphic to This is the main reason for studying Walsh functions over groups in the context of digital nets over a finite field

Since we have found all characters for the finite cyclic group already, we can now find all the characters for arbitrary finite abelian groups Let the finite abelian group be isomorphic to Then the functions

are characters of where As for cyclic groups, it can be shown that these are all characters. Hence the dual group of is the set of characters

(The details are left as exercise.)

Let be a finite abelian group. Let then we write the characters of using the notation

The following property of characters is important.

Lemma

Let be a finite abelian group and let be the dual group of characters. Then

To prove the result for the case that is a cyclic group, we just note that for any integer we have

The details for arbitrary finite abelian groups are left as exercise.

We need one more extension of the ideas above. Let be a finite abelian group and consider the infinite group

Here, the operation is defined component-wise, that is, for we write In this case, the functions

are characters of the group Notice that for any the groups are isomorphic to a subgroup of and the functions where are the characters of Hence the functions are characters of and therefore in the set

**3. Walsh functions over finite abelian groups**

We can now introduce Walsh functions over finite abelian groups.

Let

and

Let be a finite abelian group with elements. We now map and to and respectively. To do so, let be a bijection such that (here is the identity element in and is the identity element in Now let

and

Then maps to and we can use to map to

Definition(Walsh functions over a finite abelian group)

Let be a finite abelian group. Then, for the th Walsh function over the group is defined bywhere and are as defined above. For we set for all

Let and be given by for all Then it can be shown that for all and all with (the details are left as an exercise).

**4. Explicit form of Walsh functions over groups for **

Let now be a finite abelian group with elements, that is, We define the function by its components, that is, let be given by where

with for Then we have

where and

**Example**

Let Then the mapping is given by

For instance, let and Then and Then

For we obtain and therefore

Notice that

and

This illustrates that and In general unless is isomorphic $\mathbb{Z}_b$ and is chosen in a particular way (the details are left as exercise).

The following theorem can be shown using similar arguments as for Walsh functions in base (see the previous post on Walsh functions for a proof idea).

Theorem

Let be a finite abelian group. Then the Walsh function systemis a complete orthonormal system of

The details are left as exercise.

The Walsh-Fourier transform is of particular interest to me as it holds the potential for an analysis of cardiac signals that is far less energy-consuming than the regular Fast Fourier transform. While studying these functions it became evident that their algebraic and combinatorial properties were just as fascinating as their analytic ones. Though I confess I have not studied this blog in exquisite detail I believe that I will come back to it again and again for deeper insight. Thanx for putting in the effort to do this.