Hadamard Transform - Definition

Definition

The Hadamard transform H_m is a 2m × 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2m real numbers x_n into 2m real numbers X_k. 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 H₀ by the identity H₀ = 1, and then define H_m for m > 0 by:

where the 1/√2 is a normalization that is sometimes omitted. 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

and

where the k_j and n_j are the binary digits (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 n_j and k_j, respectively.

Some examples of the Hadamard matrices follow.

$\begin{align} H_0 = &+1\\ H_1 = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

(This H₁ is precisely the size-2 DFT. It can also be regarded as the Fourier transform on the two-element additive group of Z/(2).)

$\begin{align} H_2 = \frac{1}{2} &\begin{pmatrix}\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\end{pmatrix}\\ H_3 = \frac{1}{2^{\frac{3}{2}}} &\begin{pmatrix}\begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1\\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1\\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1\\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1\\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{array}\end{pmatrix}\\ (H_n)_{i,j} = \frac{1}{2^{\frac{n}{2}}} &(-1)^{i \cdot j} \end{align}$

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 of the matrix is denoted by .

The rows of the Hadamard matrices are the Walsh functions.

Read more about this topic: Hadamard Transform

Famous quotes containing the word definition:

“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)

“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)

“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)