In mathematics, more specifically in harmonic analysis, Walsh functions form a complete orthogonal set of functions that can be used to represent any discrete function—just like trigonometric functions can be used to represent any continuous function in Fourier analysis. They can thus be viewed as a discrete, digital counterpart of the continuous, analog system of trigonometric functions on the unit interval. But unlike the sine and cosine functions, which are continuous, Walsh functions are piecewise constant. They take the values −1 and +1 only, on sub-intervals defined by dyadic fractions.
Walsh functions, the Walsh system, the Walsh series, and the fast Walsh–Hadamard transform are all named after the American mathematician Joseph L. Walsh. They find various applications in physics and engineering when analyzing digital signals.
Historically, various numerations of Walsh functions have been used; none of them is particularly superior to another. In this article, we use the Walsh–Paley numeration.
We define the sequence of Walsh functions , as follows.
For any natural number k, and real number , let
- be the jth bit in the binary representation of k, starting with as the least significant bit, and
- be the jth bit in the binary representation[clarification needed], starting with as the most significant fractional bit.
Then, by definition
In particular, everywhere on the interval, since all bits of k are zero.
Notice that is precisely the Rademacher function rm. Thus, the Rademacher system is a subsystem of the Walsh system. Moreover, every Walsh function is a product of Rademacher functions:
Comparison between Walsh functions and trigonometric functionsEdit
Walsh functions and trigonometric functions are both systems that form a complete, orthonormal set of functions, an orthonormal basis in Hilbert space 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 is an orthonormal basis of Hilbert space . Orthonormality means
and being a basis means that if, for every , we set then
It turns out that for every , the series converge to for almost every .
The Walsh system (in Walsh-Paley numeration) forms a Schauder basis in , . Note that, unlike the Haar system, and like the trigonometric system, this basis is not unconditional, nor is the system a Schauder basis in .
Let be the compact Cantor group endowed with Haar measure and let be its discrete group of characters. Elements of are readily identified with Walsh functions. Of course, the characters are defined on 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 let be a strongly continuous, uniformly bounded faithful action of on X. For every , consider its eigenspace . Then X is the closed linear span of the eigenspaces: . Assume that every eigenspace is one-dimensional and pick an element such that . Then the system , or the same system in the Walsh-Paley numeration of the characters is called generalized Walsh system associated with action . Classical Walsh system becomes a special case, namely, for
where 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 ) 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 Lp spaces associated with hyperfinite type II factor.
Fermion Walsh systemEdit
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 , may be viewed as the space of observables of the system of countably infinite number of distinct spin 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 in spin space. Thus, a Walsh operator measures the spin of a subset of fermions, each along its own axis.
This section is empty. You can help by adding to it. (August 2014)
Romanuke showed that Walsh functions can be generalized to binary surfaces in a particular case of function of two variables. 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 (in the case of the function of two variables) also. It was proved that piecewise-constant functions can be represented within each of nine bases (including the Walsh functions basis) as finite sums of binary functions, when weighted with proper coefficients.
Nonlinear Phase ExtensionsEdit
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.
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.
- Walsh 1923.
- Fine 1949.
- Schipp, Wade & Simon 1990.
- Pisier 2011.
- Sukochev & Ferleger 1995.
- Ferleger & Sukochev 1996.
- Ferleger 1998.
- Romanuke 2010a.
- Romanuke 2010b.
- Romanuke 2010c.
- A.N. Akansu and R. Poluri, "Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications," IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3800–3806, July 2007.
- Ferleger, Sergei V. (March 1998). RUC-Systems In Non-Commutative Symmetric Spaces (Technical report). MP-ARC-98-188.
- Ferleger, Sergei V.; Sukochev, Fyodor A. (March 1996). "On the contractibility to a point of the linear groups of reflexive non-commutative Lp-spaces". Mathematical Proceedings of the Cambridge Philosophical Society. 119 (3): 545–560. Bibcode:1996MPCPS.119..545F. doi:10.1017/s0305004100074405.
- Fine, N.J. (1949). "On the Walsh functions". Trans. Amer. Math. Soc. 65 (3): 372–414. doi:10.1090/s0002-9947-1949-0032833-2.
- Pisier, Gilles (2011). Martingales in Banach Spaces (in connection with Type and Cotype). Course IHP (PDF).
- Romanuke, V. V. (2010a). "On the Point of Generalizing the Walsh Functions to Surfaces".
- Romanuke, V. V. (2010b). "Generalization of the Eight Known Orthonormal Bases of Binary Functions to Surfaces".
- Romanuke, V. V. (2010c). "Equidistantly Discrete on the Argument Axis Functions and their Representation in the Orthonormal Bases Series".
- Schipp, Ferenc; Wade, W.R.; Simon, P. (1990). Walsh series. An introduction to dyadic harmonic analysis. Akadémiai Kiadó.
- Sukochev, Fyodor A.; Ferleger, Sergei V. (December 1995). "Harmonic analysis in (UMD)-spaces: Applications to the theory of bases". Mathematical Notes. 58 (6): 1315–1326. doi:10.1007/bf02304891. S2CID 121256402.
- "Walsh functions". MathWorld.
- "Walsh functions". Encyclopedia of Mathematics.
- "Walsh system". Encyclopedia of Mathematics.
- "Walsh functions". Stanford Exploration Project.