Hadamard transform
Encyclopedia
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 transform
s. It is named for the French
mathematician
Jacques Hadamard
, the German-American mathematician Hans Rademacher
, and the American mathematician Joseph Leonard Walsh
. It performs an orthogonal
, symmetric, involutional, linear operation on
real number
s (or complex number
s, although the Hadamard matrices themselves are purely real).
The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transform
s (DFTs), and is in fact equivalent to a multidimensional DFT of size
. It decomposes an arbitrary input vector into a superposition of Walsh function
s.
(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.
(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).)
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 function
s.
), is a one-qubit
rotation
, mapping the qubit-basis 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 algorithm
s use the Hadamard transform as an initial step, since it maps n qubits initialized with
to a superposition of all 2n orthogonal states in the 
basis with equal weight.
One application of the Hadamard gate to either a 0 or 1 qubit will produce a quantum state that, if observed, will be a 0 or 1 with equal probability (as seen in the first two operations). This is exactly like flipping a fair coin in the standard probabilistic model of computation
. However, if the Hadamard gate is applied twice in succession (as is effectively being done in the last two operations), then the final state is always the same as the initial state. This would be like taking a fair coin that is showing heads, flipping it twice, and it always landing on heads after the second flip.
and data compression
algorithms, such as HD Photo and MPEG-4 AVC
. In video compression applications, it is usually used in the form of the sum of absolute transformed differences
.
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
s. It is named for the French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Jacques Hadamard
Jacques Hadamard
Jacques Salomon Hadamard FRS was a French mathematician who made major contributions in number theory, complex function theory, differential geometry and partial differential equations.-Biography:...
, the German-American mathematician Hans Rademacher
Hans Rademacher
Hans Adolph Rademacher was a German mathematician, known for work in mathematical analysis and number theory.-Biography:...
, and the American mathematician Joseph Leonard Walsh
Joseph Leonard Walsh
Joseph Leonard Walsh, was an American mathematician. His work was mainly in the field of analysis.For most of his professional career he studied and worked at Harvard University. He received a B.S. in 1916 and a PhD in 1920. The Advisor of his PhD was Maxime Bôcher...
. It performs an orthogonal
Orthogonal matrix
In linear algebra, an orthogonal matrix , is a square matrix with real entries whose columns and rows are orthogonal unit vectors ....
, symmetric, involutional, linear operation on
real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s (or complex number
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s, although the Hadamard matrices themselves are purely real).
The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
s (DFTs), and is in fact equivalent to a multidimensional DFT of size
. It decomposes an arbitrary input vector into a superposition of Walsh functionWalsh function
In mathematical analysis, the set of Walsh functions form an orthogonal basis of the square-integrable functions on the unit interval. The functions take the values -1 and +1 only, on sub-intervals defined by dyadic fractions...
s.
Definition
The Hadamard transform Hm is a 2m × 2m matrix, the Hadamard matrixHadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...
(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
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
(base-2) representation of the indices n and k.
Recursively, we define the 1 × 1 Hadamard transform H0 by the identity
Identity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
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 unitaryUnitary operator
In functional analysis, a branch of mathematics, a unitary operator is a bounded linear operator U : H → H on a Hilbert space H satisfyingU^*U=UU^*=I...
, if the inputs and outputs are regarded as multidimensional arrays indexed by the nj and kj, respectively.
Some examples of the Hadamard matrices follow.
(This H1 is precisely the size-2 DFT. It can also be regarded as the Fourier transform
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
on the two-element additive group of Z/(2).)
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 function
Walsh function
In mathematical analysis, the set of Walsh functions form an orthogonal basis of the square-integrable functions on the unit interval. The functions take the values -1 and +1 only, on sub-intervals defined by dyadic fractions...
s.
Quantum computing applications
In quantum information processing the Hadamard transformation, more often called Hadamard gate in this context (cf. quantum gateQuantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...
), is a one-qubit
Qubit
In quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....
rotation
Rotation
A rotation is a circular movement of an object around a center of rotation. A three-dimensional object rotates always around an imaginary line called a rotation axis. If the axis is within the body, and passes through its center of mass the body is said to rotate upon itself, or spin. A rotation...
, mapping the qubit-basis states
and to two superposition states with equal weight of the computational basis states and . Usually the phases are chosen so that we havein Dirac notation. This corresponds to the transformation matrix
in the
basis.Many quantum algorithm
Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a...
s use the Hadamard transform as an initial step, since it maps n qubits initialized with
to a superposition of all 2n orthogonal states in the basis with equal weight.Hadamard gate operations
One application of the Hadamard gate to either a 0 or 1 qubit will produce a quantum state that, if observed, will be a 0 or 1 with equal probability (as seen in the first two operations). This is exactly like flipping a fair coin in the standard probabilistic model of computation
Probabilistic Turing machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
. However, if the Hadamard gate is applied twice in succession (as is effectively being done in the last two operations), then the final state is always the same as the initial state. This would be like taking a fair coin that is showing heads, flipping it twice, and it always landing on heads after the second flip.
Computational complexity
The Hadamard transform can be computed in m log m operations, using the fast Hadamard transform algorithm.Other applications
The Hadamard transform is also used in data encryption, as well as many signal processingSignal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
and data compression
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
algorithms, such as HD Photo and MPEG-4 AVC
H.264/MPEG-4 AVC
H.264/MPEG-4 Part 10 or AVC is a standard for video compression, and is currently one of the most commonly used formats for the recording, compression, and distribution of high definition video...
. In video compression applications, it is usually used in the form of the sum of absolute transformed differences
Sum of absolute transformed differences
Sum of absolute transformed differences is a widely used video quality metric used for block-matching in motion estimation for video compression. It works by taking a frequency transform, usually a Hadamard transform, of the differences between the pixels in the original block and the...
.
See also
- Fast Walsh-Hadamard transform
- Joseph Leonard WalshJoseph Leonard WalshJoseph Leonard Walsh, was an American mathematician. His work was mainly in the field of analysis.For most of his professional career he studied and worked at Harvard University. He received a B.S. in 1916 and a PhD in 1920. The Advisor of his PhD was Maxime Bôcher...
- Pseudo-Hadamard transformPseudo-Hadamard transformThe pseudo-Hadamard transform is a reversible transformation of a bit string that provides cryptographic diffusion. See Hadamard transform.The bit string must be of even length, so it can be split into two bit strings a and b of equal lengths, each of n bits...
- Haar transform
External links
- Terry Ritter, Walsh-Hadamard Transforms: A Literature Survey (Aug. 1996)
- Charles Constantine Gumas, http://www.archive.chipcenter.com/dsp/DSP000517F1.html
- Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (May 28, 2009)