Walsh function

Natural ordered and sequency ordered Hadamard matrix of order 16.
Especially the former is usually called Walsh matrix.
Both contain the 16 Walsh functions of order 16 as rows (and columns).
In the right matrix the number of sign changes per row is consecutive.

The system of Walsh functions (or, simply, Walsh system) may be viewed as a discrete, digital counterpart of continuous, analog system of trigonometric functions on the unit interval. Unlike trigonometric functions, Walsh functions are only piecewise-continuous and, in fact, are piecewise constant. The functions take the values −1 and +1 only, on sub-intervals defined by dyadic fractions.

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

Both trigonometric and Walsh systems admit natural extension by periodicity from the unit interval to the real line $\mathbb R$. 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.

Walsh functions, series, and transforms find various applications in physics and engineering, especially in digital signal processing. They are used in speech recognition, in medical and biological image processing, in digital holography, and other areas.

Historically, various numerations of Walsh functions have been used, none of which could be considered particularly superior to another. In what follows, we will use so called Walsh–Paley numeration.

Definition

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

For any $k \in \mathbb N_0$, $x \in [0,1]$ let

$k = \sum_{j=0}^\infty k_j2^j, k_j \in \{0,1\}$,   $x = \sum_{j=1}^\infty x_j2^{-j}, x_j \in \{0,1\}$

such that there are only finitely many non-zero k_j and no trailing x_j all equal to 1, be the canonical binary representations of integer k and real number x, correspondingly. Then, by definition

$W_k(x) = (-1)^{\sum_{j=0}^\infty k_jx_{j+1}}$

In particular, $W_0(x)=1$ everywhere on the interval.

Notice that $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:

$W_k(x) = \prod_{j=0}^\infty r_j(x)^{k_j}$

Properties

The Walsh system $\{W_k\}, k \in \mathbb N_0$ is a commutative multiplicative discrete group isomorphic to $\coprod_{n=0}^\infty \mathbb Z / 2\mathbb Z$, the Pontryagin dual of Cantor group $\prod_{n=0}^\infty \mathbb Z / 2\mathbb Z$. Its identity is $W_0$, and every element is of order two (that is, self-inverse).

Walsh system is an orthonormal basis of Hilbert space $L^2[0,1]$. Orthonormality means

$\int_0^1 W_k(x)W_l(x)dx = \delta_{kl}$,

and being a basis means that if, for every $f \in L^2[0,1]$, we set $f_k = \int_0^1 f(x)W_k(x)dx$ then

$\int_0^1 ( f(x) - \sum_{k=0}^N f_k W_k(x) )^2dx \xrightarrow[N\rightarrow\infty]{} 0$

It turns out that for every $f \in L^2[0,1]$, the series $\sum_{k=0}^\infty f_k W_k(x)$ converge to $f(x)$ for almost every $x \in [0,1]$.

The Walsh system (in Walsh-Paley numeration) forms a Schauder basis in $L^p[0,1]$,   $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 $L^1[0,1]$.

Generalizations

Walsh-Ferleger systems

Let $\mathbb D = \prod_{n=1}^\infty \mathbb Z / 2\mathbb Z$ be the compact Cantor group endowed with Haar measure and let $\hat {\mathbb D} = \coprod_{n=1}^\infty \mathbb Z / 2\mathbb Z$ be its discrete group of characters. Elements of $\hat {\mathbb D}$ are readily identified with Walsh functions. Of course, the characters are defined on $\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 $(X,||\cdot||)$ let $\{ R_t \}_{t \in \mathbb D} \subset Aut(X)$ be a strongly continuous, uniformly bounded faithful action of $\mathbb D$ on X. For every $\gamma \in \hat {\mathbb D}$, consider its eigenspace $X_\gamma = \{x\in X : R_t x = \gamma(t)x \}$. Then X is the closed linear span of the eigenspaces: $X = \overline{\operatorname{Span}}(X_\gamma, \gamma \in \hat {\mathbb D})$. Assume that every eigenspace is one-dimensional and pick an element $w_\gamma \in X_\gamma$ such that $||w_\gamma||=1$. Then the system $\{w_\gamma\}_{\gamma \in \hat {\mathbb D}}$, or the same system in the Walsh-Paley numeration of the characters $\{w_k\}_{k \in {\mathbb N}_0}$ is called generalized Walsh system associated with action $\{ R_t \}_{t \in \mathbb D}$. Classical Walsh system becomes a special case, namely, for

$R_t: x=\sum_{j=1}^\infty x_j2^{-j} \mapsto \sum_{j=1}^\infty (x_j \oplus t_j)2^{-j}$

where $\oplus$ is addition modulo 2.

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

Fermion Walsh system

Fermion Walsh system is a non-commutative, or "quantum" analogue 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 will be called Walsh operators.

The word "Fermion" in the name of the system is explained by the fact that the enveloping operator space, so called hyperfinite type II factor $\mathcal R$ may be viewed as the space of observables of the system of countably infinite number of distinct spin $\frac{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 observable measuring spin component of that fermion along one of the axes $\{x,y,z\}$ in spin space. Thus, Walsh operator is measuring spin of a subset of the fermions, each along its own axis.

Precise construction is as follows.

Applications

Applications (in mathematics) can be found wherever digit representations are used, e.g. in the analysis of digital quasi-Monte Carlo methods. For those purposes there is the Walsh–Hadamard transform (WHT). Also there exists the fast Walsh–Hadamard transform (FWHT), being more effective than WHT. Besides, for a particular case of the function of two variables the Walsh functions are generalized to binary surfaces. There also exist eight Walsh-like bases of orthonormal binary functions, whose structure is nonregular (unlike the structure of Walsh functions). These eight bases are generalized to surfaces (to the cases of the function of two variables) also. It was proved that piecewise-constant functions are represented within each of nine bases (including the Walsh functions basis) as a finite sum of the binary functions, being weighted with the proper coefficients.

Walsh functions are used in Radio Astronomy to reduce the effects of electrical crosstalk between antenna signals. They are used in passive LCD panels as X and Y binary driving waveforms where the autocorelation between X and Y can be made minimal for pixels that are off.

See also

• Walsh matrix
• Exclusive or
• Joseph L. Walsh

External links

• Walsh functions at MathWorld
• Walsh functions at Stanford Exploration Project