Schmetterlingsgraph

Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, wie aus der Grundfunktion (der Schmetterling) der Fouriertransformation ein schneller Fouriertransformator (FFT, schnelle Fourier-Transformation) aufgebaut wird.

Der Begriff Schmetterling kommt von den beiden Dreiecken, die bei der Darstellung des Grundelementes (time decimation butterfly) der schnellen Fouriertransformation entstehen. In dem Schmetterlingsgraphen ist in jedem Kreis ein solcher Schmetterling. Ein Schmetterling bewerkstelligt eine komplexe Multiplikation, eine Vorzeichenumkehr und zwei komplexe Additionen.

Im Bild haben wir als Beispiel 16 Eingänge (0 bis 15) und 16 Ausgänge (auch 0 bis 15). Die Indizes der Ein- und Ausgänge sind mit Binärzahlen nummeriert.

Quelle:

Artikel Schmetterlingsgraph aus der freien Enzyklopädie Wikipedia mit dieser Versionsgeschichte

Lizenz:

GFDL

Kategorien:

Lexikalischer Artikel