Schnelle Walshtransformation


Tabelle 1: Schnelle Algorithmen und ihre Autoren Die Schnelle Walshtransformation (FWT) berechnet dasselbe Rechenergebnis wie die Diskrete Walshtransformation (DWT), lediglich etwas schneller. Es existieren diverse schnelle Algorithmen. Wie schon bei der DWT gibt es diese Algorithmen nur, wenn die Anzahl der Elemente im Signalvektor eine Zweierpotenz ist, und dann auch selten für die sehr populäre Sequenzordnung, das heißt, es sind ggf. Umsortierungen erforderlich.

Larsen-Algorithmus:

Exemplarisch sei hier der Algorithmus von H. Larsen aus dem Jahre 1976 vorgestellt. Der Algorithmus arbeitet in-place, das heißt, es wird nur ein Feld erforderlich sein. Anfangs befinden sich dort die Elemente des Signalvektors s, und im selben Feld sind nach Beendigung der Transformation die Walshkoeffizienten s' zu finden.

s' = DWT· s

Die Walshkoeffizienten s' liegen erst nach einer sich anschließenden Bitumkehr-Umordnung der Vektorelemente (engl.: bit-revers order) in Sequenzordnung vor. Die Walshkoeffizienten werden normiert, indem jeder Koeffizient geteilt wird durch die Anzahl N der Vektorelemente in s. Abbildung 1 zeigt ein Struktogramm für den Larsen-Algorithmus [1]:

Abb. 1: Struktogramm [1]

MATLAB:

Achtung! Die MATLAB-Funktion hadamard(8) liefert eine nichtorthogonale Walshmatrix, nicht sequenzgeordnet. Abbildung 2 zeigt ein MATLAB-Skript für den Larsen-Algorithmus mit sequenzgeordnetem Ergebnis:

Abb. 2: MATLAB

C-Programm:

Abbildung 3 zeigt ein C-Programm für den Larsen-Algorithmus:

Abb. 3: C-Programm

Mathcad-Programm:

Abbildung 4 zeigt ein Mathcad-Programm für den Larsen-Algorithmus:

Abb. 4: Mathcad-Programm

PHP-Programm:

Abbildung 5 zeigt ein PHP-Programm für den Larsen-Algorithmus:

Abb. 5: PHP-Programm

Python-Programm:

Abbildung 6 zeigt ein Python-Programm für den Larsen-Algorithmus:

Abb. 6: Python-Programm

Assembler-Programm:

Abbildung 7 zeigt ein Assembler-Programm [1] für den 8-bit-Mikroprozessor U880 (Zilog Z80):

Abb. 7: Assembler-Programm [1]

Pascal-Programm:

Die Abbildungen 8 und 9 zeigen Pascal-Programme für den Larsenalgorithmus:

Abb. 8: Pascal-Programm Abb. 9: Pascal-Programm

HDL-Programm:

Die Abbildungen 10 und 11 zeigen Programme in einer Hardware-Beschreibungs-Sprache (HDL). Der Unterschied zwischen beiden Beispielen [3] besteht in der Matrixzerlegung:
Abb. 10: HDL-Programm [3] Abb. 11: HDL-Programm [3]

Rechenzeiten:

Abbildung 12 zeigt die Rechenzeiten für die Ermittlung von N sequenzgeordneten Walshkoeffizienten mit Hilfe eines 8-bit-Mikroprozessors U880 (Takt 2,5 MHz):

Abb. 12: Rechenzeiten [1]

Analogrechner:

Abbildung 13 zeigt einen Analogrechner für die Walshanalyse kontinuierlicher Signale. Als Ergebnis wurden 64 Walshkoeffizienten als Dezimalzahlen angezeigt [4].

Abb. 13: Rechner aus [4]

Literatur:

  1. Hochmuth, O.: Der Einsatz der Sequenztechnik zur mikrorechnergestützten Klassifikation von Mustern und ihre Anwendung zur Biosignalanalyse. Dissertation A, Humboldt-Universität zu Berlin, 1986
  2. Langer, H., Meffert, B.: Die Sequenztechnik in der Informationsverarbeitung - Grundlagen und Anwendungen. Dissertation B, Humboldt-Universität zu Berlin, 1983
  3. Winkler, F.: Unterrichtsmodell zur Schnellen Walshtransformation. Humboldt-Universität zu Berlin, 1999
  4. Siemens, K.-H.: Walsh Spectral Analysis. PhD-Thesis, McMaster University, Hamilton 1972

© Dr. O. Hochmuth
Dipl.-Inf. Steffen Mankiewicz,
Dipl.-Inf. Enrico May,
Dipl.-Inf. Rainer Schnabel (Programme)
24.01.2019, 13:18:56