Walsh–Hadamard transform

Summary

The Walsh–Hadamard transform takes a vector of length $2^m$ to the vector of its correlations with all $\pm 1$ patterns given by a Sylvester Hadamard matrix. It is the discrete Fourier transform of the group $(\Z/2\Z)^m$, and its rows are sampled Walsh functions. A fast algorithm computes it with about $m 2^m$ additions and subtractions, and no multiplications. It is used in signal processing, coding theory, the analysis of Boolean functions and quantum computing.