https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=SchmetterlingsgraphSchmetterlingsgraph - Versionsgeschichte2026-06-04T16:48:40ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Schmetterlingsgraph&diff=272521&oldid=prev132.199.53.104: Fehlendes k im Exponenten Omega2021-10-28T09:26:48Z<p>Fehlendes k im Exponenten Omega</p>
<p><b>Neue Seite</b></p><div>[[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]]<br />
Ein '''Schmetterlingsgraph''' ({{enS|butterfly graph}}) zeigt, wie aus der Grundfunktion (der ''Schmetterling'') der [[Fourier-Transformation]] ein schneller Fouriertransformator (FFT, [[schnelle Fourier-Transformation]]) aufgebaut wird.<br />
<br />
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.<br />
<br />
Im einfachsten Fall (radix-2 Cooley und Tukey FFT-Algorithmus) besteht der Schmetterlingsgraph nur aus den dargestellten zwei Ein- und Ausgängen:<br />
<br />
:<math>y_0 = x_0 + x_1</math><br />
:<math>y_1 = x_0 - x_1</math><br />
<br />
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:<br />
<br />
:<math>y_0 = x_0 + x_1 \omega^k</math><br />
:<math>y_1 = x_0 - x_1 \omega^k</math><br />
<br />
mit<br />
<br />
:<math>\omega= \exp \left(-\frac{2 \pi \mathrm i k}{n} \right)</math>,<br />
<br />
dem Index <math>k</math> und der [[imaginäre Einheit|imaginären Einheit]] <math>\mathrm i</math>.<br />
<br />
== Literatur ==<br />
* {{Literatur<br />
|Autor=Alan V. Oppenheim, Ronald W. Schafer<br />
|Titel=Zeitdiskrete Signalverarbeitung<br />
|Auflage=3<br />
|Verlag=R. Oldenbourg<br />
|Datum=1999<br />
|ISBN=3-486-24145-1}}<br />
* {{Literatur<br />
|Autor=Steven W. Smith<br />
|Titel=The Scientist and Engineer's Guide to Digital Signal Processing<br />
|Auflage=1<br />
|Verlag=Elsevier Ltd, Oxford<br />
|Datum=2002<br />
|ISBN=978-0-7506-7444-7<br />
|Kapitel=18<br />
|Sprache=en<br />
|Online=[https://e.dspguide.com/ www.dspguide.com]}}<br />
<br />
[[Kategorie:Numerische Mathematik]]<br />
[[Kategorie:Digitale Signalverarbeitung]]<br />
[[Kategorie:Algorithmus]]</div>132.199.53.104