Walsh–Hadamard Transform
A transform with no frequency, only sequency
The Fourier tool's epicycles work because the DFT's basis functions are literal points rotating around a circle. The Walsh–Hadamard transform has no rotation to show — its basis functions (Walsh functions) only ever take the values +1 and −1. Its "nested circles" is instead a nested matrix: the Hadamard matrix is built by recursively tiling four copies of itself, one sign-flipped, doubling in size each round. Toggle coefficients below to build a signal, then watch that recursive doubling — or its FFT-style butterfly network — on the right.Transform Lab: Square Waves Instead of Sine Waves
The Walsh–Hadamard transform (WHT) decomposes a signal into square waves the same way the Fourier transform decomposes it into sine waves — a weighted sum of orthogonal basis functions. The basis, the ordering, and the geometry are all different, though, and those differences are the point of this page.
1. The Hadamard matrix
A Hadamard matrix $H_N$ is an $N\times N$ matrix of $+1$s and $-1$s whose rows are mutually orthogonal: $H_N H_N^\mathsf{T} = N I$. The smallest one is trivial, $H_1=[1]$, and every larger power-of-two size is built from it recursively: $$H_{2N} = \begin{pmatrix} H_N & H_N \\ H_N & -H_N \end{pmatrix}$$ That single recursive rule is the entire construction — no trigonometry involved. The Matrix view in the lab renders $H_N$ directly as a grid of two colors, and the self-similar "quilt" you see is exactly this recursion made visible: each quadrant is a smaller copy of the same matrix, with the bottom-right quadrant sign-flipped.
2. Sequency, not frequency
Each row of $H_N$, read as a signal, is a square wave that switches between $+1$ and $-1$ some number of times. That count is its sequency — the WHT's stand-in for frequency. Row $0$ is constant (sequency $0$, the "DC" term, same role as the Fourier transform's zero-frequency bin); the fastest-switching row has sequency $N-1$. Rows come out of the recursive construction above in an order that mixes sequencies together, so the lab re-sorts them by counting sign changes before putting them on the spectrum bars — that's why the bars in Sequency spectrum read low-to-high left to right, even though the matrix picture (which deliberately keeps the natural, unsorted order to preserve the recursive pattern) does not.
3. Reconstruction is still just superposition
Setting coefficients $c_k$ and reconstructing $x[n]=\sum_k c_k W_k[n]$ is the identical additive idea behind the Fourier series in the epicycle tool — only every "wave" here is piecewise-constant instead of smooth. With one nonzero coefficient the signal is a pure square wave at that sequency; with several, the sum is a step function. Because the rows are orthogonal, energy adds the way you'd hope: $\Vert x \Vert^2 = N\sum_k c_k^2$, a Hadamard version of Parseval's theorem, which the $\Vert x\Vert^2$ stat in the lab lets you check directly.
4. The butterfly network
Multiplying by $H_N$ directly costs $O(N^2)$ operations, but the same recursive structure that makes the matrix self-similar also makes it fast: the Fast Walsh–Hadamard Transform computes it in $O(N\log N)$ using $\log_2 N$ stages of pairwise add/subtract "butterflies" — structurally identical to the FFT's decimation network, but with plain addition and subtraction at every node instead of complex twiddle-factor rotations. The Butterfly view draws that network's wiring for the current $N$: at stage $s$, every index $i$ is paired with $i \oplus 2^s$, and the two outputs are their sum and difference.
5. Where it actually gets used
Because Hadamard butterflies are pure additions (no multiplies, no trigonometric tables), the WHT is cheap on hardware with limited arithmetic: it appears as an alternative block transform in some image/video codecs, as the basis for the orthogonal spreading codes behind CDMA-style spread-spectrum communication, and in Reed–Muller error-correcting codes. It also shows up somewhere more direct than an analogy — the quantum computing Hadamard gate applied to $n$ qubits at once is $H_2^{\otimes n} = H_{2^n}$, the exact matrix built in the lab's recursion.
6. Honesty limit: sequency is coarser than frequency
The DFT diagonalizes ordinary (cyclic) convolution, which is why it is so central to signal processing: convolve two signals in time, multiply their spectra in frequency. The WHT does not share that property for ordinary convolution — it diagonalizes a different operation, dyadic (XOR-indexed) convolution over the Boolean cube. Sequency is a real, useful notion of "how fast a signal wiggles," but it is a combinatorial one tied to the binary structure of the index set, not a continuous notion of pitch or period the way frequency is. Treat the Fourier/Walsh–Hadamard parallel in this pair of tools as "both are orthogonal-basis decompositions," not "these are interchangeable."