Walsh function

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