Hadamard transform
From Wikipedia, the
free encyclopedia
Not to be confused with Walsh
matrix.
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 is named for the French mathematician
Jacques Solomon Hadamard, the
GermanAmerican mathematician Hans Adolph Rademacher, and the American
mathematician Joseph Leonard Walsh. It performs an orthogonal,
symmetric,
involutional, linear
operation on 2^{m} real
numbers (or complex numbers, although the Hadamard matrices
themselves are purely real).
The Hadamard transform can be
regarded as being built out of size2 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.
Contents

[edit] Definition
The Hadamard transform H_{m}
is a 2^{m} × 2^{m} matrix, the Hadamard
matrix (scaled by a normalization factor), that transforms 2^{m}
real numbers x_{n} into 2^{m} real numbers X_{k}.
The Hadamard transform can be defined in two ways: recursively,
or by using the binary (base2) representation of the indices n
and k.
Recursively, we define the
1 × 1 Hadamard transform H_{0} by the identity
H_{0} = 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 n and k,
respectively. 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.
(This H_{1} is
precisely the size2 DFT. It can also be regarded as the Fourier
transform on the twoelement additive group of Z/(2).)
where is the bitwise dot product of the binary
representations of the numbers i and j. For example, , agreeing with the above (ignoring the overall constant). Note that
the first row, first column of the matrix is denoted by H_{00}
The rows of the Hadamard matrices
are the Walsh functions.
[edit] Computational complexity
The Hadamard transform can be
computed in m log m operations, using the fast Hadamard transform algorithm.
[edit] Quantum computing applications
In quantum information processing the
Hadamard transformation, more often called Hadamard gate in this context
(cf. quantum
gate), is a onequbit
rotation,
mapping the qubitbasis states and to two superposition states with equal weight of
the computational basis states and . Usually the phases are chosen so that we have
in Dirac
notation. This corresponds to the transformation matrix
in the basis.
Many quantum
algorithms use the Hadamard transform as an initial step, since it maps n
qubits initialized with to a superposition of all 2^{n}
orthogonal states in the basis with equal weight.
Hadamard gate operations:
[edit] Other applications
The Hadamard transform is also
used in many signal processing and data
compression algorithms, such as HD Photo and MPEG4
AVC. In video compression applications, it is usually
used in the form of the sum of absolute transformed
differences.
[edit] See
also
[edit] External
links
 Terry Ritter, WalshHadamard
Transforms: A Literature Survey (Aug. 1996)
 Charles Constantine Gumas, [1]
Retrieved from
"http://en.wikipedia.org/wiki/Hadamard_transform"