Walsh transforms
The basic forms shown in the main text are 2D Walsh functions—represented as ±1 matrices. Each collection of such functions can be obtained from lists of vectors representing 1D Walsh functions by using Outer[Outer[Times, ##] &, b, b, 1, 1], or equivalently Map[Transpose, Map[# b &, b, {2}]].
The pictures below show how 1D arrays of data values can be built up by adding together 1D Walsh functions. At each step the Walsh function used is given underneath the array of values obtained so far.
The components of the vectors for 1D Walsh functions can be ordered in many ways. The pictures below show the complete matrices of basis vectors obtained with three common orderings.
The matrices for size n = 2s can be obtained from
Nest[Apply[Join, f[{Map[Flatten[Map[{#, #} &, #]] &, #], Map[Flatten[Map[{#, -#} &, #]] &, g[#]]}]] &, {{1}},s]
with (a) f = Identity, g = Reverse, (b) f = Transpose, g = Identity, and (c) f = g = Identity. (a) is used in the main text. Known as sequency order, it has the property that each row involves one more change of color than the previous row. (b) is known as natural or Hadamard order. It exhibits a nested structure, and can be obtained as in the pictures below from the evolution of a 2D substitution system, or equivalently from a Kronecker product as in
Nest[Flatten2D[Map[# {{1, 1}, {1, -1}} &, #, {2}]] &, {{1}}, s]
with
Flatten2D[a_] := Apply[Join, Apply[Join, Map[Transpose,a], {2}]]
(c) is known as dyadic or Paley order. It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905)
BitReverseOrder[a_] := With[{n = Length[a]}, a〚Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1〛]
It is also given by
Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0]
where (b) is obtained simply by dropping the Reverse.
Walsh functions can correspond to nested sequences. The function at position 2/3 (1 + 4^-(Floor[s/2] + 1/2)) 2s in basis (a), for example, is exactly the Thue–Morse sequence (with 0 replaced by -1) from page 83.
Given the matrix m of basis vectors, the Walsh transform is simply data . m. Direct evaluation of this for length n takes n2 steps. However, the nested structure of m in natural order allows evaluation in only about n Log[n] steps using
Nest[Flatten[Transpose[Partition[#, 2] . {{1, 1}, {1, -1}}]] &, data, Log[2, Length[data]]]
This procedure is similar to the fast Fourier transform discussed below. Transforms of 2D data are equivalent to 1D transforms of flattened data.
Walsh functions were used by electrical engineers such as Frank Fowle in the 1890s to find transpositions of wires that minimized crosstalk; they were introduced into mathematics by Joseph Walsh in 1923. Raymond Paley introduced the dyadic basis in 1932. Mathematical connections with harmonic analysis of discrete groups were investigated from the late 1940s. In the 1960s, Walsh transforms became fairly widespread in discrete signal and image processing.