Walsh function

We define the sequence of Walsh functions ${\displaystyle W_{k}:[0,1]\rightarrow \{-1,1\}}$, ${\displaystyle k\in \mathbb {N} }$ as follows.

For any natural number k, and real number ${\displaystyle x\in [0,1]}$, let

${\displaystyle k_{j}}$ be the jth bit in the binary representation of k, starting with ${\displaystyle k_{0}}$ as the least significant bit, and

${\displaystyle x_{j}}$ be the jth bit in the fractional binary representation of ${\displaystyle x}$, starting with ${\displaystyle x_{1}}$ as the most significant fractional bit.

Then, by definition

${\displaystyle W_{k}(x)=(-1)^{\sum _{j=0}^{\infty }k_{j}x_{j+1}}}$

In particular, ${\displaystyle W_{0}(x)=1}$ everywhere on the interval, since all bits of k are zero.

Notice that ${\displaystyle W_{2^{m}}}$ is precisely the Rademacher function r_m. Thus, the Rademacher system is a subsystem of the Walsh system. Moreover, every Walsh function is a product of Rademacher functions:

${\displaystyle W_{k}(x)=\prod _{j=0}^{\infty }r_{j}(x)^{k_{j}}}$

Walsh functions and trigonometric functions are both systems that form a complete, orthonormal set of functions, an orthonormal basis in the Hilbert space ${\displaystyle L^{2}[0,1]}$ of the square-integrable functions on the unit interval. Both are systems of bounded functions, unlike, say, the Haar system or the Franklin system.

Both trigonometric and Walsh systems admit natural extension by periodicity from the unit interval to the real line. Furthermore, both Fourier analysis on the unit interval (Fourier series) and on the real line (Fourier transform) have their digital counterparts defined via Walsh system, the Walsh series analogous to the Fourier series, and the Hadamard transform analogous to the Fourier transform.

The Walsh system ${\displaystyle \{W_{k}\},k\in \mathbb {N} _{0}}$ is an abelian multiplicative discrete group isomorphic to ${\displaystyle \coprod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z} }$, the Pontryagin dual of the Cantor group ${\displaystyle \prod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z} }$. Its identity is ${\displaystyle W_{0}}$, and every element is of order two (that is, self-inverse).

The Walsh system is an orthonormal basis of the Hilbert space ${\displaystyle L^{2}[0,1]}$. Orthonormality means

${\displaystyle \int _{0}^{1}W_{k}(x)W_{l}(x)dx=\delta _{kl}}$,

and being a basis means that if, for every ${\displaystyle f\in L^{2}[0,1]}$, we set ${\displaystyle f_{k}=\int _{0}^{1}f(x)W_{k}(x)dx}$ then

${\displaystyle \int _{0}^{1}(f(x)-\sum _{k=0}^{N}f_{k}W_{k}(x))^{2}dx\;\ {\xrightarrow[{N\rightarrow \infty }]{}}\;\ 0}$

It turns out that for every ${\displaystyle f\in L^{2}[0,1]}$, the series ${\displaystyle \sum _{k=0}^{\infty }f_{k}W_{k}(x)}$ converges to ${\displaystyle f(x)}$ for almost every ${\displaystyle x\in [0,1]}$.

The Walsh system (in Walsh-Paley numeration) forms a Schauder basis in ${\displaystyle L^{p}[0,1]}$,   ${\displaystyle 1<p<\infty }$. Note that, unlike the Haar system, and like the trigonometric system, this basis is not unconditional, nor is the system a Schauder basis in ${\displaystyle L^{1}[0,1]}$.

Let ${\displaystyle \mathbb {D} =\prod _{n=1}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ be the compact Cantor group endowed with Haar measure and let ${\displaystyle {\hat {\mathbb {D} }}=\coprod _{n=1}^{\infty }\mathbb {Z} /2\mathbb {Z} }$ be its discrete group of characters. Elements of ${\displaystyle {\hat {\mathbb {D} }}}$ are readily identified with Walsh functions. Of course, the characters are defined on ${\displaystyle \mathbb {D} }$ while Walsh functions are defined on the unit interval, but since there exists a modulo zero isomorphism between these measure spaces, measurable functions on them are identified via isometry.

Then basic representation theory suggests the following broad generalization of the concept of Walsh system.

For an arbitrary Banach space ${\displaystyle (X,||\cdot ||)}$ let ${\displaystyle \{R_{t}\}_{t\in \mathbb {D} }\subset \operatorname {Aut} X}$ be a strongly continuous, uniformly bounded faithful action of ${\displaystyle \mathbb {D} }$ on X. For every ${\displaystyle \gamma \in {\hat {\mathbb {D} }}}$, consider its eigenspace ${\displaystyle X_{\gamma }=\{x\in X:R_{t}x=\gamma (t)x\}}$. Then X is the closed linear span of the eigenspaces: ${\displaystyle X={\overline {\operatorname {Span} }}(X_{\gamma },\gamma \in {\hat {\mathbb {D} }})}$. Assume that every eigenspace is one-dimensional and pick an element ${\displaystyle w_{\gamma }\in X_{\gamma }}$ such that ${\displaystyle \|w_{\gamma }\|=1}$. Then the system ${\displaystyle \{w_{\gamma }\}_{\gamma \in {\hat {\mathbb {D} }}}}$, or the same system in the Walsh-Paley numeration of the characters ${\displaystyle \{w_{k}\}_{k\in {\mathbb {N} }_{0}}}$ is called generalized Walsh system associated with action ${\displaystyle \{R_{t}\}_{t\in \mathbb {D} }}$. Classical Walsh system becomes a special case, namely, for

${\displaystyle R_{t}:x=\sum _{j=1}^{\infty }x_{j}2^{-j}\mapsto \sum _{j=1}^{\infty }(x_{j}\oplus t_{j})2^{-j}}$

where ${\displaystyle \oplus }$ is addition modulo 2.

In the early 1990s, Serge Ferleger and Fyodor Sukochev showed that in a broad class of Banach spaces (so called UMD spaces^[4]) generalized Walsh systems have many properties similar to the classical one: they form a Schauder basis^[5] and a uniform finite-dimensional decomposition^[6] in the space, have property of random unconditional convergence.^[7] One important example of generalized Walsh system is Fermion Walsh system in non-commutative L^p spaces associated with hyperfinite type II factor.

The Fermion Walsh system is a non-commutative, or "quantum" analog of the classical Walsh system. Unlike the latter, it consists of operators, not functions. Nevertheless, both systems share many important properties, e.g., both form an orthonormal basis in corresponding Hilbert space, or Schauder basis in corresponding symmetric spaces. Elements of the Fermion Walsh system are called Walsh operators.

The term Fermion in the name of the system is explained by the fact that the enveloping operator space, the so-called hyperfinite type II factor ${\displaystyle {\mathcal {R}}}$, may be viewed as the space of observables of the system of countably infinite number of distinct spin ${\displaystyle 1/2}$ fermions. Each Rademacher operator acts on one particular fermion coordinate only, and there it is a Pauli matrix. It may be identified with the observable measuring spin component of that fermion along one of the axes ${\displaystyle \{x,y,z\}}$ in spin space. Thus, a Walsh operator measures the spin of a subset of fermions, each along its own axis.

Fix a sequence ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},...)}$ of integers with ${\displaystyle \alpha _{k}\geq 2,k=1,2,\dots }$ and let ${\displaystyle \mathbb {G} =\mathbb {G} _{\alpha }=\prod _{n=1}^{\infty }\mathbb {Z} /\alpha _{k}\mathbb {Z} }$ endowed with the product topology and the normalized Haar measure. Define ${\displaystyle A_{0}=1}$ and ${\displaystyle A_{k}=\alpha _{1}\alpha _{2}\dots \alpha _{k-1}}$. Each ${\displaystyle x\in \mathbb {G} }$ can be associated with the real number

${\displaystyle \left|x\right|=\sum _{k=1}^{\infty }{\frac {x_{k}}{A_{k}}}\in \left[0,1\right].}$

This correspondence is a module zero isomorphism between ${\displaystyle \mathbb {G} }$ and the unit interval. It also defines a norm which generates the topology of ${\displaystyle \mathbb {G} }$. For ${\displaystyle k=1,2,\dots }$, let ${\displaystyle \rho _{k}:\mathbb {G} \to \mathbb {C} }$ where

${\displaystyle \rho _{k}(x)=\exp \left(i{\frac {2\pi x_{k}}{\alpha _{k}}}\right)=\cos \left({\frac {2\pi x_{k}}{\alpha _{k}}}\right)+i\sin \left({\frac {2\pi x_{k}}{\alpha _{k}}}\right).}$

The set ${\displaystyle \{\rho _{k}\}}$ is called generalized Rademacher system. The Vilenkin system is the group ${\displaystyle {\hat {\mathbb {G} }}=\coprod _{n=1}^{\infty }\mathbb {Z} /\alpha _{k}\mathbb {Z} }$ of (complex-valued) characters of ${\displaystyle \mathbb {G} }$, which are all finite products of ${\displaystyle \{\rho _{k}\}}$. For each non-negative integer ${\displaystyle n}$ there is a unique sequence ${\displaystyle n_{0},n_{1},\dots }$ such that ${\displaystyle 0\leq n_{k}<\alpha _{k+1},k=0,1,2,\dots }$ and

${\displaystyle n=\sum _{k=0}^{\infty }n_{k}A_{k}.}$

Then ${\displaystyle {\hat {\mathbb {G} }}={\chi _{n}|n=0,1,\dots }}$ where

${\displaystyle \chi _{n}=\sum _{k=0}^{\infty }\rho _{k+1}^{n_{k}}.}$

In particular, if ${\displaystyle \alpha _{k}=2,k=1,2...}$, then ${\displaystyle \mathbb {G} }$ is the Cantor group and ${\displaystyle {\hat {\mathbb {G} }}=\left\{\chi _{n}|n=0,1,\dots \right\}}$ is the (real-valued) Walsh-Paley system.

The Vilenkin system is a complete orthonormal system on ${\displaystyle \mathbb {G} }$ and forms a Schauder basis in ${\displaystyle L^{p}(\mathbb {G} ,\mathbb {C} )}$,  ${\displaystyle 1<p<\infty }$.^[8]

Nonlinear phase extensions of discrete Walsh-Hadamard transform were developed. It was shown that the nonlinear phase basis functions with improved cross-correlation properties significantly outperform the traditional Walsh codes in code division multiple access (CDMA) communications.^[9]

Applications of the Walsh functions can be found wherever digit representations are used, including speech recognition, medical and biological image processing, and digital holography.

For example, the fast Walsh–Hadamard transform (FWHT) may be used in the analysis of digital quasi-Monte Carlo methods. In radio astronomy, Walsh functions can help reduce the effects of electrical crosstalk between antenna signals. They are also used in passive LCD panels as X and Y binary driving waveforms where the autocorrelation between X and Y can be made minimal for pixels that are off.

• Discrete Fourier transform
• Dyadic derivative
• Fast Fourier transform
• Harmonic analysis
• Orthogonal functions
• Walsh matrix
• Parity function