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 performs an orthogonal, symmetric, involutive, linear operation on 2^m real numbers (or complex, or hypercomplex numbers, although the Hadamard matrices themselves are purely real).

The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.^[2] It decomposes an arbitrary input vector into a superposition of Walsh functions.

The transform is named for the French mathematician Jacques Hadamard (French: [adamaʁ]), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.

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 (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: $${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$ where the 1/√2 is a normalization that is sometimes omitted.

For m > 1, we can also define H_m by: $${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$$ where ${\displaystyle \otimes }$ represents the Kronecker product. 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 $${\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

where the k_j and n_j are the bit elements (0 or 1) of k and n, respectively. Note that for the element in the top left corner, we define: ${\displaystyle k=n=0}$. In this case, we have: $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

This is exactly the multidimensional ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ 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. Zdroj:https://en.wikipedia.org?pojem=Hadamard_transform
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.