Hadamard Transform - Definition

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/√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 kj and nj 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 nj and kj, 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 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).)

\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:

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)

    “Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
    —The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)