Walsh function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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, orthonomal 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 former being Walsh series, and the latter - the theory of Hadamard transform.

Walsh functions and corresponding series and transforms find various applications in physics and engineering, in particular, 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[edit]

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 kj and no trailing xj 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 Rademacher function rm. Thus, Rademacher system is a subsystem of 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[edit]

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 orthonomal 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] .

Walsh system (in Walsh-Paley numeration) forms a Schauder basis in  L^p[0,1] ,    1< p < \infty . Note that, unlike 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[edit]

Walsh-Ferleger systems[edit]

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 [1]) generalized Walsh systems have many properties similar to the classical one: they form a Schauder basis [2] and a uniform finite dimensional decomposition [3] in the space, have property of random unconditional convergence.[4] One important example of generalized Walsh system is Fermion Walsh system in non-commutative Lp spaces associated with hyperfinite type II factor.

Fermion Walsh system[edit]

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


Vilenkin system[edit]

Applications[edit]

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.[5] Also exist eight Walsh-like bases of orthonormal binary functions,[6] 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 Walsh functions basis) as a finite sum of the binary functions, being weighted with the proper coefficients.[7]

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[edit]

External links[edit]

References[edit]