Schnelle Walshtransformation
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]](./larsen.png "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:
C-Programm:
Abbildung 3 zeigt ein C-Programm für den Larsen-Algorithmus:
Mathcad-Programm:
Abbildung 4 zeigt ein Mathcad-Programm für den Larsen-Algorithmus:
PHP-Programm:
Abbildung 5 zeigt ein PHP-Programm für den Larsen-Algorithmus:
Python-Programm:
Abbildung 6 zeigt ein Python-Programm für den Larsen-Algorithmus:
Assembler-Programm:
Abbildung 7 zeigt ein Assembler-Programm [1]
für den 8-bit-Mikroprozessor U880 (Zilog Z80):
![Abb. 7: Assembler-Programm [1]](./larsena.png "Abb. 7: Assembler-Programm [1]")
Pascal-Programm:
Die Abbildungen 8 und 9 zeigen Pascal-Programme für den Larsenalgorithmus:
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:
- identische Hadamard-Matrizen:
das Rechenwerk muss nur einmal entworfen werden, kann aber mehrfach verwendet
werden; es muss Speicher für die Zwischenresultate Z0 bis Z3 vorgesehen werden
(Abb. 10)
- symmetrische Hadamard-Matrizen:
zwei verschiedene Rechenwerke müssen entworfen werden;
es muss kein Speicher für Zwischenresultate vorgesehen werden
(in-place-Algorithmus, Abb. 11)
![Abb. 10: HDL-Programm [3]](./hdl1.jpg "Abb. 10: HDL-Programm [3]")
![Abb. 11: HDL-Programm [3]](./hdl2.jpg "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 (Zilog Z80, Takt 2.5 MHz) [1]:
![Abb. 12: Rechenzeiten [1]](./larsent.png "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]](./walshanlzr.jpg "Abb. 13: Rechner aus [4]")
Literatur:
- 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
- Langer, H., Meffert, B.:
Die Sequenztechnik in der Informationsverarbeitung - Grundlagen
und Anwendungen.
Dissertation B, Humboldt-Universität zu Berlin, 1983
- Winkler, F.:
Unterrichtsmodell zur Schnellen Walshtransformation.
Humboldt-Universität zu Berlin, 1999
- 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)
18.11.2019, 17:40:44