Guten Tag, ich beschäftige mich seit längerer Zeit mit der Diskreten Fourier Transformation. Ich habe diese in Octave und Python umgesetzt, und jetzt möchte ich einen schritt weitergehen. Ich möchte die FFT, genauer den Coley-Tukey Algorithmus oder auch Radix-2 Verfahren genauer verstehen und auch mal programmieren. Bei der Diskreten Fourier Transformation ist es ja so, das man sich eine Matrix mit verschiedenen Gewichtungen erstellt, und dann einfach das Audio mit der Matrix multipliziert und dann einfach Integriert. Dann hat man schon den Plot mit den Frequenzen. Was ich bisher zur Fast Fourier Transformation verstanden habe: -Das Audio muss Samples mit der Anzahl von einem Exponenten von 2 haben, damit man es dann bis zum Faktor zwei zerlegen kann. -Man versucht sich anscheinend die Symetrie der Gewichtungen zu nutze zu machen -Zuerst wird zwischen Geraden und Ungeraden Zahlen getrennt. Was ich nicht verstehe ist was man jetzt machen muss, damit man am Ende die Frequenzen hat. Im Internet findet man überall solche Grafiken mit sich Überkreuzenden Pfeilen, ich verstehe die aber nicht. Könnte mir das hier jemand erläutern? Und noch ein Hinweis: Ich habe die Frage schon in einem anderen Forum gestellt, und mir wurde ohne Grund (also die wussten nicht mal wie weit ich überhaupt bin) geschrieben das ich auf einem höheren Mathematischen Niveau sein muss,und dann vertehe ich es. Mathematisch bin ich aber sehr wohl auf einem Niveau das ausreichend ist das zu verstehen. Ich habe auch die Diskrete Fourier Transformation verstanden. Ich frage nur weil mir im Internet überall nur die Formeln hinterhergeschmissen werden und nicht ausreichend genug erläutert werden.
:
Bearbeitet durch User
Dieter A. schrieb: > Ich frage nur weil > mir im Internet überall nur die Formeln hinterhergeschmissen werden und > nicht ausreichend genug erläutert werden. Das Internet ersetzt (noch) keine Bücher. Ich habe festgestellt, das die englischen Wikipedia-Artikel oft ergiebiger sind, was solche Informationen angeht: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Idea
Dieter A. schrieb: > Ich habe > auch die Diskrete Fourier Transformation verstanden. Ich frage nur weil > mir im Internet überall nur die Formeln hinterhergeschmissen werden und > nicht ausreichend genug erläutert werden. Wenn du die DFT verstanden hast, verstehe ich deine Frage nicht. Die Butterfly-Struktur geht direkt aus der DFT-Summe hervor wenn man sie entsprechend ihrer Phasenterme zerlegt hat.
Dieter A. schrieb: > -Man versucht sich anscheinend die Symetrie der > Gewichtungen zu nutze zu machen Ja. Für das Verständnis wichtig ist die Tatsache, dass sich bei der Sinus- wie bei der Kosinusfunktion stets die Werte in der "ersten" Halbwelle (0..pi) nur im Vorzeichen von den um Pi verschobenen Werten der "zweiten" Halbwelle (pi..2pi) unterscheiden. Das hat die Folge, dass man die Reihenfolge von Multiplikation und Addition vertauschen darf: Man darf ERST beide Werte addieren (okay.. eigentlich: subtrahieren) und DANN gemeinsam mit dem Koeffizienten multiplizieren (oder eben auch nicht). > -Zuerst wird zwischen Geraden und Ungeraden Zahlen getrennt. Stopp. Das ist die (übliche) Variante "decimation in time". Ich persönlich finde diese Herleitung ABSOLUT unverständlich; ich habe mich mit "decimation in frequency" (was immer das heißt) befasst. Bei letzterer wird jede Teilfolge immer in eine erste und eine zweite Hälfte aufgeteilt, was aufgrund der Eigenschaft, dass sich erste und zweite Hälfte der "Mischfrequenz" nur im Vorzeichen unterscheiden, leicht verständlich ist. > Was ich nicht verstehe ist was man jetzt machen muss, > damit man am Ende die Frequenzen hat. Im Internet findet > man überall solche Grafiken mit sich Überkreuzenden > Pfeilen, Richtig. :) > ich verstehe die aber nicht. > > Könnte mir das hier jemand erläutern? Das ist leider Stoff für ein ganzes Buch. Meine Ratschläge im Telegrammstil: 1. Mache Dir gründlich klar, was die Additionstheoreme der Winkelfunktionen (sin, cos) besagen. Beachte die verschiedenen Varianten (sin*sin, cos*cos, sin*cos, ...) 2. Mache Dir den Zusammenhang zwischen "Mischung" (im HF- technischen Sinne) und der Multiplikation klar. 3. Befasse Dich AUSFÜHRLICH mit dem Prinzip des I/Q-Mischers. 4. Man kann jetzt die FFT als Abfolge von einzelnen Durchgängen auffassen; bei jedem Durchgang werden einerseits nur Werte durch Addition zusammengefasst und andererseits Werte durch Multiplikation gemischt. Das reine Addieren von Punkten lässt sich auch als Mischung mit der Frequenz "0.0" auffassen (Gleichspannung). Es passiert also folgendes: Im ersten Durchgang werden die Messpunkte im Zeitbereich mit Gleichspannung und mit der Frequenz "1.0" gemischt. Es entstehen zwei Teilfolgen, die jeweils die Hälfte des Speichers einnehmen. (Das klappt ohne Informationsverlust, weil sich erste und zweite Halbwelle der Mischfrequenz nur im Vorzeichen unterscheiden.) Im zweiten Schritt wird mit den Frequenzen "0.0" und "2.0" gemischt -- ABER es wird jedes mit jedem kombiniert. Es entstehen VIER Teilfolgen, die jeweils ein Viertel des Speichers einnehmen: - Im ersten Viertel wurde "0.0" mit "0.0" gemischt; das gibt "0.0" -- also den neuen Gleichanteil. - Im zweiten Viertel wurde "0.0" mit "2.0" gemischt, das gibt die Zwischenergebnisse für die Frequenz "2.0". - Im dritten Viertel wurde "1.0" mit "0.0" gemischt, das gibt "1.0". Das sind die Zwischenergebnisse für die Frequenz "1.0". - Im vierten Viertel wurde "1.0" mit "2.0" gemischt, das gibt "3.0". Das sind die Zwischenergebnisse für die Frequenz "3.0". Man kann erkennen, dass in jedem Durchgang einerseits die alten Zwischenergebnisse einfach weitergereicht werden (Mischung mit "Gleichspannung"), andererseits werden auch alle alten Zwischen- ergebnisse mit der neuen nächsten Zweierpotenz gemischt. Die Mischfrequenzen sind also: 0000000011111111 Mischfrequenz 1 0000222211113333 Mischfrequenz 2 0044226611553377 Mischfrequenz 4 084C2A6E195D3B7F Mischfrequenz 8 Der Algorithmus ist beendet, wenn je Frequenz nur ein (komplexer) Wert übrig ist. > Und noch ein Hinweis: Ich habe die Frage schon in einem anderen > Forum gestellt, und mir wurde ohne Grund (also die wussten nicht > mal wie weit ich überhaupt bin) geschrieben das ich auf einem > höheren Mathematischen Niveau sein muss, und dann vertehe ich es. Diese Diskussion ist nicht zielführend. Für mich ist nicht der Beweis entscheidend, DASS es funktioniert -- ich möchte ein intuitives Verständnis dafür bekommen, WARUM es funktioniert.
Felix U. schrieb: > Dieter A. schrieb: >> Ich habe >> auch die Diskrete Fourier Transformation verstanden. Ich >> frage nur weil mir im Internet überall nur die Formeln >> hinterhergeschmissen werden und nicht ausreichend genug >> erläutert werden. > > Wenn du die DFT verstanden hast, verstehe ich deine Frage > nicht. Dich erwartet der Schock Deines Lebens. > Die Butterfly-Struktur geht direkt aus der DFT-Summe hervor > wenn man sie entsprechend ihrer Phasenterme zerlegt hat. Das mag sein -- aber was als bekannte und offensichtliche Grundtatsache vorausgesetzt werden kann, variiert von Mensch zu Mensch.
Felix U. schrieb: > Wenn du die DFT verstanden hast, verstehe ich deine Frage nicht. Die > Butterfly-Struktur geht direkt aus der DFT-Summe hervor wenn man sie > entsprechend ihrer Phasenterme zerlegt hat. Und ich verstehe dein Unverständnis nicht. Also der TO hat es kapiert, wie man die Elemente des Eingangsfeldes umordnet (Indexinversion) oder sich selbst rekursiv aufruft, so daß man in jeder Stufe jeweils ein Odd und ein Even Feld hat, bis man ans Ende gelangt. Nun fragt er, wie zum Kuckuck es dann weitergeht und wie er aus all dem das Feld mit den finalen Frequenzanteilen tatsächlich erhält. Diese Frage ist doch verständlich! Also erzähle ihm, was er denn in irgend einer existierenden Programmiersprache tun muß. All die grandiosen Pseudo-Codes sind ihm nämlich auch bloß genauso unverständlich wie die rein mathematische Darstellung. Ich sehe das als ein allgemeines Übel an: Die Mathematiker, die damit tagtäglich umgehen, meinen, es sei ja alles derart trivial, daß man es gar nicht erklären muß. Kalauer: "den Löwen zu fangen, wenn er sich zuletzt im Einheitsfeld[x,y] befindet und dort nicht mal ne Pfote rühren kann, überlasse ich den Studenten als Übungsaufgabe für daheim". Vielleicht würde es helfen, wenn man sie zwänge, all das auch mal auf Botokudisch oder Sanskrit zu formulieren, aber OHNE jegliche Sonderzeichen. Kurzum: Wer einem Programmierer erklären will, wie man eine FFT schreibt, der hat dazu eine Programmiersprache zu wählen - sonst bleibt er unverstanden. Ich möchte mal den Mathematiker sehen, der es versteht, wenn ich ihm den CORDIC in PIC-Assembler erkläre, ohne Kommentare und ohne ihm dazu irgend ein mathematisches Pendant zu den Assemblerzeilen zu geben. W.S.
W.S. schrieb: > Die Mathematiker, die damit tagtäglich umgehen, > meinen, es sei ja alles derart trivial, daß man > es gar nicht erklären muß. Nein. Mathematiker betreiben Mathematik, d.h. sie BEWEISEN mathematische Aussagen. Nichtmathematiker wenden die Mathematik an, d.h. sie RECHNEN. Das ist ein ähnlicher Unterschied wie der zwischen Jurist und Kaufmann -- oder der zwischen Gemüsezüchter und Koch.
Dieter A. schrieb: > Im Internet findet man überall solche Grafiken mit > sich Überkreuzenden Pfeilen, ich verstehe die aber nicht. W.S. schrieb: > Also der TO hat es kapiert, > wie man die Elemente des Eingangsfeldes umordnet (Indexinversion) oder > sich selbst rekursiv aufruft, so daß man in jeder Stufe jeweils ein Odd > und ein Even Feld hat, bis man ans Ende gelangt. W.S. schrieb: > Wer einem Programmierer erklären will, wie man > eine FFT schreibt, der hat dazu eine Programmiersprache zu wählen Hallo, die FFT kann man elegant durch einen rekursiven Algorithmus beschreiben und mit einer funktionalen Programmiersprache implementieren (geht natürlich auch in einer imperativen Sprache wie C). Hier ein Beispiel in Scheme: The Scheme Programming Language, Section 12.9. Fast Fourier Transform https://scheme.com/tspl4/examples.html#./examples:h9
> Diese Frage ist doch verständlich! Richtig. > Also erzähle ihm, was er denn in irgend einer existierenden > Programmiersprache tun muß. All die grandiosen Pseudo-Codes sind ihm > nämlich auch bloß genauso unverständlich wie die rein mathematische > Darstellung. Richtig, ich bin weder Mathematiker noch Programmierer. Meine Denkweise ist irgendwas dazwischen. > Ich sehe das als ein allgemeines Übel an: Die Mathematiker, die damit > tagtäglich umgehen, meinen, es sei ja alles derart trivial, daß man es > gar nicht erklären muß. Das ist zu 100% Richtig. Dann hätte ich diese Frage niemals gestellt. > Kalauer: "den Löwen zu fangen, wenn er sich > zuletzt im Einheitsfeld[x,y] befindet und dort nicht mal ne Pfote rühren > kann, überlasse ich den Studenten als Übungsaufgabe für daheim". So fühle ich mich auf Wikipedia. > Ich möchte mal den Mathematiker sehen, der es versteht, wenn ich ihm den > CORDIC in PIC-Assembler erkläre, ohne Kommentare und ohne ihm dazu > irgend ein mathematisches Pendant zu den Assemblerzeilen zu geben. Ich auch. Einfach aus Rache. Danke für die Antwort.
... > Meine Ratschläge im Telegrammstil: ... > Das reine Addieren von Punkten lässt sich auch als Mischung mit > der Frequenz "0.0" auffassen (Gleichspannung). > > Es passiert also folgendes: Im ersten Durchgang werden die > Messpunkte im Zeitbereich mit Gleichspannung und mit der > Frequenz "1.0" gemischt. Es entstehen zwei Teilfolgen, die > jeweils die Hälfte des Speichers einnehmen. (Das klappt ohne > Informationsverlust, weil sich erste und zweite Halbwelle > der Mischfrequenz nur im Vorzeichen unterscheiden.) ... > - Im ersten Viertel wurde "0.0" mit "0.0" gemischt; das gibt > "0.0" -- also den neuen Gleichanteil. > - Im zweiten Viertel wurde "0.0" mit "2.0" gemischt, das > gibt die Zwischenergebnisse für die Frequenz "2.0". > - Im dritten Viertel wurde "1.0" mit "0.0" gemischt, das gibt > "1.0". Das sind die Zwischenergebnisse für die Frequenz "1.0". > - Im vierten Viertel wurde "1.0" mit "2.0" gemischt, das gibt > "3.0". Das sind die Zwischenergebnisse für die Frequenz "3.0". > > Man kann erkennen, dass in jedem Durchgang einerseits die alten > Zwischenergebnisse einfach weitergereicht werden (Mischung mit > "Gleichspannung"), andererseits werden auch alle alten Zwischen- > ergebnisse mit der neuen nächsten Zweierpotenz gemischt. Die > Mischfrequenzen sind also: ... > Der Algorithmus ist beendet, wenn je Frequenz nur ein (komplexer) > Wert übrig ist. ... Danke für die Ausführliche Antwort. Es hat mich definitiv weitergebracht.
Alexander S. schrieb: > die FFT kann man elegant durch einen rekursiven Algorithmus beschreiben > und mit einer funktionalen Programmiersprache implementieren (geht > natürlich auch in einer imperativen Sprache wie C). Hier ein Beispiel in > Scheme: Ja, man kann zeigen, daß... gilt. Hier geht es aber nicht um die beweisführung, daß ein Satz gilt oder daß etwas unter den gezeigten Randbedingungen konvergiert. Das Thema FFT ist ein Thema der angewandten Mathematik. Das heißt im Klartext, daß die Zielrichtung eben die Anwendung ist (und nicht zu mathematischen Beweisen) und diese Anwendung schlußendlich in einen Haufen Maschinencode münden muß, der auf irgend einem Stück Silizium funktionieren soll. Zwischen der Denke der Mathematiker und der tatsächlichen Anwendung klafft noch immer eine riesige Lücke. Manche Mathematiker meinen, sie hätten sich bereits ausreichend den schnöden Niederungen genähert, wenn sie ein Stück Quelle zeigen, das für Matlab etc. gedacht ist und dort lediglich eine der tausend eingebauten Funktionen aufruft. Andere versuchen, aus dieser Lücke ein Geschäft zu machen, indem sie versuchen, vorübersetzte Bibliotheken (ohne Quellcode) für sowas zu verkaufen. Aber die Lücke zwischen mathematischer Darstellung und der Praxis (in Form von Quellen in benutzbaren Programmiersprachen) klafft noch immer. Und sowas wie eine Quelle in "Scheme" ist sowas von weltfremd... Das wirklich einzige Werk, das wenigstens ansatzweise versucht, diese Lücke zu schließen, ist The Scientist and Engineer's Guide to Digital Signal Processing ( http://www.dspguide.com/ ). Dort finden sich wenigstens einige Beispiele in BASIC formuliert. OK, hier ist nicht der platz über Basic zu diskutieren, aber besser dieses als garnichts. W.S.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.