A Walsh function is one of a family of mutually orthogonal step functions taking the values 
and 1 between their jumps. In the finite sampled convention
used here, the 
Walsh functions of order 
are the rows of the standard recursively constructed Hadamard
matrix 
arranged in sequency order, with each row starting at
(Thompson et al. 1986, p. 204;
Wolfram 2002, p. 1073).
Write 
for row 
,
numbered from 1 to 
,
where 
is a nonnegative integer. Each row has 
samples. The cases 
, 2, and 3 are illustrated above.
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).
For 
,
replacing 
by 0 in ![W(n-1,[2^n/3])](/images/equations/WalshFunction/Inline14.svg)
gives the first 
terms of the Thue-Morse sequence beginning
1, 0, 0, 1, ... (Wolfram 2002, p. 1073).
Here ![[x]](/images/equations/WalshFunction/Inline16.svg)
is the ceiling function. For 
, the values of ![[2^n/3]](/images/equations/WalshFunction/Inline18.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 
whenever both row indices are in range. The pointwise
product of two sampled Walsh rows of the same length is another Walsh row of that
length.
After centering the time interval at zero, Harmuth (1969) designates the even Walsh functions 
and the odd Walsh functions 
,
 |  |  |
(1)
|
 |  |  |
(2)
|
where 
is the sequency and the row indices are restricted to
1, ..., 
.
In particular, 
is the constant row.
Taking the matrix product of one-dimensional data represented as a row vector with a corresponding matrix of Walsh basis vectors gives the Walsh transform. Two-dimensional data can also be flattened to a vector and treated in this way (Wolfram 2002, p. 1073). Walsh transforms can be performed particularly efficiently, resulting in the so-called fast Walsh transform.
