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.
The system of Walsh functions is known as the Walsh system. It is an extension of the Rademacher system of orthogonal functions.
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. This articles uses the Walsh–Paley numeration.
Definition
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 fractional binary representation of , 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 functions
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.
Properties
The Walsh system is a commutative multiplicative discrete group isomorphic to , the Pontryagin dual of Cantor group . Its identity is , and every element is of order two (that is, self-inverse).
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 .
Generalizations
Walsh-Ferleger systems
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.