FFT für Vielfache von 360°

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.

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

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

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

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