Walsh functions II: Walsh functions in general base and Walsh functions over groups

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

\displaystyle \mathrm{wal}_k(x)=(-1)^{\kappa_0 x_1 + \cdots + \kappa_{a-1} x_a}

is based on the dyadic expansion of x=x_1 2^{-1} + x_2 2^{-2} + \cdots and k=\kappa_0 + \kappa_1 2 + \cdots + \kappa_{a-1} 2^{a-1}. Using a b-adic expansion for some integer b \ge 2 then yields generalized Walsh functions.

1. Walsh functions in base b

Let now b \ge 2 be an integer and \omega_b=\mathrm{e}^{2\pi\mathrm{i}/b}. The Walsh functions in base b are functions

\displaystyle _b\mathrm{wal}_k:[0,1)\to \mathbb{T},

where \mathbb{T}=\{z\in \mathbb{C}: |z|=1\}. We define

\displaystyle _b\mathrm{wal}_0(x)=1.

Let the base b expansion of k \in \mathbb{N} be given by

k =\kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1},

where \kappa_0,\ldots, \kappa_{a-1} \in \{0,\ldots, b-1\}. Further, let the base b expansion of x \in [0,1) be given by

\displaystyle x=\frac{x_1}{b}+\frac{x_2}{b^2} + \cdots,

where x_1, x_2, \ldots \in \{0,\ldots, b-1\}. Then the kth Walsh function in base b is given by

\displaystyle _b\mathrm{wal}_k(x)= \omega_b^{\kappa_0 x_1 + \cdots + \kappa_{a-1} x_a}.

For any given base b \ge 2, it can be shown that the system

\displaystyle _b\mathrm{wal}_0, \;_b\mathrm{wal}_1, \;_b\mathrm{wal}_2,\ldots

is a complete orthonormal system of L_2([0,1]).

Further generalizations of Walsh functions in base b can be obtained by considering other representations of nonnegative integers and real numbers in [0,1). 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.)

2. Group characters

Definition (Group character)
Let (G, \circ) be a finite abelian group and let \mathbb{T}=\{z\in \mathbb{C}: |z|=1\}. Then a function \chi:G\to\mathbb{T} is called a group character if

\displaystyle \chi(g_1 \circ g_2) = \chi(g_1) \chi(g_2) \quad \mbox{for all } g_1,g_2 \in G.

Let e\in G be the identity element in G, i.e. we have e\circ g = g for all g\in G. Then for any g\in G we have

\displaystyle \chi(g) = \chi(e \circ g) = \chi(e) \chi(g).

By dividing this equation by \chi(g) \in \mathbb{T} we obtain \chi(e) = 1.

Example
Let b \ge 2 be an integer and let G=\mathbb{Z}_b=\{0,1, \ldots, b-1\} be the cyclic group of order b, where the operation is addition modulo b. (Here we identify the element a \in \mathbb{Z}_b with the nonnegative integer a.) Let \omega_b= \mathrm{e}^{2\pi \mathrm{i}/b}. Then, for each a\in \mathbb{Z}_b we can define a character \chi_a by

\displaystyle \chi_a(g)= \omega_b^{a g} \quad \mbox{for all } g \in \mathbb{Z}_b.

(Here, by a g we simply mean the product of the integers {}a and {}g.) For a=0 we obtain the trivial character \chi_0(g) = 1 for all g \in \mathbb{Z}_b.

The characters of the finite cyclic group \mathbb{Z}_b defined above are also all possible characters. Assume that \chi is a character on \mathbb{Z}_b. Then \chi(1)= \omega_b^x for some x \in [0,b). This defines the character completely, since

\displaystyle \chi(a) = \chi(1+\cdots + 1) = \chi(1)\cdots \chi(1) = \omega_b^x \cdots \omega_b^x = \omega_b^{x a}.

Since \chi(b) = \chi(0) = 1 it follows that

\displaystyle \omega_b^{x b} = 1.

Therefore x b \equiv 0 \pmod{b} and hence x \in \mathbb{Z}. Let a\in \mathbb{Z}_b such that a \equiv x \pmod{b}, i.e. 0 \le a = x - k b \textless b for some integer {}k. Then it follows that

\displaystyle \chi(g) = \omega_b^{xg} = \omega_b^{a g - k b g} = \omega_b^{a g} (\omega_b^{b})^{-kg} = \omega_b^{ag} (1)^{-kg} = \omega_b^{ag} = \chi_a(g).

\Box

The function \chi(g)=1 for all g\in G is a character. It is called the trivial character, which we denote by \chi_0 in the following. Another property of characters is the following. Let {}G be a finite abelian group and let \chi and \eta be two characters on {}G. Then the function

\displaystyle (\chi\cdot \eta)(g) := \chi(g) \eta(g) \quad \mbox{for all } g \in G

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

Further, if \chi is a character on {}G, then the complex conjugate \overline{\chi}, i.e. the function \eta(g)= \overline{\chi(g)} for all g \in G, is also a character. Notice that \chi \cdot \overline{\chi} = \chi_0, the trivial character. Hence it follows that the set of all characters of a finite abelian group G, which we denote by \widehat{G}, is again a group. The group \widehat{G} is called the dual group.

Example
The dual group \widehat{\mathbb{Z}_b} of the finite cyclic group \mathbb{Z}_b is the set of characters

\displaystyle \chi_0, \chi_1,\ldots, \chi_{b-1}.

For x,y,z \in \mathbb{Z}_b with z \equiv x+y \pmod{b} we have

\displaystyle \chi_x \cdot \chi_y = \chi_z.

Hence we can define a mapping

\displaystyle \begin{array}{rcl} \Gamma:\mathbb{Z}_b & \to & \widehat{\mathbb{Z}_b} \\ && \\ a &;; \mapsto & \chi_a. \end{array}

This defines a group isomorphism, since \Gamma is bijective and

\displaystyle \Gamma(x + y) = \Gamma(x) \Gamma(y) \quad \mbox{for all } x, y \in \mathbb{Z}_b.

\Box

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

\displaystyle \prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}},

where p_1,\ldots, p_r are prime numbers (not necessarily distinct) and \alpha_1,\ldots, \alpha_r \in \mathbb{N}.

Example
Consider \mathbb{Z}_6. This is a finite abelian group which is isomorphic to \mathbb{Z}_2 \times \mathbb{Z}_3. We can identify the elements by

\displaystyle \begin{array}{rcl} 0 & \leftrightarrow & (0,0) \\ 1 & \leftrightarrow & (1,1) \\ 2 & \leftrightarrow & (0,2) \\ 3 & \leftrightarrow & (1,0) \\ 4 & \leftrightarrow & (0, 1) \\ 5 & \leftrightarrow & (1,2) \end{array}

That is, the rule here is a \leftrightarrow (a \pmod{2}, a\pmod{3}) and (u,v) + (x,y) = (u+x \pmod{2}, v+y\pmod{3}). For instance 5+5\equiv 4\pmod{6} and (1,2)+(1,2) \equiv (2 \pmod{2},4 \pmod{3}) \equiv (0,1) in \mathbb{Z}_2\times \mathbb{Z}_3. See also the chinese remainder theorem.
\Box

Remark
Notice that the group \mathbb{Z}_{p^\alpha} is different from the group \mathbb{Z}_p^\alpha. For instance, the group \mathbb{Z}_4 = \{0,1,2,3\} is cyclic, since 1+1=2, 1+1+1=3, 1+1+1+1=0. On the other hand, the group \mathbb{Z}_2^2=\mathbb{Z}_2\times \mathbb{Z}_2=\{(0,0), (1,0), (0,1), (1,1)\} is not cyclic. We have (1,0)+(1,0)=(0,0), (0,1)+(0,1)=(0,0), (1,1)+(1,1)=(0,0). Further, the additive group of a finite field \mathbb{F}_{p^r}, where {}p is a prime and r \in \mathbb{N}, is isomorphic to \mathbb{Z}_p^r. This is the main reason for studying Walsh functions over groups in the context of digital nets over a finite field \mathbb{F}_{p^r}.
\Box

Since we have found all characters for the finite cyclic group \mathbb{Z}_b already, we can now find all the characters for arbitrary finite abelian groups {}G. Let the finite abelian group {}G be isomorphic to \prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}. Then the functions

\displaystyle \chi_{(a_1,\ldots, a_r)}(g_1,\ldots, g_r) := \prod_{i=1}^r \chi_{a_i}(g_i)

are characters of \prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}, where a_i \in \mathbb{Z}_{p_i^{\alpha_i}}. As for cyclic groups, it can be shown that these are all characters. Hence the dual group of \prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}} is the set of characters

\displaystyle \chi_{(a_1,\ldots, a_r)} : a_i \in \mathbb{Z}_{p_i^{\alpha_i}} \quad \mbox{for } 1 \le i \le r.

(The details are left as exercise.)

Let {}G be a finite abelian group. Let a,g\in G, then we write the characters of {}G using the notation \chi_a(g) = \omega_b^{ag}.

The following property of characters is important.

Lemma
Let {}G be a finite abelian group and let \widehat{G} be the dual group of characters. Then

\displaystyle \begin{array}{rl}  \forall \chi \in \widehat{G}\setminus \{\chi_0\}:  & \sum_{g \in G} \chi(g)  = 0, \\ & \\ \forall g \in G\setminus\{0\}: & \sum_{\chi \in \widehat{G}} \chi(g) = 0. \end{array}

To prove the result for the case that {}G is a cyclic group, we just note that for any integer 0<a<b we have

\displaystyle \sum_{g=0}^{b-1} \omega_b^{a g} = \frac{1-\omega_b^{a b}}{1-\omega_b} = 0.

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

We need one more extension of the ideas above. Let (G,+) be a finite abelian group and consider the infinite group

\displaystyle G^{\mathbb{N}} = \{(g_1,g_2, \ldots): g_i \in G\}.

Here, the operation is defined component-wise, that is, for \boldsymbol{g} = (g_1,g_2,\ldots), \boldsymbol{h}=(h_1, h_2,\ldots) \in G, we write \boldsymbol{g}+\boldsymbol{h} = (g_1+h_1, g_2+h_2,\ldots) \in G^{\mathbb{N}}. In this case, the functions

\displaystyle \chi_{\boldsymbol{a}}= \prod_{i=1}^\infty \chi_{a_i} \quad \mbox{where } a_i \in G \mbox{ and } a_i = 0 \mbox{ for } i \ge K \mbox{ for some } K \in \mathbb{N}, \qquad (1)

are characters of the group G^{\mathbb{N}}. Notice that for any K \in\mathbb{N} the groups G^K are isomorphic to a subgroup of G^{\mathbb{N}} and the functions \prod_{i=1}^K \chi_{a_i}, where a_i \in G, are the characters of G^K. Hence the functions (1) are characters of G^{\mathbb{N}} and therefore in the set \widehat{G^{\mathbb{N}}}.

3. Walsh functions over finite abelian groups

We can now introduce Walsh functions over finite abelian groups.

Let

\displaystyle x=\frac{x_1}{b}+\frac{x_2}{b^2} + \cdots \in [0,1)

and

\displaystyle k= \kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1} \in \mathbb{N}.

Let {}G be a finite abelian group with {}b elements. We now map {}x and {}k to G^{\mathbb{N}} and \widehat{G^{\mathbb{N}}}, respectively. To do so, let \phi:\mathbb{Z}_b \to G be a bijection such that \phi(0) = e (here {}0 is the identity element in \mathbb{Z}_b and {}e is the identity element in {}G.) Now let

\displaystyle \psi(x) = (\phi(x_1), \phi(x_2),\ldots) \in G^{\mathbb{N}}

and

\displaystyle \eta(k) = (\phi(\kappa_0), \ldots, \phi(\kappa_{a-1}), e, e, \ldots ) \in G^{\mathbb{N}}.

Then \psi maps x\in [0,1) to \psi(x) \in G^{\mathbb{N}} and we can use \eta to map k\in \mathbb{N}_0 to \chi_{\eta(k)} \in \widehat{G^{\mathbb{N}}}.

Definition (Walsh functions over a finite abelian group)
Let {}G be a finite abelian group. Then, for k\in\mathbb{N}, the kth Walsh function \mathrm{wal}_k^G over the group G is defined by

\displaystyle \begin{array}{rcl} \mathrm{wal}_k^G: [0,1) & \to & \mathbb{T} \\ && \\ x & \mapsto & \chi_{\eta(k)}(\psi(x)) \end{array}

where \psi and \eta are as defined above. For k=0 we set \mathrm{wal}_0^G(x) = 1 for all x \in [0,1).

Let G=\mathbb{Z}_b and \phi:\mathbb{Z}_b\to G be given by \phi(a) = a for all a \in \mathbb{Z}_b. Then it can be shown that \mathrm{wal}_k^{\mathbb{Z}_b} = \,_b\mathrm{wal}_k for all k\in \mathbb{N}_0 and all b \in \mathbb{N} with b \ge 2 (the details are left as an exercise).

4. Explicit form of Walsh functions over groups for G=\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}

Let now G=\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}} be a finite abelian group with b elements, that is, b = \prod_{i=1}^r p_i^{\alpha_i}. We define the function \phi by its components, that is, let \phi:\mathbb{Z}_b\to G be given by \phi(a)=(\phi_1(a),\ldots, \phi_r(a)), where

\displaystyle \phi_i:\mathbb{Z}_b \to \mathbb{Z}_{p_i^{\alpha_i}}  \quad \mbox{for } 1 \le i \le r

with \phi_i(0) = 0 for 1 \le i \le r. Then we have

\displaystyle \mathrm{wal}_k^G(x) = \prod_{j=1}^a \prod_{i=1}^r \omega_{p_i^{\alpha_i}}^{\phi_i(\kappa_{j-1}) \phi_i(x_j) },

where k = \kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1} \in \mathbb{N} and x=\frac{x_1}{b} + \frac{x_2}{b^2} + \cdots \in [0,1).

Example
Let G=\mathbb{Z}_2 \times \mathbb{Z}_2. Then the mapping \phi is given by

\displaystyle \begin{array}{rcl} 0 & \mapsto & (0,0) \\ && \\ 1 & \mapsto & (1,0) \\ && \\ 2 & \mapsto & (0,1) \\ && \\ 3 & \mapsto & (1,1)  \end{array}

For instance, let k=1 and x = 1/2. Then \eta(1) = ((1,0),(0,0), \ldots) and \psi(1/2) = \psi(2/4) =  ((0,1),(0,0),\ldots). Then

\displaystyle \mathrm{wal}_1^{G}(1/2) = (-1)^{1 \cdot 0 + 0 \cdot 1} = 1.

For x=3/4 we obtain \psi(3/4)= ((1,1), (0,0),\ldots) and therefore

\displaystyle \mathrm{wal}_1^{G}(3/4) = (-1)^{1\cdot 1 + 0 \cdot 1} = -1.

Notice that

\displaystyle _2\mathrm{wal}_1(1/2) = (-1)^{1 \cdot 1} = -1

and

\displaystyle _4\mathrm{wal}_1(3/4)= \omega_4^{1 \cdot 3} = \omega_4^{3}.

This illustrates that \mathrm{wal}_k^{\mathbb{Z}_2\times \mathbb{Z}_2} \neq \,_2\mathrm{wal}_k and \mathrm{wal}_k^{\mathbb{Z}_2 \times \mathbb{Z}_2} \neq \,_4\mathrm{wal}_k. In general \mathrm{wal}_k^G \neq \,_b\mathrm{wal}_k unless G is isomorphic $\mathbb{Z}_b$ and \phi is chosen in a particular way (the details are left as exercise).
\Box

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

Theorem
Let {}G be a finite abelian group. Then the Walsh function system

\displaystyle \mathrm{wal}^G_0, \mathrm{wal}^G_1, \mathrm{wal}^G_2,\ldots

is a complete orthonormal system of L_2([0,1]).

The details are left as exercise.

Advertisements

One response to “Walsh functions II: Walsh functions in general base and Walsh functions over groups

  1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s