Hadamard transformation

The Hadamard transformation , also referred to as Walsh – Hadamard transformation , Hadamard – Rademacher – Walsh transformation , Walsh transformation and Walsh – Fourier transformation , is a discrete transformation from the field of Fourier analysis . It is an orthogonally symmetric, self-inverse and linear transformation and, in terms of its structure, is related to the discrete Fourier transformation (DFT). The Hadamard transformation maps a set of real or complex input values into an image area made up of superimposed Walsh functions , the Walsh spectrum. The transformation is named after the mathematicians Jacques Hadamard , Joseph L. Walsh and Hans Rademacher . ${\displaystyle 2^{m}}$

The Hadamard transformation is used in the area of digital signal processing and data compression, such as JPEG XR and H.264 / MPEG-4 AVC .

definition

The product of a binary input sequence and a - Hadamard matrix gives the Walsh spectrum: (1,0,1,0,0,1,1,0) * H (8) = (4,2,0, −2, 0,2,0,2) ${\displaystyle 2^{m}\times 2^{m}}$

The Hadamard transformation is formed from a - Hadamard matrix , scaled with a normalization factor, which transforms an input sequence of length into an output sequence by means of a matrix-vector multiplication . ${\displaystyle \operatorname {H} _{m}}$ ${\displaystyle 2^{m}\times 2^{m}}$ ${\displaystyle (x_{n})}$ ${\displaystyle 2^{m}}$ ${\displaystyle (X_{k})}$

The Hadamard transformation can be variously defined, including recursively , wherein a transform -Hadamard with the identity is expected and for set becomes: ${\displaystyle 1\times 1}$ ${\displaystyle \operatorname {H} _{0}}$ ${\displaystyle \operatorname {H} _{0}=1}$ ${\displaystyle \operatorname {H} _{m}}$ ${\displaystyle m>0}$

${\displaystyle \operatorname {H} _{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}\operatorname {H} _{m-1}&\operatorname {H} _{m-1}\\\operatorname {H} _{m-1}&-\operatorname {H} _{m-1}\end{pmatrix}}}$

with the normalization factor , which is sometimes omitted. ${\displaystyle {\tfrac {1}{\sqrt {2}}}}$

Analogous to the discrete Fourier transformation (DFT) and the optimized fast Fourier transformation (FFT) there is also a fast Hadamard transformation , which reduces the number of operations to with . ${\displaystyle n}$ ${\displaystyle n\cdot \operatorname {log} (n)}$ ${\displaystyle n=2^{m}}$

Relation to the discrete Fourier transform

Like the Hadamard transformation, the discrete Fourier transformation can be formulated as the product of a transformation matrix and an input vector. If elements in the time domain are to be transformed into the spectral domain using DFT, the DFT matrix is ${\displaystyle N=2}$

${\displaystyle F_{2}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$.

The Hadamard matrix without a scaling factor can then be constructed as a Kronecker product from individual DFT matrices: ${\displaystyle 2\times 2}$

${\displaystyle H_{2^{k}}={\underset {k{\text{ mal}}}{\underbrace {{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes \ldots \otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}} }}}$.

literature

• Kathy J. Horadam: Hadamard Matrices and their Applications . Princeton University Press, Princeton NJ et al. 2007, ISBN 978-0-691-11921-2 .

Individual evidence

1. ^ Henry O. Kunz: On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. In: IEEE Transactions on Computers. Vol. 28, No. 3, 1979, ISSN  0018-9340 , pp. 267-268, doi : 10.1109 / TC.1979.1675334 .