Editing Walsh function

{{Short description|Concept in mathematics}}
[[File:Natural and sequency ordered Walsh 16.svg|thumb|480px|Natural ordered [[Hadamard matrix]] (middle matrix) of order 16 that is sequency ordered to output a  [[Walsh matrix]] (right matrix).<br>Both contain the 16 Walsh functions of order 16 as rows (and columns).<br>In the right matrix, the number of sign changes per row is consecutive.]]

In [[mathematics]], more specifically in [[harmonic analysis]], '''Walsh functions''' form a [[Complete orthogonal system|complete orthogonal set]] of [[function (mathematics)|function]]s that can be used to represent any discrete function—just like [[trigonometric functions]] can be used to represent any [[continuous function]] in [[Fourier analysis]].<ref>{{harvnb|Walsh|1923}}.</ref>  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 function|constant]]. They take the values −1 and +1 only, on sub-intervals defined by [[dyadic fraction]]s.

The system of Walsh functions is known as the '''Walsh system'''. It is an extension of the [[Rademacher system]] of orthogonal functions.<ref>{{harvnb|Fine|1949}}.</ref>

Walsh functions, the Walsh system, the Walsh series,<ref>{{harvnb|Schipp|Wade|Simon|1990}}.</ref> 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 [[Digital signal processing|analyzing digital signals]].

Historically, various [[numeration]]s of Walsh functions have been used; none of them is particularly superior to another. This articles uses the ''Walsh–Paley numeration''.

==Definition==

We define the sequence of Walsh functions <math>W_k : [0,1] \rightarrow \{-1,1\}</math>, <math>k\in\mathbb{N}</math> as follows.

For any [[natural number]] ''k'', and [[real number]] <math>x \in [0,1]</math>, let

:<math>k_j</math> be the ''j''th bit in the [[binary representation]] of ''k'', starting with <math>k_0</math> as the least significant bit, and

:<math>x_j</math> be the ''j''th bit in the fractional binary representation of <math>x</math>, starting with <math>x_1</math> as the most significant fractional bit.

Then, by definition

:<math>W_k(x) = (-1)^{\sum_{j=0}^\infty k_jx_{j+1}}</math>

In particular, <math>W_0(x) = 1</math> everywhere on the interval, since all bits of ''k'' are zero.

Notice that <math>W_{2^m}</math> is precisely the [[Rademacher system|Rademacher function]] ''r<sub>m</sub>''.
Thus, the Rademacher system is a subsystem of the Walsh system. Moreover, every Walsh function is a product of Rademacher functions:

:<math>W_k(x) = \prod_{j=0}^\infty r_j(x)^{k_j}</math>

==Comparison between Walsh functions and trigonometric functions==

Walsh functions and trigonometric functions are both systems that form a complete, [[orthonormality|orthonormal]] set of functions, an [[orthonormal basis]] in the [[Hilbert space]] <math>L^2[0,1]</math> of the [[square-integrable function]]s on the unit interval. Both are systems of [[bounded function]]s, unlike, say, the [[Haar wavelet|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.

==Properties==

The Walsh system <math>\{W_k\}, k \in \mathbb{N}_0</math> is an [[abelian group|abelian]] multiplicative [[discrete group]] [[isomorphic]] to <math>\coprod_{n=0}^\infty \mathbb{Z}/2\mathbb{Z}</math>, the [[Pontryagin duality|Pontryagin dual]] of the [[Cantor cube|Cantor group]] <math>\prod_{n=0}^\infty \mathbb{Z}/2\mathbb{Z}</math>. Its [[identity element|identity]] is <math>W_0</math>, and every element is of [[order (group theory)|order]] two (that is, self-inverse).

The Walsh system is an orthonormal basis of the Hilbert space <math>L^2[0,1]</math>. Orthonormality means

:<math>\int_0^1 W_k(x)W_l(x) dx = \delta_{kl}</math>,

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

:<math>\int_0^1 ( f(x) - \sum_{k=0}^N f_k W_k(x) )^2 dx \;\ \xrightarrow[N\rightarrow\infty]{}\;\ 0</math>

It turns out that for every <math>f \in L^2[0,1]</math>, the [[series (mathematics)|series]] <math>\sum_{k=0}^\infty f_k W_k(x)</math> [[convergent series|converges]] to <math>f(x)</math> for almost every <math>x \in [0,1]</math>.

The Walsh system (in Walsh-Paley numeration) forms a [[Schauder basis]] in <math>L^p[0,1]</math>, &nbsp; <math>1 < p < \infty</math>. Note that, unlike the [[Haar wavelet|Haar system]], and like the trigonometric system, this basis is not [[Schauder basis|unconditional]], nor is the system a Schauder basis in <math>L^1[0,1]</math>.

==Generalizations==

===Walsh-Ferleger systems===

Let <math>\mathbb{D} = \prod_{n=1}^\infty \mathbb{Z}/2\mathbb{Z}</math> be the [[compact group|compact]] [[Cantor cube|Cantor group]] endowed with [[Haar measure]] and let <math> \hat {\mathbb D} = \coprod_{n=1}^\infty \mathbb Z / 2\mathbb Z </math> be its discrete group of [[Character (mathematics)|characters]]. Elements of <math> \hat {\mathbb D} </math> are readily identified with Walsh functions. Of course, the characters are defined on <math> \mathbb D </math> while Walsh functions are defined on the unit interval, but since there exists a [[Standard probability space|modulo zero isomorphism]] between these [[measure space]]s, 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]] <math>(X, ||\cdot||)</math> let <math>\{ R_t \}_{t \in \mathbb D} \subset \operatorname{Aut}X</math> be a [[Strong operator topology|strongly continuous]], uniformly bounded [[Group action#Notable properties of actions|faithful]] [[group action|action]] of <math>\mathbb D</math> on ''X''. For every <math>\gamma \in \hat{\mathbb D}</math>, consider its [[eigenspace]] <math> X_\gamma = \{x \in X : R_t x = \gamma(t)x \}</math>. Then  ''X'' is the closed linear span of the eigenspaces: <math>X = \overline{\operatorname{Span}}(X_\gamma, \gamma \in \hat {\mathbb D})</math>. Assume that every eigenspace is one-[[dimension (vector space)|dimensional]] and pick an element <math>w_\gamma \in X_\gamma</math> such that <math>\|w_\gamma\| = 1</math>. Then the system <math>\{w_\gamma\}_{\gamma \in \hat {\mathbb D}}</math>, or the same system in the Walsh-Paley numeration of the characters <math>\{w_k\}_{k \in {\mathbb N}_0}</math> is called generalized Walsh system associated with action <math>\{ R_t \}_{t \in \mathbb D}</math>. Classical Walsh system becomes a special case, namely, for

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

where <math>\oplus</math> is addition [[modular arithmetic|modulo]] 2.

In the early 1990s, Serge Ferleger and Fyodor Sukochev showed that in a broad class of Banach spaces (so called ''UMD'' spaces<ref>{{harvnb|Pisier|2011}}.</ref>) generalized Walsh systems have many properties similar to the classical one: they form a Schauder basis<ref>{{harvnb|Sukochev|Ferleger|1995}}.</ref> and a uniform finite-dimensional decomposition<ref>{{harvnb|Ferleger|Sukochev|1996}}.</ref> in the space, have property of random unconditional convergence.<ref>{{harvnb|Ferleger|1998}}.</ref>
One important example of generalized Walsh system is Fermion Walsh system in non-commutative ''L''<sup>p</sup> spaces associated with [[hyperfinite type II factor]].

===Fermion Walsh system===

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]] <math> \mathcal R</math>, may be viewed as the space of ''observables'' of the system of countably infinite number of distinct [[Spin (physics)|spin]] <math>1/2</math> [[fermion]]s. Each [[Rademacher function|Rademacher]] operator acts on one particular fermion coordinate only, and there it is a [[Pauli matrices|Pauli matrix]]. It may be identified with the observable measuring spin component of that fermion along one of the axes <math> \{x,y,z\}</math> in spin space. Thus, a Walsh operator measures the spin of a subset of fermions, each along its own axis.

===Vilenkin system===

Fix a sequence <math>\alpha = (\alpha_1,\alpha_2,...)</math> of [[integer]]s with <math>\alpha_k \geq 2, k=1,2,\dots</math> and let <math>\mathbb{G} = \mathbb{G}_\alpha = \prod_{n=1}^\infty \mathbb{Z}/\alpha_k\mathbb{Z}</math> endowed with the [[product topology]] and the normalized Haar measure. Define <math>A_0 = 1</math> and <math>A_k = \alpha_1 \alpha_2 \dots \alpha_{k-1}</math>. Each <math>x \in \mathbb G</math> can be associated with the real number

:<math> \left|x\right| = \sum_{k=1}^{\infty} \frac{x_k}{A_{k}} \in \left[0,1\right].</math>

This correspondence is a module zero isomorphism between <math>\mathbb G</math> and the unit interval. It also defines a norm which generates the [[topological space|topology]] of <math>\mathbb G</math>. For <math>k=1,2,\dots</math>, let <math>\rho_k: \mathbb{G}\to\mathbb{C}</math> where

:<math>\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).</math>

The set <math>\{\rho_k\}</math> is called ''generalized Rademacher system''. The Vilenkin system is the [[group (mathematics)|group]] <math>\hat{\mathbb G} = \coprod_{n=1}^\infty \mathbb{Z}/\alpha_k\mathbb{Z}</math> of ([[complex number|complex]]-valued) characters of <math>\mathbb G</math>, which are all finite products of <math>\{\rho_k\}</math>. For each non-negative integer <math>n</math> there is a unique sequence <math>n_0, n_1, \dots</math> such that <math>0 \leq n_k < \alpha_{k+1}, k=0,1,2,\dots</math> and

:<math>n = \sum_{k=0}^{\infty} n_k A_k.</math>

Then <math>\hat{\mathbb G} = {\chi_n | n=0,1,\dots}</math> where

:<math>\chi_n = \sum_{k=0}^{\infty} \rho_{k+1}^{n_k}.</math>

In particular, if <math>\alpha_k = 2, k=1,2...</math>, then <math>\mathbb G</math> is the Cantor group and <math>\hat{\mathbb G} = \left\{\chi_n | n=0,1,\dots\right\}</math> is the (real-valued) Walsh-Paley system.

The Vilenkin system is a complete orthonormal system on <math> \mathbb G </math> and forms a [[Schauder basis]] in <math>L^p(\mathbb{G}, \mathbb{C})</math>,&nbsp; <math>1 < p < \infty</math>.<ref>{{harvnb|Young|1976}}</ref>

===Nonlinear Phase Extensions===
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.<ref>A.N. Akansu and R. Poluri,  [http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf "Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications,"] IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3800–3806, July 2007.</ref>

==Applications==

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 method]]s. 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 [[pixel]]s that are off.

==See also==

*[[Discrete Fourier transform]]
*[[Dyadic derivative]]
*[[Fast Fourier transform]]
*[[Harmonic analysis]]
*[[Orthogonal functions]]
*[[Walsh matrix]]
*[[Parity function]]

==Notes==

{{Reflist}}

==References==

*{{Cite tech report
 | first = Sergei V.
 | last = Ferleger
 | title = RUC-Systems In Non-Commutative Symmetric Spaces
 | number =  MP-ARC-98-188
 | url = http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=98-184
 | date = March 1998
 }}
*{{Cite journal
 | first1 = Sergei V.
 | last1 = Ferleger
 | first2 = Fyodor A.
 | last2 = Sukochev
 | title = On the contractibility to a point of the linear groups of reflexive non-commutative Lp-spaces
 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]
 | volume = 119
 | issue = 3
 | pages = 545–560
 | date = March 1996
 | doi=10.1017/s0305004100074405
| bibcode = 1996MPCPS.119..545F
 | s2cid = 119786894
 }}
*{{Cite journal
 | first = N.J.
 | last = Fine
 | title = On the Walsh functions
 | journal = Trans. Amer. Math. Soc.
 | volume = 65
 | issue = 3
 | year = 1949
 | pages = 372–414
 | doi=10.1090/s0002-9947-1949-0032833-2
| doi-access = free
 }}
*{{Cite book
 | first = Gilles
 | last = Pisier
 | title = Martingales in Banach Spaces (in connection with Type and Cotype). Course IHP
 | year = 2011
 | url = https://webusers.imj-prg.fr/~gilles.pisier/ihp-pisier.pdf
 }}
*{{Cite book
 | first1 = Ferenc
 | last1 = Schipp
 | first2 = W.R.
 | last2 = Wade
 | first3 = P.
 | last3 = Simon
 | title = Walsh series. An introduction to dyadic harmonic analysis
 | publisher = Akadémiai Kiadó
 | year = 1990
 }}
*{{Cite journal
 | first1 = Fyodor A.
 | last1 = Sukochev
 | first2 = Sergei V.
 | last2 = Ferleger
 | title = Harmonic analysis in (UMD)-spaces: Applications to the theory of bases
 | journal = Mathematical Notes
 | date = December 1995
 | volume = 58
 | issue = 6
 | pages = 1315–1326
 | doi=10.1007/bf02304891
| s2cid = 121256402
 }}
*{{Cite journal
 | first = J.L.
 | last = Walsh
 | title = A closed set of normal orthogonal functions
 | journal = [[American Journal of Mathematics|Amer. J. Math.]]
 | volume = 45
 | issue = 1
 | year = 1923
 | pages = 5–24
 | doi=10.2307/2387224
| jstor = 2387224
 | s2cid = 6131655
 }}
*{{Cite journal
 | first = W.-S.
 | last = Young
 | title = Mean convergence of generalized Walsh-Fourier series
 | journal = [[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]]
 | volume = 218
 | year = 1976
 | pages = 311–320
 | doi=10.1090/s0002-9947-1976-0394022-8
 | jstor = 1997441
 | s2cid = 53755959
 | doi-access = free
 }}

==External links==
*{{Cite web
 | title = Walsh functions 
 | work = MathWorld
 | url = http://mathworld.wolfram.com/WalshFunction.html
}}

*{{Cite encyclopedia
 | title = Walsh functions
 | encyclopedia = Encyclopedia of Mathematics
 | url = https://www.encyclopediaofmath.org/index.php/Walsh_functions
}}

*{{Cite encyclopedia
 | title = Walsh system
 | encyclopedia = Encyclopedia of Mathematics
 | url = https://www.encyclopediaofmath.org/index.php/Walsh_system
}}

*{{Cite web
 | title = Walsh functions
 | work = Stanford Exploration Project
 | url = http://sepwww.stanford.edu/public/docs/sep70/carlos1/paper_html/node5.html
}}

{{Authority control}}

[[Category:Special functions]]