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 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 . It decomposes an arbitrary input vector into a superposition of Walsh functions.
The transform is named for the French mathematician Jacques Hadamard (), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.
Definition
The Hadamard transform Hm is a 2m × 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2m real numbers xn into 2m real numbers Xk. The Hadamard transform can be defined in two ways: recursively, or by using the binary (base-2) representation of the indices n and k.
Recursively, we define the 1 × 1 Hadamard transform H0 by the identity H0 = 1, and then define Hm for m > 0 by:
where the 1/ is a normalization that is sometimes omitted.
For m > 1, we can also define Hm by:
where represents the Kronecker product. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1.
Equivalently, we can define the Hadamard matrix by its (k, n)-th entry by writing
where the kj and nj are the bit elements (0 or 1) of k and n, respectively. Note that for the element in the top left corner, we define: . In this case, we have:
This is exactly the multidimensional DFT, normalized to be unitary, if the inputs and outputs are regarded as multidimensional arrays indexed by the nj and kj, respectively.
Some examples of the Hadamard matrices follow.
where is the bitwise dot product of the binary representations of the numbers i and j. For example, if , then agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by .
H1 is precisely the size-2 DFT. It can also be regarded as the Fourier transform on the two-element additive group of Z/(2).
The rows of the Hadamard matrices are the Walsh functions.
Advantages of the Walsh–Hadamard transform
Real
According to the above definition of matrix H, here we let H = H[m,n]
In the Walsh transform, only 1 and −1 will appear in the matrix. The numbers 1 and −1 are real numbers so there is no need to perform a complex number calculation.
No multiplication is required
The DFT needs irrational multiplication, while the Hadamard transform does not. Even rational multiplication is not needed, since sign flips is all it takes.
Some properties are similar to those of the DFT
In the Walsh transform matrix, all entries in the first row (and column) are equal to 1.
Discrete Fourier transform：
In discrete Fourier transform, when m equal to zeros (mean first row), the result of DFT also is 1. At the second row, although it is different from the first row we can observe a characteristic of the matrix that the signal in the first raw matrix is low frequency and it will increase the frequency at second row, increase more frequency until the last row.
If we calculate zero crossing:
First row = 0 zero crossing
Second row = 1 zero crossing
Third row = 2 zero crossings
⋮
Eight row = 7 zero crossings
Relation to Fourier transform
The Hadamard transform is in fact equivalent to a multidimensional DFT of size .
Another approach is to view the Hadamard transform as a Fourier transform on the Boolean group . Using the Fourier transform on finite (abelian) groups, the Fourier transform of a function is the function defined by
where is a character of . Each character has the form for some , where the multiplication is the boolean dot product on bit strings, so we can identify the input to with (Pontryagin duality) and define by
This is the Hadamard transform of , considering the input to and as boolean strings.
In terms of the above formulation where the Hadamard transform multiplies a vector of complex numbers on the left by the Hadamard matrix the equivalence is seen by taking to take as input the bit string corresponding to the index of an element of , and having output the corresponding element of .