Schmetterlingsgraph
aus Wikipedia, der freien Enzyklopädie
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 im Bild unten ist jedes gelbe Kästchen ein solcher Schmetterling. Das Kästchen oben links zeigt auch die beiden Dreiecke.
Ein Schmetterling bewerkstelligt eine komplexe Multiplikation, eine Vorzeichenumkehr und zwei komplexe Additionen.
Im Unterschied zu herkömmlichen Darstellungen wurde hier eine Anordnung der Schmetterlinge gewählt, aus der die fraktale Evolution (hier für N=4, also für 16=2^4 Frequenzen in 4 Evolutionsstufen mit 1, 4, 12 und 32 Schmetterlingen) eines schnellen Fouriertransformators deutlich wird.
Im Bild haben wir als Beispiel 16 Eingänge (0 bis 15) und 16 Ausgänge (auch 0 bis 15). Wenn man die Nummern binär schreibt, dann kann man leichter verstehen, wie die Nummerierung zustande kommt: 0000, 0001, 0010, 0011, ..., 1110, 1111 für den (linken) Eingang des DFT und 0000, 1000, 0100, 1100, ..., 0111, 1111 für den (rechten) Ausgang.
