Fast Walsh–Hadamard Transform

The Fast Walsh–Hadamard Transform (FWHT) is an efficient algorithm to compute the Walsh-Hadamard Transform (WHT). Unlike the Discrete Fourier Transform (DFT), which uses complex exponential basis functions, the WHT uses orthogonal real binary functions composed only of +1 and -1 values. This makes it computationally simpler, requiring only additions and subtractions without multiplications.

Worked Example

Consider the 4-point input vector x = [1, 2, 3, 4]. The algorithm processes the array in-place across two butterfly stages.

Stage 1: Pairs elements separated by 1 index (blocks of 2).
x[0] = x[0] + x[1] = 1 + 2 = 3
x[1] = x[0] - x[1] = 1 - 2 = -1
x[2] = x[2] + x[3] = 3 + 4 = 7
x[3] = x[2] - x[3] = 3 - 4 = -1
Vector becomes [3, -1, 7, -1].
Stage 2: Pairs elements separated by 2 indices (blocks of 4).
x[0] = x[0] + x[2] = 3 + 7 = 10
x[1] = x[1] + x[3] = -1 + -1 = -2
x[2] = x[0] - x[2] = 3 - 7 = -4
x[3] = x[1] - x[3] = -1 - -1 = 0
Final transformed vector is [10, -2, -4, 0].

Experiment with the Controls

The interactive visualization allows you to see the butterfly operations in real-time.

Select the Impulse signal and set the Stage to 0. Observe the initial state.
Increment the Stage control step-by-step. Watch how the single non-zero value propagates through the network via the addition (green) and subtraction (red) paths.
Try the Ramp signal and observe how energy is conserved but redistributed across the transformed values. Check the round trip error to see that the inverse accurately reconstructs the input.

Try it out in the interactive module.

Properties and Limitations

The FWHT operates in natural (or Sylvester) order. The output sequence values do not necessarily correspond directly to increasing "sequency" (number of zero crossings), unlike the Fourier transform where frequency strictly increases. To obtain a sequency-ordered transform, the natural output must be bit-reversed and Gray-code permuted.

Efficiency: Dense matrix multiplication requires O(n^2) operations. The FWHT uses a divide-and-conquer strategy reducing this to O(n log n).
Orthogonality: The transformation matrix H satisfies H^T * H = N * I. Thus, the inverse is simply 1/N * H.
Power of Two: The standard FWHT requires the input size N to be a power of two.

References

Learn more about the mathematics and implementation of discrete transforms.

SymPy Discrete Modules Documentation

Fast Walsh–Hadamard Transform