The Walsh functions consist of trains of square pulses (with the allowed states being 
and 1) such that transitions may only
occur at fixed intervals of a unit time step, the initial state is always 
, and the functions satisfy certain other orthogonality relations.
In particular, the 
Walsh functions of order 
are given by the rows of the Hadamard matrix 
when arranged in so-called "sequency" order (Thompson et al. 1986, p. 204;
Wolfram 2002, p. 1073).
There are 
Walsh functions of length 
, illustrated above for 
, 2, and 3.
Walsh functions were used by electrical engineers such as Frank Fowle in the 1890s to find transpositions of wires that minimized crosstalk and were introduced into mathematics by Walsh (1923; Wolfram 2002, p. 1073).
Amazingly, concatenating the Walsh functions ![W(n-1,[2^n/3])](/images/equations/WalshFunction/Inline9.svg)
(while simultaneously replacing 
s by 0s), where ![[x]](/images/equations/WalshFunction/Inline11.svg)
is the ceiling function,
gives the Thue-Morse sequence (Wolfram 2002,
p. 1073).
The values of ![[2^n/3]](/images/equations/WalshFunction/Inline12.svg)
are given explicitly by 
,
and the first few are 1, 2, 3, 6, 11, 22, 43, 86, 171, ... (OEIS A005578).
Walsh functions can be ordered in a number of ways, illustrated above (Wolfram 2002, p. 1073).
The sequency 
of a Walsh function is defined as half the number of zero
crossings in one cycle of the time base. In sequency order (left figure), each row
has one more color change than the preceding row. In natural (or Hadamard) order
(middle figure), the Walsh functions display a nested structure. Dyadic (or Paley)
order (right figure) is related to Gray code reordering
of the rows (Wolfram 2002, p. 1073).
Walsh functions with nonidentical sequencies are orthogonal, as are the functions 
and 
. The product of two Walsh functions is also a Walsh
function.
Harmuth (1969) designates the even Walsh functions 
and the odd
Walsh functions 
,
 |  |  |
(1)
|
 |  |  |
(2)
|
where 
is the sequency.
Taking the matrix product of a set of two-dimensional data (represented as a square matrix with size a power of two) with a corresponding array of Walsh functions is known as the Walsh transform (Wolfram 2002, p. 1073). Walsh transforms can be performed particular efficiently, resulting in the so-called fast Walsh transform.
