Hadamard-Transformation
Die Hadamard-Transformation, auch bezeichnet als Walsh-Hadamard-Transformation, Hadamard-Rademacher-Walsh-Transformation, Walsh-Transformation und als Walsh-Fourier-Transformation, ist eine diskrete Transformation aus dem Bereich der Fourier-Analysis. Sie ist eine orthogonal-symmetrische, selbstinverse und lineare Transformation und von der Struktur her verwandt mit der diskreten Fourier-Transformation (DFT). Die Hadamard-Transformation bildet einen Satz von <math>2^m</math> reellen oder komplexen Eingangswerten in einen Bildbereich aus überlagerten Walsh-Funktionen, dem Walsh-Spektrum, ab.<ref name="Kunz1"/> Die Transformation ist benannt nach den Mathematikern Jacques Hadamard, Joseph L. Walsh und Hans Rademacher.
Die Anwendungen der Hadamard-Transformation liegen im Bereich der digitalen Signalverarbeitung und Datenkompression wie beispielsweise bei JPEG XR und H.264/MPEG-4 AVC.
Definition[Bearbeiten]
.svg){kind=link}
(1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2)
Die Hadamard-Transformation <math>\operatorname{H}_m</math> wird aus einer <math>2^m \times 2^m</math>-Hadamard-Matrix, skaliert mit einem Normalisierungsfaktor, gebildet, welche eine Eingangsfolge <math>(x_n)</math> der Länge <math>2^m</math> mittels einer Matrix-Vektor-Multiplikation in eine Ausgangsfolge <math>(X_k)</math> transformiert.
Die Hadamard-Transformation kann verschiedenartig definiert werden, unter anderem rekursiv, wobei von einer <math>1 \times 1</math>-Hadamard-Transformation <math>\operatorname{H}_0</math> mit der Identität <math>\operatorname{H}_0 = 1</math> ausgegangen wird und <math>\operatorname{H}_m</math> für <math>m > 0</math> festgelegt wird zu:
- <math>\operatorname{H}_m = \frac{1}{\sqrt2} \begin{pmatrix} \operatorname{H}_{m-1} & \operatorname{H}_{m-1} \\ \operatorname{H}_{m-1} & -\operatorname{H}_{m-1} \end{pmatrix}</math>
mit dem Normalisierungsfaktor <math>\tfrac{1}{\sqrt2}</math>, der mitunter auch weggelassen wird.
Analog wie bei der diskreten Fourier-Transformation (DFT) und der optimierten schnellen Fourier-Transformation (FFT) existiert auch eine schnelle Hadamard-Transformation, welche die Anzahl <math>n</math> der Operationen auf <math>n \cdot \operatorname{log} (n)</math> mit <math>n = 2^m</math> reduziert.
Zusammenhang zur diskreten Fouriertransformation[Bearbeiten]
Wie auch die Hadamard-Transformation lässt sich die diskrete Fourier-Transformation als Produkt einer Transformationsmatrix und eines Eingangsvektors formulieren. Sollen per DFT <math>N=2</math> Elemente im Zeitbereich in den Spektralbereich transformiert werden, so lautet die DFT-Matrix
- <math>F_2 = \begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}</math>.
Die Hadamard-Matrix ohne Skalierungsfaktor ist dann als Kronecker-Produkt aus einzelnen <math>2 \times 2</math> DFT-Matrizen konstruierbar:
- <math>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}}}</math>.
Literatur[Bearbeiten]
- Kathy J. Horadam: Hadamard Matrices and their Applications. Princeton University Press, Princeton NJ u. a. 2007, ISBN 978-0-691-11921-2.
Einzelnachweise[Bearbeiten]
<references> <ref name="Kunz1">Henry O. Kunz: On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. In: IEEE Transactions on Computers. Bd. 28, Nr. 3, 1979, ISSN 0018-9340, S. 267–268, doi:10.1109/TC.1979.1675334.</ref> </references>