Hadamard transform

"Walsh transform" redirects here. Not to be confused with Walsh matrix.

The product of a Boolean function and a Hadamard matrix is its Walsh spectrum:[1]
(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)
Fast Walsh–Hadamard transform, a faster way to calculate the Walsh spectrum of (1, 0, 1, 0, 0, 1, 1, 0).
The original function can be expressed by means of its Walsh spectrum as an arithmetical polynomial.

The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on 2m real numbers (or complex, or hypercomplex numbers, although the Hadamard matrices themselves are purely real).

The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.[2] It decomposes an arbitrary input vector into a superposition of Walsh functions.

The transform is named for the French mathematician Jacques Hadamard (French: [adamaʁ]), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.

  1. ^ Compare Figure 1 in Townsend, W.J.; Thornton, M.A. "Walsh spectrum computations using Cayley graphs". Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001). MWSCAS-01. IEEE. doi:10.1109/mwscas.2001.986127.
  2. ^ Cite error: The named reference kunz was invoked but never defined (see the help page).