Hadamard-Transformation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 2^m reellen oder komplexen Eingangswerten in einen Bildbereich aus überlagerten Walsh-Funktionen, dem Walsh-Spektrum, ab.[1] 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]

Das Produkt einer binären Eingangsfolge und einer 2^m \times 2^m-Hadamard-Matrix ergibt das Walsh-Spektrum:
(1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2)

Die Hadamard-Transformation \operatorname{H}_m wird aus einer 2^m \times 2^m-Hadamard-Matrix, skaliert mit einem Normalisierungsfaktor, gebildet, welche eine Eingangsfolge (x_n) der Länge 2^m mittels einer Matrix-Vektor-Multiplikation in eine Ausgangsfolge (X_k) transformiert.

Die Hadamard-Transformation kann verschiedenartig definiert werden, unter anderem rekursiv, wobei von einer 1 \times 1-Hadamard-Transformation \operatorname{H}_0 mit der Identität \operatorname{H}_0 = 1 ausgegangen wird und \operatorname{H}_m für m > 0 festgelegt wird zu:

\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}

mit dem Normalisierungsfaktor \tfrac{1}{\sqrt2}.

Analog wie bei der diskreten Fourier-Transformation (DFT) und der optimierten schnellen Fourier-Transformation (FFT) existiert auch eine schnelle Hadamard-Transformation, welche die Anzahl n der Operationen auf n \cdot \operatorname{log} (n) mit n = 2^m reduziert.

Literatur[Bearbeiten]

  •  K. J. Horadam: Hadamard Matrices and Their Applications. Princeton University Press, 2006, ISBN 978-0-69111921-2.

Einzelnachweise[Bearbeiten]

  1. H.O. Kunz: On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. In: IEEE Transactions on Computers. 28, Nr. 3, 1979, S. 267–268. doi:10.1109/TC.1979.1675334.