Schmetterlingsgraph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Datenflussdiagramm von den beiden Eingängen x0,1 zu den beiden Ausgängen y0,1, welche der Kontur eines Schmetterlings entspricht

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

Der Begriff Schmetterling leitet sich im Datenflussdiagramm von der Darstellung der beiden Dreiecke ab, die bei der Darstellung des Grundelementes (time decimation butterfly) der schnellen Fouriertransformation entstehen. Ein Schmetterling bewerkstelligt (jeweils komplex) eine Multiplikation, eine Subtraktion und eine Addition im Rahmen des FFT-Algorithmus von Cooley und Tukey. Durch die Linien wird angezeigt, dass die beiden Ausgänge und von den beiden Eingängen und abhängen.

Im einfachsten Fall (radix-2 Cooley und Tukey FFT-Algorithmus) besteht der Schmetterlingsgraph nur aus den dargestellten zwei Ein- und Ausgängen:

Der allgemeine Fall mit Eingängen resultiert in einer Anzahl von an Schmetterlingsgraphen mit den Bezügen:

mit

,

dem Index und der imaginären Einheit .

  • Alan V. Oppenheim, Ronald W. Schafer: Zeitdiskrete Signalverarbeitung. 3. Auflage. R. Oldenbourg, 1999, ISBN 3-486-24145-1.
  • Steven W. Smith: The Scientist and Engineer's Guide to Digital Signal Processing. 1. Auflage. Elsevier Ltd, Oxford, 2002, ISBN 978-0-7506-7444-7, Kap. 18 (englisch, dspguide.com).