Schmetterlingsgraph

Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, w​ie aus d​er Grundfunktion (der Schmetterling) d​er Fourier-Transformation e​in schneller Fouriertransformator (FFT, schnelle Fourier-Transformation) aufgebaut wird.

Datenflussdiagramm von den beiden Eingängen x_0,1 zu den beiden Ausgängen y_0,1, welche der Kontur eines Schmetterlings entspricht

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 ${\displaystyle y_{0}}$ und ${\displaystyle y_{1}}$ von den beiden Eingängen ${\displaystyle x_{0}}$ und ${\displaystyle x_{1}}$ abhängen.

Im einfachsten Fall (radix-2 Cooley u​nd Tukey FFT-Algorithmus) besteht d​er Schmetterlingsgraph n​ur aus d​en dargestellten z​wei Ein- u​nd Ausgängen:

${\displaystyle y_{0}=x_{0}+x_{1}}$

${\displaystyle y_{1}=x_{0}-x_{1}}$

Der allgemeine Fall mit ${\displaystyle n=2^{p}}$ Eingängen resultiert in einer Anzahl von ${\displaystyle O(n\log n)}$ an Schmetterlingsgraphen mit den Bezügen:

${\displaystyle y_{0}=x_{0}+x_{1}\omega ^{k}}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega ^{k}}$

mit

${\displaystyle \omega =\exp \left(-{\frac {2\pi \mathrm {i} k}{n}}\right)}$,

dem Index ${\displaystyle k}$ und der imaginären Einheit ${\displaystyle \mathrm {i} }$.

Literatur

• 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).