Ich suche nach einer Möglichkeit die Berechnung für 360 Wertepaare zu optimieren. Ist da etwas bekannt? Bislang fahren wir jeweils 512 Punkte und interpolieren, was nicht so gut gelingt und deshalb besteht die Überlegung, auf 1024 zu wechseln und dann die Ergebnisse auf 360 abzubilden. Es müssen 360 sein weil das Frequenzen sind, die mit Phasenwinkeln korellieren. Idee?
Die FFT nutzt die Symmetrien der DFT bei Längen von 2^n für die vereinfachte Berechnung. Daher ist eine FFT prinzipbedingt stets nur mit Längen von Zweierpotenzen möglich. Die DFT unterliegt dieser Beschränkung nicht und kann über beliebige Längen berechnet werden. Der Rechenaufwand ist allerdings erheblich höher als bei der FFT.
Eine klassische FFT hat eine Laufzeit von O(n*log2(n)), weil sie aus log2(n) hintereinandergeschalteten Stufen von n butterfly Operationen besteht. Mit jeder Stufe werden die Ergebnisse von halb so großen FFTs miteinander verrechnet. Das ganze lässt sich auch auf Zahlen erweitern, die keine Zweierpotenzen sind. Bei der 360 hat man als Faktoren neben drei 2en auch zwei 3en und eine 5. Für eine 3 hätte man dann eine Stufe die drei FFTs verrechnet, die ein Drittel so groß sind und für die 5 eine Stufe, die fünf FFTs verrechnet, die ein Fünftel so groß sind. Bibliotheken wie FFTW machen die Primfaktorzerlegung von selbst und haben für kleine Faktoren vorgefertigte Codeschnipsel, die dann verkettet werden.
:
Bearbeitet durch User
Die abschnittsweise Reduzierung der Rechnung habe ich in Erinnerung. Wurde im Studium vorgerechnet und verstanden. Leider aber nun 25 Jahre her und nicht mehr in Erinnerung. Code-Fragemente die ich hintereinnderschalten könnte, wären sicher eine Hilfe. Ein Suche war aber bisher noch erfolglos.
Man könnte jetzt entsprechend Aufwand treiben mit der FFT und entsprechenden Umrechnungen. Man könnte natürlich auch erstmal prüfen, ob eine DFT für die Aufgabe nicht hinreichend schnell ist sodass man sich das gezumpel mit der FFT nicht sparen kann. Für nicht genutzte Rechenkapazität gilt das selbe wie für nicht genutzt Speicherkapazität: Dafür gibts kein Geld zurück ;)
Doofe Frage: Warum kann man nicht einfach die nächst größere FFT nehmen und die überzähligen Ergebnisse ignorieren?
http://www.fftw.org/ kann sowas auch in O(n log n) "Arbitrary-size transforms. (Sizes with small prime factors are best, but FFTW uses O(N log N) algorithms even for prime sizes.)" 360 = 2 2 2 3 3 * 5 sollte also auch schnell gehen.
Moin, Michael L. schrieb: > Doofe Frage: Warum kann man nicht einfach die nächst größere FFT > nehmen > und die überzähligen Ergebnisse ignorieren? Weil das genauso clever ist, wie wenn man zur Samplerateconversion einfach mal ein paar Samples weglaesst oder welche wiederholt. Kann man so machen, wird halt shice. Zum Originalproblem: Wuerd' ich auch nicht lange rummachen und das Rad versuchen wollen selber zu erfinden, sondern eher gucken, dass ich fftw fuer die eigene HW compiliert krieg'. Gruss WK
Dergute W. schrieb: > Weil das genauso ist, wie wenn man zur Samplerateconversion > einfach mal ein paar Samples weglaesst Da sehe ich den Zusammenhang nicht. Die FFT wird nicht verfälscht, wenn man mehr Frequenzen berechnet und diese nicht benutzt. Der Rest ist nicht tangiert. (???)
Moin, Michael L. schrieb: > Dergute W. schrieb: >> Weil das genauso ist, wie wenn man zur Samplerateconversion >> einfach mal ein paar Samples weglaesst > Da sehe ich den Zusammenhang nicht. Dann solltest du da genauer hinschauen ;-) scnr, WK
Angehängte Dateien:
-
music_fft.jpg
94 KB
Bei der FFT bilden sich "Frequenznummern" mit ganzzahliger Teilung der Abtastfrequenz anhand der FFT-Tiefe. Will man das auf ein anderes "Raster" bringen, muss man entweder die Ergebnisse interpolieren, was der TE offenbar nicht nöchte, oder (wenn man es in Echtzeit physikalisch braucht) die Abtastfrequenz ändern und die Eingangswerte interpolieren. Beides hat seine Vor- und Nachteile. Die Methode 2 wende ich bei einem meiner Audio-GEQ an, der aus das Signal wieder zusammensetzt, profitiere aber von einem geschickt gestrickten Interpolationsfilter und der massiven Überabtastung, die ich im FPGA benutze. Für DSPs und Software ist eine Interpretation der Ergebnisse mit Interpolation einfacher. Auch beim FPGA ist das oft der Weg, wenn es nicht so genau sein muss, wie bei einer Anzeige: Einfach die reinrauschenden FFT-Ergebnisse aus dem Core mit einem einfachen Fenster summieren und jeweils den oberen Bereich benutzen. Eine 2k-FFT löst bis auf 1 Hz auf, wenn man es Oktaven-weise kaskadiert.
Andi F. schrieb: > Arc N. schrieb: >> 360 = 2 2 2 3 3 * 5 sollte also auch schnell gehen. > > Das hatte ich mir angesehen. Und?
Hier ist das eigentlich gut erklärt: https://www.researchgate.net/figure/Positions-in-the-FFT-1920-algorithm-where-scaling-can-be-applied_fig2_38107258
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.