Walsh system

of functions $ \{ W _ {n} \} $ on the interval $ [ 0, 1] $

The functions $ W _ {0} ( x) \equiv 1 $ and $ W _ {n} ( x) = r _ {\nu _ {1} } ( x) \dots r _ {\nu _ {m} } ( x) $ for $ n \geq 1 $, where $ r _ {k} ( x) = \mathop{\rm sign} \sin 2 ^ {k + 1 } \pi x $, $ k = 0, 1 \dots $ are the Rademacher functions (cf. Rademacher system) and $ n = 2 ^ {\nu _ {1} } + {} \dots + 2 ^ {\nu _ {m} } $, $ \nu _ {1} > \dots > \nu _ {m} $, is the binary representation of the number $ n \geq 1 $. This system was defined and studied by J.L. Walsh [1], but already in 1900 J.A. Barrett studied functions of this system in questions connected with the distribution of electrons on open conducting curves. In connection with this theory another definition of Walsh functions is preferred. Namely, if

$$ W _ {0} ^ {*} ( x) = \ \left \{ then the functions $ W _ {n} ^ {*} ( x) $ are defined by the following recurrence formulas: $$ W _ {2j + p } ^ {*} ( x) = \ W _ {j} ^ {*} ( 2x) + (- 1) ^ {j + p } W _ {j} ^ {*} ( 2x - 1), $$ $$ p = 0, 1; \ j = 0, 1 , . . . . $$

The systems $ \{ W _ {n} \} $ and $ \{ W _ {n} ^ {*} \} $ differ only in their ordering in the ranges $ 2 ^ {m} \leq n \leq 2 ^ {m + 1 } - 1 $, $ m = 1, 2 , . . . $. For example, $ W _ {2 ^ {m} } ^ {*} = W _ {3 \cdot 2 ^ {m - 1 } } $, $ W _ {2 ^ {m - 1 } - 1 } ^ {*} = W _ {2 ^ {m} } $, $ W _ {2 ^ {m + 1 } - 2 } ^ {*} = W _ {2 ^ {m} + 1 } $, etc. The index $ k $ of the function $ W _ {k} ^ {*} $ corresponds to the number of changes of sign of this function in the interval $ ( 0, 1) $, i.e. it is the analogue to doubling the frequency of a sinusoidal function. The Walsh system is a complete orthonormal system on the interval $ [ 0, 1] $ and it may be considered as a natural completion of the Rademacher system.

The Walsh system forms a commutative multiplicative group, with the function $ W _ {0} $ as unit element, while each $ W _ {k} $ is its own inverse.

References

[1]	J.L. Walsh, "A closed set of normal orthogonal functions" Amer. J. Math. , 45 (1923) pp. 5–24
[2]	F.F. Fowle, Trans. AJEE , 23 (1905) pp. 659–687
[3]	N.J. Fine, "On the Walsh functions" Trans. Amer. Math. Soc. , 65 (1949) pp. 372–414
[4]	S. Kaczmarz, H. Steinhaus, "Theorie der Orthogonalreihen" , Chelsea, reprint (1951)
[5]	H.F. Harmut, "Transmission of information by orthogonal functions" , Springer (1972)

References

[a1]	B. Golubov, A. Efimov, V. Skvortsov, "Walsh series and transforms" , Kluwer (1987) (Translated from Russian)