The Walsh–Hadamard Transform

Trading sinusoids for rectangles

The Fourier and cosine transforms both decompose a signal into smooth, curved waveforms. The Walsh–Hadamard transform throws that away and decomposes a signal into rectangular waveforms instead — basis functions that only ever take the values $+ 1$ and $- 1$ . No multiplication by a fractional cosine value, no complex numbers — just additions and sign flips, which made it extremely cheap to compute on early hardware.

The idea has three names attached to it because it was built in stages: Hadamard developed the matrix structure in 1893, Rademacher identified a related set of orthonormal rectangular-wave functions in 1922, and Walsh completed the connection between them in 1923. Reordered correctly, a Walsh transform is a Hadamard transform — the two names describe the same idea in two different row orderings.

Sequency: frequency for rectangular waves

A sinusoid's rate of oscillation is its frequency. A ±1 rectangular wave doesn't have a frequency in that sense, but it has a direct analogue: sequency, defined as half the number of sign changes (zero crossings) per unit interval. Informally: sequency is just "how choppy does this basis vector look."

Building the Hadamard matrix recursively

The smallest Hadamard matrix is a 2×2 orthonormal building block, and every larger one is built from it recursively:

H_{2} = \frac{1}{2} [11 1 - 1] H_{2 N} = \frac{1}{2} [H_{N} H_{N} H_{N} - H_{N}]

Each step doubles the size by tiling four copies of the previous matrix, negating the bottom-right block. Step through the orders below — in natural order the rows don't look sorted by sequency at all; toggle "sequency order" to see them sorted by zero-crossing count, low to high, the way Walsh originally arranged them.

Interactive · Hadamard Matrix

Sequency order

Reading an entry directly

You never actually need to build the whole matrix to read one entry. Write $x$ and $u$ in binary and let $b_{i} (x)$ denote bit $i$ . Then:

H (u, v) = x, y \sum f (x, y) (- 1)^{β}, β = i = 0 \sum n - 1 b_{i} (x) b_{i} (u) + b_{i} (y) b_{i} (v)

Worked example, $N = 8$ (so $n = 3$ bits): for $x = 6 = 11 0_{2}$ and $u = 1 = 00 1_{2}$ , the bits are $b_{0} (x) = 0, b_{1} (x) = 1, b_{2} (x) = 1$ and $b_{0} (u) = 1, b_{1} (u) = 0, b_{2} (u) = 0$ . Every term in $\sum b_{i} (x) b_{i} (u)$ has at least one zero factor, so $β = 0$ and the sign is $(- 1)^{0} = + 1$ .

Basis images

Following the same $T = K f K$ pattern as every transform in this unit, here's the full 8×8 basis set — each tile a product of two ±1 rectangular waves instead of two cosines:

8 × 8 Hadamard basis images (natural order)

Compare this grid to the DCT's from the previous lesson: same idea (an orthonormal outer-product basis), same increasing complexity moving away from the top-left corner, but hard rectangular edges instead of smooth gradients.

Sequency order and the formal Walsh transform

To sort the natural-order Hadamard rows by sequency, Walsh used a set of functions built from cumulative, modulo-2 sums of the bits of $u$ : $P_{0} (u) = b_{n - 1} (u)$ , $P_{1} (u) = b_{n - 1} (u) \oplus b_{n - 2} (u)$ , and so on down to $P_{n - 1} (u) = b_{1} (u) \oplus b_{0} (u)$ . Substituting $P_{i}$ for $b_{i} (u)$ in the sign formula above reorders the rows so that sequency increases monotonically — exactly the "sequency order" toggle above. Like the Hadamard kernel, the Walsh kernel is separable and symmetric, so its 2-D version is likewise built by two successive applications of the 1-D transform.

Check your understanding

What does the Walsh–Hadamard transform's basis function actually look like, compared to the DCT's?