Diskussion:Schnelle Fourier-Transformation/Archiv

Fehler in erster Formel

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Wenn ich mir nicht irre hatte es in der ersten Formel einen kleinen Fehler:

In : $f_{j}=\sum _{k=0}^{2n-1}x_{k}\;e^{-{\frac {2\pi i}{2n}}jk}\qquad j=0,\dots ,n-1.$

j sollte von 0 bis 2n-1 gehen oder? Es ist ja die Rede von der DFT der Grösse 2n. Habe das mal korrigiert.

Smurn 17:11, 24. Jun. 2007 (CEST)

Schmetterlingsgraph identisch zum Quicksort?

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Da das Pivotelement nicht notwendigerweise in der Mitte landen muss ist diese im Artikel gemachte Aussage meiner Ansicht nach falsch.--ThiloHarich 10:43, 16. Jan. 2007 (CET)

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)

Beschlossen, ich füg' einige Anwendungsgebiete hinzu, die ich aus eigener Ansicht kenne, und erkläre gleich grob, warum dieses Anwendungsgebiet von der FFT profitiert. Wenn ich dabei übertrieben habe, dann bitte ich um Korrektur dieses Teils des Artikels.

- Petepall 12:16, 12. Dez 2009 (MET)

Pseudocode

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

Wäre auch für den nichtrekursiven Algoritmus eine gute Idee.

- Petepall 12:16, 12. Dez 2009 (MET)

Die Beschleunigung beruht auf...

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

"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)

Das mit den sich gegenseitig aufhebenden Thermen ist irreführend bis falsch. Rein mathemstisch gesehen ergibt die Die Laufzeit aus T(2^r) = 2 * T (2^{r-1}) + f (2^r). Wobei T(2^n) gesucht ist. Das liegt daran das ja Das Ergebnis A_r aus zwei Ergebnissen A_{r-1} gebildet wird. Der Faktor f (2^r) beschreibt den Aufwand um das Ergebnis mit w^l zu multiplieren und die Ergebnisse zu addieren. Man Kann das auch wie folg ausdrücken: T (n) = 2 * T (n/2) + f (n). Laut Master_Theorem ist die Lauzzeit nach wie vor Quadratisch wenn f (n) = n^2 (dann braucht alleine schon der letzte Schritt n^2 Zeit. Die Addition geht in linearer Zeit. Die Multiplikation braucht nach Schulmethode jedoch n^2. Würde man die Multiplikation weider mit schneller Schnelle Fourier-Transformation machen hätte man folgende Laufzeit: T (n) = 2 * T (n/2) + T (n/2) + O (n) und man wäre bei Karatsuba-Algorithmus. Da die w aber Zweierpotenzen sind führen wir nur Shifts aus. Die sind sicherlich in der Länge der Zahlen ausführbar. In diesem Fall ist f (n) = O (n), und es ergibt sich eine Laufzeit von n*log (n) wie etwa bei Mergesort. Man sollte den Satz also ändern denke ich.--ThiloHarich 15:34, 16. Jan. 2007 (CET)

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

Letzter Kommentar: vor 14 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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)

Hab' soeben einen Versuch unternommen, dies zu tun. -- Peterpall 16:37, 13. Dez. 2009 (CET)

O-Notation und Schlüsse

Letzter Kommentar: vor 18 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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

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 ?

Letzter Kommentar: vor 18 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

Was begrenzt die Frequenzauflösung ? (nicht signierter Beitrag von 62.2.110.51 (Diskussion) -- 12:59, 10. Nov. 2006)

Die Anzahl der Datenpunkte und das Abtastintervall? Es ist fraglich, inwiefern überhaupt von "Auflösung" gesprochen werden kann. Die niedrigsten und höchsten Frequenzen sind "schlechter" "aufgelöst" als die mittleren. Es gibt einen Zeitabstand und eine Punktzahl und daraus resultierend einen Frequenzabstand, der Rest ist Interpretation.--LutzL 15:51, 10. Nov. 2006 (CET)

1. Die Auflösung im Zeitbereich ist die Begrenzung der Frequenzauflösung bzw. vice versa. (wieviele Abtastwerte/Samples pro Zeiteinheit).

2. Natürlich kann von einer Auflösung gesprochen werden: beim Übergang von dem zeitkontinuierlichen Signal zum zeitdiskreten Signal. Es kann die zeitliche bzw. spektrale Auflösung aber auch normiert werden um unabhängig von den konkreten Werten zu sein.

3. Die "niedrigsten/höchsten" Spektralkomponenten (Bins) werden nicht schlechter aufgelöst. Was da vielleicht gemeint sein könnte, ist die "Fensterung" (Windowing) und die damit verbundenen Effekte. Auch das eher bekannte Aliasing bzw. der Leck-Effekt sind Teil aus dem Umfeld bei (zeit)diskreten Systemen: Die Abtastrate bzw. Bin-Breite steht in bestimmten Relation zu dem abgetasteten/zeitdiskreten Signalverlauf und ergibt dann Notwendigkeiten wie Fensterung z.b. mit Hamming-Fenster um Fehler zu minimieren wenn der abgetaste Signalverlauf nicht synchron bzw. keinen ("ganzzahligen") Bezug zur Abtastrate aufweist. Oder auch Methoden wie Overlap-Add/Save um die Blockung der Transformation zu kompensieren. Dieser Punkt fehlt in dem Artikel allerdings komplett, ist vielleicht auch zu weitgehend. (?)

4. Der Rest ist nicht Interpretation, :-), da in einem zeitdiskreten System grundsätzlich zwischen den Datenpunkten (sowohl im Zeitbereich bei den Abtastwerten als auch im Spektralbereich zwischen den Bins) keine Werte vorhanden sind die festgelegt werden könnten. Was Du vielleicht meinst ist der Übergang in ein zeitkontinuierliches Signal: Da muss dann der Verlauf zwischen Abtastwerten bzw. zwischen Bins verschiedenartig interpoliert werden. --wdwd 18:04, 10. Nov. 2006 (CET)

Das ist natürlich richtig und alle Vermutungen sind korrekt. In der Praxis wird aber eine beliebige Sampling-Folge durch eine FFT-Routine gejagt und das Ergebnis dann Spektrum genannt (das ist die Interpretation). Dass das Signal dazu exakt periodisch sein müsste, fällt aus der Überlegung raus. Manchmal wundert sich wer über Schmutzeffekte am Anfang und Ende des Spektrums.--LutzL 07:43, 13. Nov. 2006 (CET)

MP3 und FFT

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

"Die Kombination aus FFT und iFFT kann zur Kodierung und Dekodierung von Signalen auf Frequenzebene eingesetzt werden. Kompressionsalgorithmen wie der des MP3-Formats basieren hierauf."

Dies ist schlichtweg falsch. MPEG-1 Layer 3 beruht auf einer modifizierten Form der Diskreten Cosinus Transformation. Die ist der Fourier Transformation verwandt aber doch nicht identisch!!

--80.129.232.102 15:37, 26. Dez. 2006 (CET) LINNE

hmm jein würd ich dazu murmeln - auch die DCT/MDCT läßt sich mit etwas Hin und Hergerechne dann zum großen Teil durch eine FFT implementieren, die Transformationslängen bei mp3 sind wohl mit Bauchschmerzen gerade noch groß genug um aus dem FFT-Effizienzgewinn noch Nutzen zu ziehen. Außerdem läßt sich die FFT auch zur etwas effizienteren Implementierung des Polyphasenfilters in mp3 (das mpeg audio layer 1,2,3=mp3 gemein ist) einsetzen. Soll heißen man kann die (I)FFT an vielen Stellen, so auch bei mp3 als Algorithmus zur Beschleunigung einsetzen (oder auch nicht), bei den AudioCodecs kommts mehr auf die Idee (Transformationscodec vs Filterbank) an als auf die konkrete Transformation, mp3 ist hier aber durch die mpeg layer1,2,3 Historie interessanterweise eine Mischform im Encoder erstmal Filterbank, dann Transformation in den einzelnen Frequenzbändern um die Frequenzauflösung zu erhöhen, hmm eigentlich sogar eine doppelte Mischform, da MDCT wiederum keine reinrassige Blocktransformation wie FFT oder DCT ist sondern aufeinanderfolgende Blöcke vermixt um Artefakte an den Blockgrenzen zu reduzieren .. uli (nicht signierter Beitrag von 80.187.108.247 (Diskussion | Beiträge) 08:34, 8. Aug. 2009 (CEST))

Implementierung (Pseudocode)

Letzter Kommentar: vor 14 Jahren10 Kommentare6 Personen sind an der Diskussion beteiligt

Fuer mich nicht verstaendlich ist der Begriff "Feld" im Satz "Das Feld wird als Parameter übergeben und..." Was ist mit dem Feld gemeint? Traute Meyer 18:55, 20. Sep. 2008 (CEST)

Ach so, danke, Messwerte sind gemeint. Das ist dann wohl aus der Sicht eines Messtechnikers heraus formuliert. Auf die Messwerte kann man m.E. auch verzichten; theoretische Betrachtungen (ohne Bezug auf Experimente) betrifft die SFT ja auch. Ich will das aber nicht aendern. Traute Meyer 22:03, 9. Okt. 2008 (CEST)

Ist wohl Computersprache, da wird ein Tupel oder Vektor von Zahlen als Array bezeichnet, was man lose als Feld, Datenfeld oder Datenreihe übersetzen kann.--LutzL 12:40, 12. Okt. 2008 (CEST)

In diesem Zusammenhang ergibt sich eine andere Frage: in welchem Intervall (von-bis) liegen die Resultatwerte vor? Für die Eingabedaten f(t) ist das sicher bekannt, aber im Frequenzraum? 82.210.236.73 13:03, 20. Okt. 2008 (CEST)

Wenn man von einem Basisband ausgeht, dann von minus bis plus der halben Abtastfrequenz. Die Anzahl der bestimmten Frequenzen stimmt mit der Anzahl der Abtastpunkte überein und ist diese sind gleichmäßig übers Intervall verteilt.--LutzL 21:58, 20. Okt. 2008 (CEST)

Danke! Ich war so frei und habe es mal eingebaut. 82.210.236.73 09:40, 23. Okt. 2008 (CEST)

Ist der Pseudocode korrekt? Ich habe ihn eben mal implementiert, und erhalte andere Werte als bei der DFT... --89.15.32.89 00:34, 21. Jul. 2009 (CEST)

Noch eine Anmerkung von mir dazu: Der c[k]-Teil schein korrekt zu sein, und erzeugt die gleichen Werte, wie die DFT. Der c[k+n/2]-Teil erzeugt aber keine korrekten Werte --95.116.156.227 14:06, 21. Jul. 2009 (CEST)

~~+1 Das kann ich genau so bestätigen! — Falk _Palaver … 19:48, 9. Mai 2010 (CEST)~~

Meine Implementierung funktioniert jetzt. Ich hatte einen (sehr dummen^^) Fehler bei der Implementation der Multiplikation von algebraischen komplexen Zahlen gemacht. (ComplexNumber mul(ComplexNumber z){ re=re*z.getRe()-im*z.getIm(); im=re*z.getIm()+im*z.getRe(); return this} XD). Soweit ich das also bisher testen konnte, ist der Code korrekt. – Falk _Palaver … 02:45, 10. Mai 2010 (CEST)

Winograd

Letzter Kommentar: vor 15 Jahren4 Kommentare3 Personen sind an der Diskussion beteiligt

Im Artikel darf $N$ ein Produkt von teilerfremden Elementen aus $\{2,3,4,5,7,8,9,16\}$ sein. Ist das nicht nur eine unnötig komplizierte Formulierung für: $N$ ist ein Teiler von 5040 ( $=2^{4}\cdot 3^{2}\cdot 5\cdot 7$ )?--Hagman 12:19, 21. Nov. 2008 (CET)

Ist das nicht eh Bogus? In der englischen WP findet sich nur, dass Winograd eine Erweiterung des Rader-Algorithmus ist, die auch Primzahlpotenzen zulässt. Und der Trick hinter Rader's Algorithm lässt sich auf jede Primzahl anwenden. Wenn man die FFT zu relativ primen Faktoren realisiert hat, kann man auch die FFT zum Produkt erzeugen, das ist halt mit etwas nichttrivialer Umsortierung verbunden. Evtl. gibt es Implementierungen, die diese Einschränkung verwenden, weil für größere Längen andere FFT-Varianten effektiver sind?--LutzL 21:15, 21. Nov. 2008 (CET)

Wenn man hier schon sätzeweise aus einem Buch zitiert, sollte das dann nicht auch genannt werden (Digitale Signalverarbeitung: Filterung und Spektralanalyse mit MATLAB-Übungen; von Karl Dirk Kammeyer,Kristian Kroschel; Seite 245)-- (nicht signierter Beitrag von 95.117.149.46 (Diskussion | Beiträge) 23:41, 13. Nov. 2009 (CET))

Bitte konkrete Angaben machen. Der Text ist jetzt schon Jahre alt und der ursprüngliche Autor bzw. vorgebliche Plagiator ist wahrscheinlich nicht mehr aktiv und wird sich wohl nicht melden.--LutzL 11:14, 14. Nov. 2009 (CET)

Artikel für Nichtstudierte verstehbar machen

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Hallo, momentan ist keine Teilmenge des Artikels ohne Kenntnisse der höheren Mathematik, sprich ohne Mathematik Kurse im Rahmen einer gymnasialen Oberstufe + Studium verstehbar. Damit ist der mögliche Leserkreis recht klein. Dass man die FFT auch so beschreiben kann, dass sie ohne diese Kenntnisse programmierbar ist, davon zeugen entsprechende Berufschulbücher für Auszubildende und zumindest ansatzweise auch ein im Artikel genannter Weblink. Mir ist allerdings nicht klar, wie man diese einfachere Darstellungsweise konkret im Artikel implementieren soll. Denn hierzu müsste man den Text und Struktur des Artikels neu gestalten. Beispielsweise müssten die Summen- und Produktformeln durch Grafiken ersetzt werden. Oder sollte man die jetzige Beschreibung parallel zur einfachen Beschreibungsweise belassen, so dass sich jeder die für ihn besser verstehbare aussuchen kann? Nach den Wikipedia Regeln sollen die einfachen Inhalte an den Anfang des Artikels gestellt werden. Demnach sollte die einfache Darstellung zuerst aufgeführt werden, wenn Parallelität gewünscht ist. Wie sind Eure Meinungen zur Vorgehensweise bei der Lösung dieses Problems? Wie sollten die Überschriften bei paralleler Beschreibung aussehen? So?:

Beschreibung des Algorithmus in einfacher Form
Beschreibung des Algorithmus mit höherer Mathematik

-- 84.132.70.6 16:58, 10. Jan. 2009 (CET)

Hi, eventuell eigenes Kapitel als Ergänzung. Ersatz der bestehenden Gleichungen durch Grafiken (?) ist wohl nicht ideal.--wdwd 18:19, 10. Jan. 2009 (CET)

Elektrotechnische Notation bitte

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Habe grad gesehen, dass j der Index der Spektrallinien ist. Für die imaginäre Einheit wird hingegen i verwendet. Das führt zu Verwirrungen, da beide Größen im Exponenten der e-Funktion auftauchen. Könnte das bitte jemand sauber ändern, wenn Zeit ist: j als imaginäre Einheit, n als Index der Spektrallinie und N als FFT-Länge? Danke! --DB1BMN 00:00, 12. Aug. 2009 (CEST)

Die einheitliche Indizierung [i, j] lässt sich nur auf Portalebene wirkungsvoll diskutieren. --Traute Meyer 21:15, 12. Aug. 2009 (CEST)

Zu allgemeine Aussage

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Richtig ist, daß die FFT am wirkungsvollsten arbeitet, wenn es sich um Zweierpotenzen handelt. Möglich ist sie mit allen Primzahlpotenzen. - -Heinrich Faust (10:34, 14. Aug. 2009 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Bitte neue Beiträge unten anfügen. Wie man im Abschnitt zu den Varianten, im Spiral-Projekt und auch im fftw (fastest fourier trafo in the west) nachlesen kann, gibt es beschleunigte DFTs, die man als FFT bezeichnen kann, für beliebige ganze Zahlen, nicht nur für Primzahlpotenzen. Wobei viele kleine Faktoren natürlich hilfreich sind.--LutzL 11:51, 14. Aug. 2009 (CEST)

So ist der Artikel Schrott ..

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Cooley-Tukey beschreibt FFT für jede Zerlegung N=M_1*M_2 .. N=2^n ist davon nur ein Spezialfall. Bitte auch mal en:WP Cooley–Tukey_FFT_algorithm lesen. Für Primfaktoren gibt es folgenden speziellen Algorithmus: en:WP Prime-factor_FFT_algorithm.

Auch kann sich der Artikel wohl nicht entscheiden, wer die Audience sein soll. Mathematiker? .. die werden eher den Bronstein konsultieren. Informatiker/Ingenieure? .. die finden es hier nicht auf eine Art und Weise die es verständlich machen würde. -- Christian Bahls Mogis 13:59, 21. Nov. 2009 (CET)

Ob Mathematiker zum Thema FFT den Bronstein konsultieren ist fuer den Artikel unerheblich und insbesondere unwahrscheinlich. Aber ich kenne das; man liest einen Artikel und findet dieses und jenes nicht passend. Meine Strategie ist da "Artikel bearbeiten". --Traute Meyer 21:13, 21. Nov. 2009 (CET)

Fehler bei der Implementierung (nichtrekursiv):

Letzter Kommentar: vor 13 Jahren4 Kommentare4 Personen sind an der Diskussion beteiligt

Fehler in folgender Zeile:

Die nächste Schleife zählt das Element innerhalb eines FFT-Abschnittes (im Folgenden "ElementDesAbschnitts" genannt) durch (von 0 bis 2^Ebene)

Das sollte wohl so lauten: 0 bis 2^(Ebene)-1 Bin nämlich grad dabei die FFT in C zu programmieren und so wie der Algorithmus hier angegeben ist ist definitiv ein Fehler drinnen! (nicht signierter Beitrag von 80.108.168.168 (Diskussion | Beiträge) 20:58, 23. Mär. 2010 (CET))

Richtig. Die Schleife geht über N=2^(Ebene) Elemente, also von 1 bis N oder von 0 bis N-1.--LutzL 09:56, 24. Mär. 2010 (CET)

So wie ich das sehe, ist auch noch ein Fehler im Schmetterlingsgraphen. Ich habe es auch überprüft und wie folgt nachimplementiert, es müssten eigentlich schon andere auf den Fehler gestoßen sein, es sei denn, die Permutation des Eingangsvektors wird hier auch anders vollzogen als ich es gemacht habe (der entsprechende Abschnitt müsste vielleicht auch nochmal überarbeitet werden).

{\begin{array}{rcl}x_{\mathrm {links,neu} }&=&x_{\mathrm {links} }+e^{-i\pi {\frac {\mathrm {ElementDesAbschnitts} }{\mathrm {2^{\mathrm {Ebene} }} }}}\cdot x_{\mathrm {rechts} }\\x_{\mathrm {rechts,neu} }&=&x_{\mathrm {links} }-e^{-i\pi {\frac {\mathrm {ElementDesAbschnitts} }{\mathrm {2^{\mathrm {Ebene} }} }}}\cdot x_{\mathrm {rechts} }\end{array}}

So folgt es auch auf den ersten Blick ganz dem Schema des rekursiven Algorithmus. Könnt ihr diesen Fehler bestätigen?

-- Jimi87 01:51, 15. Feb. 2011 (CET)

Ich habe letzte Woche die nichtrekursive Variante implementiert (siehe http://audorra.svn.sourceforge.net/viewvc/audorra/src/AuFFT.pas?revision=62&view=markup#l254 ) und bin dabei auch auf den Fehler gestoßen. Ich verwende nun jedoch folgende Formel für den Schmetterlingsgraphen:

{\begin{array}{rcl}x_{\mathrm {links,neu} }&=&x_{\mathrm {rechts} }+e^{-i\pi {\frac {\mathrm {ElementDesAbschnitts} }{\mathrm {2^{\mathrm {Ebene} }} }}}\cdot x_{\mathrm {links} }\\x_{\mathrm {rechts,neu} }&=&x_{\mathrm {rechts} }-e^{-i\pi {\frac {\mathrm {ElementDesAbschnitts} }{\mathrm {2^{\mathrm {Ebene} }} }}}\cdot x_{\mathrm {links} }\end{array}}

also im Gegensatz zum Artikel vertauschte Vorzeichen bei der Addition.

--Igel457 00:54, 20. Feb. 2011 (CET)

link: local.wasp.uwa.edu.au/~pbourke/other/dft/ (schöner FFT-Code in C, in 1D und 2D)

Letzter Kommentar: vor 13 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Diesen Code als "schönen FFT-Code" zu bezeichnen ist hoffentlich nicht ernst gemeint. Er mag gut und effizient implementiert sein, ist aber nahezu unkommentiert und man kann die Bedeutung der Codezeilen nur erraten. Damit lockt man Leser auf eine Seite, die eher verwirrt, als den Sachverhalt erklärt. (nicht signierter Beitrag von 80.139.255.178 (Diskussion) 21:12, 20. Mär. 2011 (CET))

Artefakt aus der Übersetzung aus dem Englischen???

Letzter Kommentar: vor 19 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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: x″0 = x1, x″1 = x3, ..., x″n'-1 = xn-1 by f0″, ..., f ″n'-1. Dann folgt:

Zitat Ende. Die beiden "by" gehören da nicht hin, oder? (nicht signierter Beitrag von 80.136.231.146 (Diskussion | Beiträge) 23:26, 15. Jun. 2005 (CEST))

schwachsinniger Satz?

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Der Satz "Die Unterschiede liegen in der benötigten Anzahl der Rechenoperationen, so können die Anzahl der Multiplikationen in bestimmten Umfang durch schnellere Addition getauscht werden, und in den notwendigen Speicherplatz für das Bereithalten der zu transformierenden Daten." ergibt keinen Sinn. Korrigieren kann ich ihn aber nicht, da ich nicht weiß, was ausgedrückt werden soll. 14:30 05. Apr 2007 (nicht signierter Beitrag von 141.56.119.120 (Diskussion | Beiträge) 14:33, 5. Apr. 2007 (CEST))

Beispielcode für die iterative FFT

Letzter Kommentar: vor 12 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Wer ist dafür, folgenden Beispielcode für die nicht-rekursive FFT in den Artikel einzufügen? Der Vorteil gegenüber Pseudocode ist: es ist exakt, jeder kann es notfalls mit FreeBasic laufen lassen, und auch wer FreeBasic nicht kennt oder hat, kann trotzdem etwas damit anfangen, da Syntax und Semantik doch recht allgemeinverständlich und -gültig sind. Das sollte allen helfen, die tagelang versuchen, irgendeine dubiose FFT-Implementierung zum Laufen zu bringen. Diese Implementierung ist auch viel verständlicher als z.B. die in Numerical Recipes.

' endlich eine gescheite FFT

Const pi = 6.283185307179586477
Const NN = 128		' Größe Array
Const BB = 7		' Anzahl Bits in NN

Type complex
	r As Double
	i As Double
End Type

Dim Shared As complex a(NN,3), b(NN,BB+1)
Dim Shared As Integer count

Declare Sub main
main
End

Private Function cmplx (r As Double, i As Double) As complex
	Dim As complex c
	c.r = r
	c.i = i
	Return c
End Function

Private Function cmul (a As complex, b As complex) As complex
	Dim As complex c
	c.r = a.r*b.r - a.i*b.i
	c.i = a.r*b.i + a.i*b.r
	Return c
End Function

Private Function cadd (a As complex, b As complex) As complex
	Dim As complex c
	c.r = a.r + b.r
	c.i = a.i + b.i
	Return c
End Function

Private Function csub (a As complex, b As complex) As complex
	Dim As complex c
	c.r = a.r - b.r
	c.i = a.i - b.i
	Return c
End Function

Private Function cexp (a As Double) As complex
	Dim As complex c
	c.r = Cos(a)
	c.i = Sin(a)
	Return c
End Function

Private Sub drawa (m As Integer, bx As Integer, by As Integer)
	Dim As Integer t
	Dim As Double r, i, x, y

	For t = 0 To NN-1
		r = a(t,m).r
		i = a(t,m).i
		x = t
		y = r*20
		Line(bx+x,by)-(bx+x,by-y),RGB(255,0,0)
		x = t+NN+10
		y = i*20
		Line(bx+x,by)-(bx+x,by-y),RGB(255,0,0)
	Next
End Sub

Private Sub inita (m As Integer)
	Dim As Integer t

	For t = 0 To NN-1
		a(t,m).r = Rnd
		a(t,m).i = Rnd
	Next
End Sub

Private Sub scalea (m As Integer, u As Double)
	Dim As Integer t

	For t = 0 To NN-1
		a(t,m).r *= u
		a(t,m).i *= u
	Next
End Sub

Private Function bitreverse (m As Integer) As Integer
	Dim As Integer c, t

	c = 0
	For t = 0 To BB-1
		c = (c Shl 1) Or ((m Shr t) And 1)
	Next
	Return c
End Function

Private Sub fftscramble ()
	Dim As Integer t, d

	For t = 0 To NN-1
		d = bitreverse (t)
		b(d,1) = b(t,0)
	Next
End Sub

Private Sub fftstage (eb As Integer, si As Double)
	Dim As Integer l, k, j
	Dim As complex w, z

	l = 2^eb
	For k = 0 To NN-1 Step l
		For j = 0 To l/2-1
			w = cexp (si*pi*j/l)
			z = cmul (w, b(k+j+l/2,eb))
			b(k+j+l/2,eb+1) = csub (b(k+j,eb), z)
			b(k+j    ,eb+1) = cadd (b(k+j,eb), z)
			count += 2
		Next
	Next
End Sub

Private Sub fft1d (vo As Integer, na As Integer, si As Double)
	Dim As Integer t

	For t = 0 To NN-1
		b(t,0) = a(t,vo)
	Next

	fftscramble ()

	For t = 1 To BB
		fftstage (t, si)
	Next

	For t = 0 To NN-1
		a(t,na) = b(t,BB+1)
	Next
End Sub

Private Sub dft1d (vo As Integer, na As Integer, si As Double)
	Dim As Integer n, k

	For k = 0 To NN-1
		a(k,na) = cmplx (0,0)
		For n = 0 To NN-1
			a(k,na) = cadd (a(k,na), cmul (cexp (si*pi*k*n/NN), a(n,vo)))
			count += 1
		Next
	Next
End Sub

Sub main ()
	Screen 19,32

	Randomize Timer

	inita (1)

	drawa (1, 10, 40)
	count = 0
	dft1d (1, 2, -1)
	Locate 30,1 : Print count;NN*NN
	drawa (2, 10, 240)
	dft1d (2, 3, 1)
	scalea (3, 1/NN)
	drawa (3, 10, 440)

	drawa (1, 310, 40)
	count = 0
	fft1d (1, 2, -1)
	Locate 30,50 : Print count;NN*BB
	drawa (2, 310, 240)
	fft1d (2, 3, 1)
	scalea (3, 1/NN)
	drawa (3, 310, 440)

	GetKey
End Sub

88.217.121.146 13:16, 2. Dez. 2011 (CET)

Hi, halte das für nicht so sinnvoll, da Beispielsammlungen mit langen Programmcodes hier nicht das Thema sind. Siehe bitte sinngemäss Wikipedia:WWNI Punkt 9.--wdwd 14:23, 2. Dez. 2011 (CET)

Ergebniss format des Rekursiven form der FFT

Letzter Kommentar: vor 12 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Hallo, nach dem ich die FFT nach diesem Artikel implementiert habe und mich über das Ergebniss gewundert habe, habe ich von unserem Professor gesagt bekommen, dass das ergebnisfeld nicht wie anngenommen von -f_grenz bis f_grenz geht sondern von -0 bis -f_grenz und dan von f_grenz bis +0 geht. Könnte man das irgendwo im Text erwähnen. (Natürlich fehlen Quellnachweise) <- hab gerade gesehen das es ja unter http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation#Allgemein schon steht, vll. wäre (wie für mich) eine deutlicher Hinweise das man den Teil lesen MUSS angebracht-- Asuro (Diskussion) (02:03, 6. Jun. 2012 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Absatz Radix-4-Algorithmus (bzw. allg. Radix-N)

Letzter Kommentar: vor 12 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Wäre in einer bestimmten Anwendung eine Blocklänge von beispielsweise 2048 Stützstellen ideal und damit auch der Speicherplatz gering zu halten, können diese schnelleren Algorithmen daher nicht eingesetzt werden. Es müsste dann ein größerer Speicher eingesetzt werden und der Rechenaufwand gesteigert werden.

Ich kann hiermit nicht übereinstimmen: Zum einen lässt sich bspw. eine 2048pt FFT berechnen durch 5 Radix-4 Stufen und eine Radix-2 Stufe (Stichwort Mixed-Radix). "Diese schnelleren Algorithmen" können also sehr wohl eingesetzt werden (und werden es auch), ganz insbesondere sogar sehr gut für das gewählte (Gegen-)Beispiel.

Der Halbsatz "Es müsste dann ein größerer Speicher eingesetzt werden und der Rechenaufwand gesteigert werden" erschließt sich mir von der Vorhaben-Zielsetzung nicht: wir wollen doch Spezial-Methoden anwenden um effizienter zu werden! Eine bspw. 2048pt FFT auf 4096pt padden und dann mit Higher-Radix rechnen macht summa summarum keinen Sinn, das ist doch weit weit suboptimaler als 2048pt Standard-Radix-2!!

-- 84.148.106.139 16:33, 13. Jul. 2012 (CEST)

Iterativer Algorithmus fehlerhaft

Letzter Kommentar: vor 11 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Letzter Absatz (über einen Schmetterlingsgraph kombiniert:) müsste lauten:

x[links_neu] = x[links] + x[rechts] * e ^{i*pi*Element/2^Ebene}

x[rechts_neu] = x[links] - x[rechts] * e ^{i*pi*Element/2^Ebene}

Außerdem fehlt dem bitreversen Shuffle ein anschauliches Beispiel:

6(110) -> 3(011) => (0,1,2,3,4,5,6,7) -> (0,4,2,6,1,5,3,7)

N als Anzahl der Ebenen ist schlecht gewählt, da es im rekursiven Algorithmus als Stützstellenzahl dient. Die Anzahl der Ebenen ist folgerichtig log2(N). (nicht signierter Beitrag von 2003:61:E90F:E401:21B:38FF:FE08:7A29 (Diskussion | Beiträge) 00:45, 14. Dez. 2012 (CET))

Iterativer Algorithmus immernoch fehlerhaft?

Letzter Kommentar: vor 9 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Ich denke, da ist ein "off-by-one" Fehler beim Berechnen des Faktors, mit dem x_rechts multipliziert wird. Wenn die Ebene von 0 zählt sollte die Formel so lauten:

{\begin{array}{rcl}x_{\text{links,neu}}&=&x_{\text{links}}+e^{-i\pi {\frac {\text{Element des Abschnitts}}{2^{\text{Ebene+1}}}}}\cdot x_{\text{rechts}}\\x_{\text{rechts,neu}}&=&x_{\text{links}}-e^{-i\pi {\frac {\text{Element des Abschnitts}}{2^{\mathrm {Ebene+1} }}}}\cdot x_{\text{rechts}}\end{array}}

Ich bin in der dahinter liegenden Theorie nicht drin; mir ist das nur beim Implementieren und anschließendem Vergleich mit anderen Implementierungen aufgefallen... (nicht signierter Beitrag von 91.89.245.2 (Diskussion) 17:48, 24. Jan. 2015 (CET))

Vollkommen (Oma-)untauglich...

Letzter Kommentar: vor 9 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

...dieser Artikel. Die WP ist kein Fachlexikon, sondern soll ein Lemma gerade auch für einen Nicht-Fachmann zumindest im Ansatz verständlich machen. Dazu gibt man sich hier nicht mal ansatzweise Mühe. Natürlich ist so etwas Abstraktes schwer anschaulich zu beschreiben, aber es würde schon helfen, ein paar Anwendungen zu nennen, zB könnte man in die Einleitung schreiben, dass die FFT bei der Komprimierung von Bilddaten (JPEG), bei der Videokomprimierung und teilweise bei der Audiokompression essentiell ist. Und schon würde auch der letzte Depp sehen, dass er offensichtlich damit ständig in Berührung kommt. Im Moment kann nur ein Ingenieur oder Mathematiker wissen, worum es hier geht, für alle anderen ist das ein nichtssagender, vollkommen unverständlicher Artikel über für das tägliche Leben ganz offensichtlich irrelevante - jedenfalls dem Anschein nach - höhere Mathematik. Dass dieses Verfahren enorme technische Bedeutung hat, ist mE eine essentielle Aussage für die Einleitung, und nicht wie jetzt für Gliederungspunkt 10 (!) im Artikellangtext. Solaris3 (Diskussion) 15:54, 7. Feb. 2015 (CET)

Okay, ich hab es mal versucht etwas Oma-tauglicher zu formulieren.--Plankton314 (Diskussion) 16:36, 12. Feb. 2015 (CET)

Gefällt mir gut. Goldene Verbesserungs-Medaille für Dich ;-) Solaris3 (Diskussion) 08:50, 13. Feb. 2015 (CET)

Leider ist im Pseudocode die Variable i nicht erklärt.

Letzter Kommentar: vor 9 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Leider ist im Pseudocode die Variable i nicht erklärt. (nicht signierter Beitrag von 94.217.173.239 (Diskussion) 13:52, 16. Mai 2015 (CEST)) Das ist m. E. keine Variable sondern die imaginäre Einheit i. Für die weiter oben (wie bei den "Elektrikern" üblich) j verwendet wurde. Der Autor dachte vielleicht, dass es eigentlich klar sein sollte, wenn man das vorher erklärte verstanden hat. (nicht signierter Beitrag von 178.197.231.102 (Diskussion) 09:41, 30. Nov. 2015 (CET))

Ist der nichtrekursive Pseudocode korrekt?

Letzter Kommentar: vor 8 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Ich habe versucht den Code in Python zu implementieren, aber mindestens die Berechnung der Indizes (links, rechts) erscheint mir fehlerhaft. Für n=8 kommt man in der letzten Iteration ja auf 2^(7+1) * 1 + 2^7-1, was deutlich über der Länge des Eingabevektors liegt.

Gibt es eine Quelle dazu? (nicht signierter Beitrag von 193.111.212.83 (Diskussion) 17:42, 27. Jan. 2016 (CET))

Algorithmus von Cooley und Tukey

Letzter Kommentar: vor 8 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Sollte im Formel nicht m=0,1,…,2n-1 sein? Madyno (Diskussion) 21:51, 14. Apr. 2016 (CEST)

In der ersten Formel? Ja, ich hab’s korrigiert. Danke -- HilberTraum (d, m) 08:33, 15. Apr. 2016 (CEST)