Schmetterlingsgraph


Schmetterlingsgraph
Datenflussdiagramm von den beiden Eingäng x0,1 zu den beiden Ausgängen y0,1, welche der Konktur eines Schmetterlings entspricht

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 leitet sich im Datenflussdiagramm von der Darstellung der beiden Dreiecken 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 y0,1 von den beiden Eingängen x0,1 abhängen.

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

y0 = x0 + x1
y1 = x0x1

Im speziellen Fall mit n=2p Eingängen resultiert in einer Anzahl von O(nlog n) an Schmetterlingsgraphen mit den Bezügen:

y0 = x0 + x1ωk
y1 = x0x1ωk

mit \omega= \exp \left(-\frac{2 \pi i}{n} \right), dem Index k und der imaginären Einheit i.

Literatur

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Butterfly-Graph — Schmetterlingsgraph Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, wie aus der Grundfunktion (der Schmetterling) der Fouriertransformation ein schneller Fouriertransformator (FFT, schnelle Fourier Transformation) aufgebaut wird. Der… …   Deutsch Wikipedia

  • Butterfly Graph — Schmetterlingsgraph Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, wie aus der Grundfunktion (der Schmetterling) der Fouriertransformation ein schneller Fouriertransformator (FFT, schnelle Fourier Transformation) aufgebaut wird. Der… …   Deutsch Wikipedia

  • Fast-Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Fast Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Schnelle Fouriertransformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… …   Deutsch Wikipedia

  • Schnelle Fourier-Transformation — Eine schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei solchen Algorithmen handelt es sich… …   Deutsch Wikipedia

  • Butterfly — (engl. für ‚Schmetterling‘) steht für: Butterflymesser oder Balisong, eine Klappmesserart Butterfly (Finanzwesen), eine Investitionsstrategie Butterfly Verschluss, einen stabilen Verschluss, besonders an Transportkisten Venenverweilkanüle, eine… …   Deutsch Wikipedia