Schmetterlingsgraph

2021-10-28T09:26:48Z

132.199.53.104: Fehlendes k im Exponenten Omega

[[Bild:Butterfly-FFT.png|thumb|right|Datenflussdiagramm von den beiden Eingängen ''x''<sub>0,1</sub> zu den beiden Ausgängen ''y''<sub>0,1</sub>, welche der Kontur eines Schmetterlings entspricht]]
Ein '''Schmetterlingsgraph''' ({{enS|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 [[Komplexe Zahl|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 <math>y_0</math> und <math>y_1</math> von den beiden Eingängen <math>x_0</math> und <math>x_1</math> abhängen.

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

:<math>y_0 = x_0 + x_1</math>
:<math>y_1 = x_0 - x_1</math>

Der allgemeine Fall mit <math>n = 2^p</math> Eingängen resultiert in einer Anzahl von <math>O(n \log n)</math> an Schmetterlingsgraphen mit den Bezügen:

:<math>y_0 = x_0 + x_1 \omega^k</math>
:<math>y_1 = x_0 - x_1 \omega^k</math>

mit

:<math>\omega= \exp \left(-\frac{2 \pi \mathrm i k}{n} \right)</math>,

dem Index <math>k</math> und der [[imaginäre Einheit|imaginären Einheit]] <math>\mathrm i</math>.

== Literatur ==
* {{Literatur
|Autor=Alan V. Oppenheim, Ronald W. Schafer
|Titel=Zeitdiskrete Signalverarbeitung
|Auflage=3
|Verlag=R. Oldenbourg
|Datum=1999
|ISBN=3-486-24145-1}}
* {{Literatur
|Autor=Steven W. Smith
|Titel=The Scientist and Engineer's Guide to Digital Signal Processing
|Auflage=1
|Verlag=Elsevier Ltd, Oxford
|Datum=2002
|ISBN=978-0-7506-7444-7
|Kapitel=18
|Sprache=en
|Online=[https://e.dspguide.com/ www.dspguide.com]}}

[[Kategorie:Numerische Mathematik]]
[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Algorithmus]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Schmetterlingsgraph