Schnelle WT

Schnelle Walshtransformation

Tabelle 1: Schnelle Algorithmen und ihre Autoren

Die Schnelle Walshtransformation berechnet dasselbe Rechenergebnis wie die Diskrete Walshtransformation (DWT), lediglich etwas schneller. Es existieren diverse schnelle Algorithmen. Wie schon bei der DWT gibt es diese 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 (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]:

MATLAB:

Abbildung 2 zeigt ein MATLAB-Skript für den Larsen-Algorithmus:

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):

Pascal-Programm:

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

Rechenzeiten:

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

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
Bibliography on Hadamard (Walsh) Transforms