Diskussion:Schnelle Fourier-Transformation

Erwähnung der Anwendungsgebiete?

Sollte vielleicht erwähnt werden, wo die schnelle Fourier-Transformation Anwendung findet um das Ganze auch greifbarer zu erklären? Bspw. Anwendung bei der Berechnung von WU (Work-Units) im Rahmen von SETI@Home? - Schrottie 23:50, 25. Jul 2004 (CEST)

das wäre interessant. Stern !? 23:53, 25. Jul 2004 (CEST)

Klar. Die Anwendungen sind extrem vielfältig. Ebenso stark sind die Grenzen: äquidistante Daten. Sei mutig! Viele Gruesse --DaTroll 23:54, 25. Jul 2004 (CEST)

Hmmh, müsste sich nur jemand zum "mutig sein" finden, der dann auch den nötigen Background hat. Mir fehlt eben dieser ein bischen, ich kenne diesen Begriff eben nur von einigen Computeranwendungen, deshalb ja auch der Gedanke zu den Anwendungsgebieten, dann kann sich wenigstens auch der Laie etwas darunter vorstellen. - Schrottie 00:01, 26. Jul 2004 (CEST)

Man könnte auch einen Implementierungsansatz (Pseudocode) einfügen !?!

Die Beschleunigung beruht auf...

"Die Beschleunigung gegenüber der direkten Berechnung beruht auf der Vermeidung mehrfacher Berechnung sich gegenseitig aufhebender Terme."

Das verstehe ich nicht so ganz. Kann mir jemand den Satz mal bitte genauer erlaeutern? Muesste es nicht zunaechst einmal heissen: Die Beschleunigung gegenüber der DFT beruht auf...

Und meint der Satz dann schliesslich: Die Beschleunigung gegenüber der DFT beruht auf dem Wegfall der Berechnung sich gegenseitig aufhebender Terme.

ODER: Die Beschleunigung gegenüber der DFT beruht auf dem Wegfall der mehrfachen Berechnung von sich wiederholenden Termen?

Waere super, wenn das jemand auch noch mathematisch auseinanderklamuesern koennte. Also von wegen: "Die FFT berechnet keine Terme doppelt, da ..." streetlife 12:47, 1. Jun 2005 (CEST)

--

Also wenn ich das aus dem Buch 'Numerical Recipes' (Kap. 12, S.506) richtig verstanden habe, beruht die Beschleunigung auf dem Wegfall der Berechnung von sin() und cos() der Vielfachen eines Winkels!? streetlife 13:15, 1. Jun 2005 (CEST)

Die nach Definition ausgeführte DFT verlangt die Multiplikation einer voll besetzten NxN-Matrix mit einem N langen Vektor, das sind N² Multiplikationen und Additionen. Allerdings hat die Matrix Struktur. Ist die Dimension als N=AB faktorisierbar, so kann die Matrix in AxA Blöcke der Größe BxB oder umgekehrt zerlegt werden, wobei alle Blöcke sich bis auf eine Phase gleichen. Dadurch kann die Anzahl der Rechenoperationen reduziert werden. Ist N weiter faktorisierbar, so kann dies rekursiv fortgesetzt werden, bis die FFT bei N=2ⁿ rauskommt.--LutzL 13:25, 1. Jun 2005 (CEST)

Artefakt aus der Übersetzung aus dem Englischen???

Zitat:

Setzen wir n' = n/2 und notieren die geraden Indizes als x'0 = x0, x'1 = x2, ..., x'n'-1 = xn-2 by f0', ..., f 'n'-1; die ungeraden Indizes notieren wir entsprechend: x0 = x1, x1 = x3, ..., xn'-1 = xn-1 by f0, ..., f n'-1. Dann folgt:

Zitat Ende. Die beiden "by" gehören da nicht hin, oder?

FFT und die Zweierpotenzen

Übrigens ..

die FFT sollte im Prinzip auf jeder (Prim)zahl möglich sein, muß aber zugeben das ich dafür noch keine praktische Anwendung gesehen habe. Der Ansatz dafür dürfte wohl entsprechend sein: statt jeden 2. Wert zur Zerlegung der Eingangsfolge in zwei halbsolange zu nehmen nimmt man halt jeden dritten oder fünften etc. Im Falle von 3 erhält man dann eben "radix-3" statt "radix-2" Butterflies. Was dann aber nicht mehr so problemlos geht ist das Bitreversal (das Kompensieren der Verwürfelung von entweder Input oder Outputfolge durch den FFT Algorithmus), da unsere Rechnerzahlensysteme halt auf Binärtechnik und nicht auf Ternär-, oder.. basieren. Mixen von FFT-Stages basierend auf verschiedenen Radizes sollte eigentlich auch gehen - nur macht das wohl für jede Sorte eine eigene Koeffiziententabelle erforderlich, was dann eben etwas unpraktisch ist. Womit wohl auch genug Grund gefunden ist weswegen nur 2erpotenzzerlegungen üblich aber andere eben nicht unmöglich sind .. (Ulixy 19:58, 27. Aug 2005 (CEST))

Hi, s. meine Bemerkung weiter oben. Das Umsortieren erfolgt nach der Regel, dass der Eingangsvektor mit Indizes $0\leq k<AB$ nach Division mit Rest durch A einen Doppelindex bekommt, $k=Am+i,\ 0\leq i<A,\ 0\leq m<B$, dieser bestimmt die Blockstruktur. Der Ausgangsvektor liegt dann in der Reihenfolge $m+Bi$ vor.--LutzL 08:34, 29. Aug 2005 (CEST)

Berechnung der inversen FFT

Sollte man nicht auch erwähnen, dass die iFFT darin besteht, das Vorzeichen des Exponenten umzudrehen und den Faktor ${\frac {1}{n}}$ zu multiplizieren? Steht sogar auf der Seite der DFT (Berechnung der iDFT). Ich weiss aber auch nicht recht, wo das dazu passen würde. Ausserdem fällt mir auf, dass die DFT und die FFT Seite unterschiedliche Formulierungen des Terms im Exponenten verwenden.

Der Unterschied liegt sowohl an den unterschiedlichen Autoren, als auch daran, dass im DFT-Artikel die Berechnungsvorschrift mit von 1 verschiedenem Zeitschritt etc. abgeleitet wird, während hier in einer genau spezifizierten Situation ein Algorithmus beschrieben wird. Die Exponenten sind identisch, nur anders angeordnet. Was aber ist besser... Zur ersten Frage: iFFT als konjugierte FFT darstellen und danach dazuschreiben, dass die kombinierte Anwendung einen Faktor n zur Folge hat, der noch herausdividiert werden muss.--LutzL 11:03, 26. Sep 2005 (CEST)

O-Notation und Schlüsse

Mich verwirrt dieser Satz: "Bei N = 24 = 16 gilt für die Effizienz der FFT Nlog(N) = 64, das heißt, die FFT ist schon für kurze Folgen schneller als eine DFT (N2 = 256). Bei N = 210 = 1024 benötigt die DFT schon 341 mal mehr Zeit als die FFT."

Ich glaube hier wird unterschlagen, dass die O-Notation nicht die wirkliche Laufzeit angibt sondern nur bis auf einen konstanten Faktor. Es ist klar, was gesagt werden soll, aber konkret anzugeben "bei problemgröße soundso ist der algorithmus schon besser" führt mE in die Irre. Günstiger fände ich die Aussage, dass bei quasi allen praktischen Anwendungen die FFT schneller ist.

Dies ist ein Beispiel unter Tausenden für den schlampigen bis falschen Umgang mit Komplexitätsabschätzungen. Deine Kritik ist völlig berechtigt. Im konkreten Fall der schnellen DFT und iDFT sind die Algorithmen ja so glasklar spezifiziert, dass man die einzelnen benötigten Additionen, Multiplikationen, Vergleiche und Zuweisungen genau zählen kann. Entweder tut man dies, dann kann man Aussagen obiger Art treffen, oder man verwendet andernfalls die Landau-Notation und entsprechende Komplexitäten, dann sind die kritisierten Aussagen in der Tat Schmarrn.--JFKCom 21:44, 8. Nov 2005 (CET)

Ich bin gerade etwas irritiert: Ist der Aufwand der FFT nicht N*ld(N) (also Logarithmus Dualis) und nicht zur Basis 10? --Pihalbe 19:29, 10. Apr 2006 (CEST)

Lies mal in Computeralgebra den Abschnitt "Effiziente exakte Arithmetik mit ganzen Zahlen"; das sollte Deine Frage klären. Oder präziser: Der Aufwand der FFT ist O(N*log(N)), wobei die gewählte Basis des Logarithmus gar keine Rolle spielt, da ein Basenwechsel nur einen für die Komplexitätsangabe irrelevanten konstanten Faktor ins Spiel bringt.--JFKCom 19:48, 10. Apr 2006 (CEST)

Okay, danke für den Tip. Mit der O-Notation stand ich bisher immer so ein bissel auf Kriegsfuß. Aber so ist's natürlich klar und korrekt. --Pihalbe 15:08, 11. Apr 2006 (CEST)

---

Ich lese: "Im konkreten Fall der schnellen DFT und iDFT sind die Algorithmen ja so glasklar spezifiziert, dass man die einzelnen benötigten Additionen, Multiplikationen, Vergleiche und Zuweisungen genau zählen kann."

Dazu zwei Anmerkungen: 1 - Die "glasklaren" Spezifikationen bestehen nur aus Formeln. Die Formeln kann man - und tut das in der Praxis auch! - auf unterschiedliche Weise in Rechenschritte umsetzen, und die Zählung ergibt ganz unterschiedliche Werte. Es gibt nicht DEN FFT-Algorithmus, sondern etliche Varianten, die sich in der Rechenzeit deutlich unterscheiden können.

2 - Dass man aus der Anzahl der Multiplikationen auf die Rechenzeit schließen kann, weil alle anderen Operationen sehr viel schneller sind und deshalb vernachlässigt werden können, das war vor Jahrzehnten so und wird immer wieder gern aus älteren Texten abgeschrieben. Heute aber sind die Computer anders konstruiert. FFT ist zum Beispiel eine Standardaufgabe für Digitale Signalprozessoren (DSPs). Ein DSP multipliziert ebensoschnell wie er addiert und subtrahiert, außerdem besitzt er spezielle Befehle zum gleichzeitigen Durchführen mehrerer Operationen, da ist also jedes Zählen der in den Formeln vorkommenden Multiplikationen Unfug. Auch die Größenordnung stimmt dann nicht mehr.

Was man sagen kann, ist nur eins: Es gibt eine Mindestpunktezahl, ab der eine FFT schneller als eine DFT ist, wobei der Vorsprung der FFT mit steigender Punktzahl immer größer wird. (nicht signierter Beitrag von 80.134.237.250 (Diskussion) LutzL 10:37, 18. Mai 2006 (CEST))

Allgemein: Komplexitätsabschätzungen beziehen sich, wenn nichts anderes gesagt wird, auf die Turing-Maschine. Selbst bei einem idealen Arithmetikprozessor fester Wortlänge ergibt sich noch die Dominanz der Multiplikation gegenüber der Addition, wenn man das Rechnen mit hoher Stellenzahl betrachtet. Dann müsste in der Komplexität noch der Aufwand zur Multiplikation von n-Wort-Zahlen aufgeführt werden. Interessanterweise ist das wieder die FFT-Komplexität nach Schönhage-Strassen.

zu 1.) Wenn man einen nackten Arithmetikprozessor betrachtet, der von einer einfachen CPU gesteuert wird und auf trivial gestrickten RAM zugreift, sollte jede der sinnvollen Implementierungen (also nicht künstlich aufgebläht) zur selben Komplexität führen. Unterschiede gibt es, wenn man einen Prozessor-Cache hinzunimmt, da dann die verschiedenen Implementierungen zu einer unterschiedlichen Anzahl von Cache-Misses führen. Das zu untersuchen ist theoretisch etwas komplizierter, die Suche nach optimalen Varianten ist praktisch bisher noch exponentiell. Das SPIRAL-Projekt hat einen heuristischen Suchalgorithmus gebaut, s. [1].

zu 2.) Spezielle Hardware, besonders dann, wenn parallele Abarbeitung im Spiel ist, erfordert natürlich eine separate Komplexitätsabschätzung. Es ist aber ein Spezialfall mit fester kleiner Bitlänge der Zahlen und beschränkter Länge des zu transformierenden Vektors. Sollte auf solcher Hardware ohne weitere Anpassungen mit einer höheren Genauigkeit und längeren Vektoren gerechnet werden, ergibt sich, wenn überhaupt realisierbar, wieder die angegebene Komplexität. Zum (ersten) Vergleich verschiedener Algorithmen ist es aber meist ausreichend, die serielle Rechenzeit auf einfacher Hardware zu betrachten. Oft sind die seriell besseren Algorithmen auch besser parallel implementierbar.

--LutzL 10:37, 18. Mai 2006 (CEST)

Fragen ?

Was begrenzt die Frequenzauflösung ?