Schnelle Fourier-Transformation

[altralaser]

Hallo,

für ein Projekt würde ich gern eine adaptierte Form des FFT verwenden. Ich habe mir also zunächst mal eine beispielhafte Implementierung in Java angeschaut:
http://www.ee.columbia.edu/~ronw/cod...va-source.html

Die Syntax ist verständlich, was mir Probleme macht ist die Semantik. Zum besseren Verständnis, wie das Verfahren funktioniert, habe ich also den folgenden Artikel in der Wikipedia gelesen:
http://de.wikipedia.org/wiki/Schnell...Transformation

Ich muss allerdings gestehen, dass ich nicht alles verstanden habe.
Wenn ich beispielsweise ein Array [ 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 ] mit der oben angegebenen Java-Funktion verarbeite, erhalte ich als Ausgabe Re: [ 28.0 -4.0 -4.0 -4.0 -4.0 -3.999 -3.999 -3.999 ] Im: [ 0.0 9.656 4.0 1.656 0.0 -1.656 -4.0 -9.656 ]
Aber was genau sagt mir das jetzt? Was ist die Logik dahinter? Was passiert hier?

Vielen Dank schonmal und viele Grüße

[Wernfried]

Verstehe ich deine Frage richtig, du möchtest von jemanden die Fourier-Transformation erklärt bekommen und wissen was der Zweck einer solchen ist?

Gruss

[Christian Marquardt]

Glaube, dass hat er bei Wikipedia schon herausgefunden, er will erläutert haben, wie das Programm funktioniert und warum diese Ergebnisse kommen

[altralaser]

Ja, wozu der Algorithmus dient, habe ich nachgelesen. Mir ist unklar, wie die Ausgabe bei der dargestellten Eingabe zustande kommt und welche Bedeutung die Ergebnisse in Bezug auf die Eingabeparameter haben.

[Wernfried]

Das verstehe ich jetzt nicht ganz, die verstehst was bei einer FFT gemacht wird und es gibt ein Programm dafür.
Wenn du Eingabe Werte hast, werden die einem mathematischen Algorithmus unterworfen und es kommen andere Werte heraus. Der Weg von Eingabe zu Ausgabe ist blosse Mathematik.

Oder ist dir nicht klar was eine FT im Grunde genommen macht?

Gruss

[altralaser]

Ja genau. Also den Rechenweg kann ich natürlich nachvollziehen. Mir ist etwas schleierhaft, wie die Ergebnisse zu interpretieren sind. Was genau erhalte ich für Daten und was sagen sie mir in Bezug auf die gegebenen Eingaben?

[tömmel]

Ähm... wenn du nicht weisst wozu es gut ist, brauchst du es in der Regel nicht.
Und wenn du es nicht brauchst:

Pack alles zur Fourier-Analyse zu den Büchern über Funktionsräume und Differentialgleichungsgedönse und schau alle Jahre mal nach, wie dick die Staubschicht schon geworden ist

[Wernfried]

Fourier-Transformation für Dummies - (streng mathematisch gesehen sicher nicht haltbar):

Laut Fourier lässt sich jeder beliebige Funktionsverlauf auch als eine Summe von (unendlich vielen) Sinus-Funktionen darstellen. Die Paradeanwendung dafür ist die Elektro- bzw. Nachrichtentechnik. Bezogen auf dieses Gebiet macht die Fourier-Transformation nichts anderes als ein beliebiges Signal in seine (sinusförmigen) Frequenzanteile zu zerlegen.

Trivales Beispiel ist eine einfache Sinus-Schwingung. Wenn du die 50Hz Schwingung aus deiner Steckdose einer Fourier-Transformation unterziehst bekommst du einfach einen einzelnen Punkt (oder je nach Darstellung eine senkrechte Linie) bei 50Hz.

Anderes Beispiel: wenn du eine Rechteckschwingung der Frequenz f einer Fourier-Transformation unterziehst bekommst du sowas wie
4U/π * (sin ωt + sin 3ωt/3 + sin 5ωt/5 + sin 7ωt/7 + ...) mit ω = 2*π*f (π soll das Pi sein), d.h. das ist das Gleiche nur anders ausgedrückt - du kann es einfach mit Excel o.ä. überprüfen.

Die Diskrete, bzw. "Schnelle" Fourier-Transformation ist nun ein Spezialfall, bzw. Vereinfachung. Wenn du z.B. mit deinem PC ein Musikstück bearbeiten möchtest hast du ja keine Funktionsgleichung der Musik, sondern nur eine (diskrete) Liste aus Abtastwerten. Eine solche Liste aus Abtastwerten kann damit ebenfalls in seine Frequenzanteile zerlegt werden um sie dann mit einfachen mathematishen Mitteln zu manipulieren. Anschliessend macht man wieder eine inverse Transformation und hat sein verändertes Musikstück (z.B mit angehobenen Bass-Tönen)

Hoffe die Erklärung hat dir geholfen.

Gruss

[altralaser]

Erstmal vielen Dank für deine Erläuterungen.
Was mir noch etwas unklar ist: In dem Wikipedia-Artikel steht unter anderem, dass die FFT zur Umwandlung von Zeit- oder Raumdaten in Frequenzdaten genutzt wird. Was würde das übertragen auf dein Beispiel mit den Musikstücken bedeuten? Mal ganz dumm gefragt: Wenn ich Bytesequenzen aus einer WAVE-File lese, habe ich dann nicht bereits die Frequenzen der einzelnen Töne vorliegen und kann diese ohne Umrechnungen manipulieren?
Wozu eine Transformation überhaupt nötig ist, steht in dem Wikipedia-Artikel auch nicht. Kann ich nicht gleich die Ausgangswerte bearbeiten? Was dort leider auch nicht zu finden war, in welcher Form die Eingaben überhaupt vorliegen müssen. Deshalb war ich dann eben etwas verwirrt, als ich die Java-Klasse studiert habe, in der einfach ein Array mit den Ziffern von 0 bis 7 verarbeitet wird und plötzlich komplexe Zahlen entstehen.
In der angegebenen Java-Funktion werden außerdem nur Arrays bearbeitet, deren Element-Anzahl einer Zweierpotenz entspricht. Das ist insofern logisch, weil sonst die Berechung bzw. die Zerlegung nicht funktionieren würde. Was mache ich aber, wenn ich ein Array mit einer anderen Anzahl habe? Müsste ich das dann mit Nullen auffüllen oder sowas?

[fanderlf]

Ich glaube das hat er verstanden. Aber er versteht wohl nicht wie er die Werte in dem Array mit der Theorie in Zusammenhang bringen soll.

Re und Im könnte für Real- und imaginärteil stehen. Bin mir aber nicht mehr ganz sicher wie man das in Zusammenhang mit Fourier bringt

[tömmel]

Also Wernfried hat die Idee in dem Beispiel ja schön beschrieben...

Schau dir http://de.wikipedia.org/wiki/Fourier-Reihe an - da sollte klar sein wo die Komplexenzahlen herkommen ....

und weiter unten "Zusammenhang mit der Fourier-Transformation " ist auch recht anschaulich dargestellt was das werden soll...


wenn ihr von da zu eurer "FFT" kommen wollt ist erstmal das :

http://de.wikipedia.org/wiki/Diskret...Transformation

zu verstehen...

aber im Ernst - hab ich auch nie gefressen, und denke mal, wer nich muss.......

[Wernfried]

Was würde das übertragen auf dein Beispiel mit den Musikstücken bedeuten? Mal ganz dumm gefragt: Wenn ich Bytesequenzen aus einer WAVE-File lese, habe ich dann nicht bereits die Frequenzen der einzelnen Töne vorliegen und kann diese ohne Umrechnungen manipulieren?

Nein, wenn du ein Musikstück nimmst, hast du am Anfang ein zeitabhängiges (analoges Ton-)Signal. Dieses Signal muss man zuerst abtasten (unter Berücksichtigung des Nyquist-Shannon-Abtasttheorem). Diese abgetasteten Werte kann man dann in einem WAVE File o.ä. abspeichern. Aus den Abtastwerten kann man nicht erkennen welche Frequenzen das ursprüngliche Signal enthält (es sei denn das Ursprungssignal ist ein Sinus und die Abtastrate ein ganzzahliges Vielfaches dieser Sinusfrequenz), dafür braucht es eben die Fourier-Transformation.

Das das ganze Komplex wird hat mit Mathmatik zu tun, bzw. damit dass es sich besser darstellen lässt.

Die genauen Randbedingungen kenne ich nicht aber bedenke mal, dass ein einfaches Sprachsignal für ein Telefongespräch mit "nur" 8kHz und einer Quantisierungstiefe von 8Bit (d.h. 256 Stufen) abgetastet wird. Da wird es schnell unübersichtlich und man sollte sich auf die Leute verlassen, die davon mehr verstehen als wir und zum Glück die ganze Arbeit schon gemacht haben

Gruss

[gfoidl]

Hallo,

eine einfache Implementierung ist der Algorithmus von Cooley und Tukey. Schau dir zum Verständnis mindestens auch Fourierreihe und Diskrete Fourier-Transformation an.

Was würde das übertragen auf dein Beispiel mit den Musikstücken bedeuten?

Musik ist ein zeitkontinuierliches Signal, das zur Verarbeitung im Computer diskretisiert wird, es sind Zeitdaten - mathematisch gesehen eine Funktion in Abhängigkeit der Zeit => f(f). Diese Funktion wird durch die Fourier-Transformation (FT) in eine Funktion der Frequenzen (und Phasen) übergeführt. Da es um Frequenzen und Phasen geht, ist die Darstellung als komplexe Zeiger einfacher in der (mathematischen) Verwenden - daher auch Real- (Re) und Imaginar- (Im) Teil.

Allgemeiner "besteht" eine Schwingung nicht nur aus der Frequenz, sondern auch aus der Phase. Das lässt sich einfacher als Zeigerdiagramm vorstellen und das entspricht mathematisch gesehen eben der komplexen Ebene. Entsprechend dem ist das Ergebnis mit Re und Im zu verstehen.

Allerdings ist Musik kein optimales Beispiel für eine FT, da bei der FT das gesamte Signal betrachtet wird. Bei Analyse od. Manipulation von Musik bietet sich eher die Wavelet-Transformation od. die Short-time FT an, da so auch eine Zetiauflösung möglich ist.

wie die Ausgabe bei der dargestellten Eingabe zustande kommt und welche Bedeutung die Ergebnisse in Bezug auf die Eingabeparameter haben.

Das findest du leicht heraus, sobald du verstanden hast was die Grundlage (Fourier-Analyse) bedeutet. Diesen Schritt können wir dir hier im Forum kaum abnehmen.

Wenn ich Bytesequenzen aus einer WAVE-File lese, habe ich dann nicht bereits die Frequenzen der einzelnen Töne vorliegen und kann diese ohne Umrechnungen manipulieren?

Nein. Beim (Riff-) Wave hast du die Abtastwerte des zeit-diskretisierten Signals. Siehe Puls-Code-Modulation.
Durch die FT kann dieses Signal vom Zeitraum in den Frequenzraum überführt werden.

Deshalb war ich dann eben etwas verwirrt, als ich die Java-Klasse studiert habe

Das ist meines Erachtes die falsche Vorgehensweise. Schau dir vorher die Grundlagen des Algorithmus an und erst anschließend eine konkrete Implementierung.

Was mache ich aber, wenn ich ein Array mit einer anderen Anzahl habe? Müsste ich das dann mit Nullen auffüllen oder sowas?

Mit Nullen füllen (zero-padding) ist eine Möglichkeit, andere Möglichkeiten sind verschiedene Fenstertechniken od. eine Kombination aus beiden. Das gehört aber zu den erweiterten Grundlagen.

Als Literatur kann ich dir auch Numerical Recipes Books On-Line empfehlen. Schau dir dort am ehesten die C-Version an.
Lies dir auch nochmals Wernfrieds Antworten an.


mfG Gü

[altralaser]

Ich möchte mich nur nochmal für alle eure Antworten, Hinweise und Erläuterungen bedanken. Ich denke, ich habe erstmal einen ganz guten Überblick bekommen und kann mich jetzt etwas eingehender mit der Thematik befassen. Vor allem die Anpassung der Implementierung an mein Projekt sollte mir jetzt etwas leichter fallen. Vielen Dank!