FFT

[Tyrdal]

Gibt es einen Algorithmus für die FFT, der keine Folge der Länge 2^n vorraussetzt? Wennja, wo kann ich den nachlesen?

[Helium]

Weißt du überhaupt, was die FFT ist? Suchst du vielleicht die DFT?

[Tyrdal]

Fast Fourier Transformation. Worauf zielt deine Frage ab?

[Bloops]

Der Trick gewissermaßen, der die DFT "fast" macht, ist gerade, dass sie nur mit Längen von 2^N arbeiten kann. Man nutzt Symmetrien geschickt aus, um sich eine Menge Rechenschritte zu sparen.

Also zu deiner Frage: Nein.

Du kannst

• Eine normale diskrete Fouriertrafo benutzen
• deine Werte mit Nullen auffüllen (Zeropadding) und dann die gewohnte FFT benutzen

mfg

[Marc++us]

Bloops schrieb:

deine Werte mit Nullen auffüllen (Zeropadding) und dann die gewohnte FFT benutzen

Ist aber nicht ungefährlich, das führt zu einem anderen Spektrum.

[Tyrdal]

Die letzten beiden Möglichkeiten waren mir schon bewußt.

Auf die Frage kam ich durch einen Absatz in "Digital Image Processing" von Gonzalez/Woods:

Virtually all comprehensive signal and image processing software packages have generalized implementation of the FFT that handle cases in which the number of points is not an integer power of 2.

Gefunden hatte ich aber nur Algorithmen die eben ne Anzahl als power of 2 brauchen.

[Marc++us]

Die machen das teilweise so, daß die "überzähligen" Argumente mit der DFT transformiert werden, und die 2^n-Anteile mit der FFT.
Also etwa so:

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15  - ist keine 2^n-Folge
|<-  FFT(8)         ->| |<-FFT(4)->|<-DFT->|
DFT zum Zusammenbau der Teilergebnisse

Das geht, ist allerdings eine Indizierungshölle, wie man die jeweiligen Teilergebnisse richtig aufaddiert, und welche Drehzeiger wann verwendet werden müssen.

[Henno]

Zu dem würde ich auch behaupten, dass einige Autoren den Unterschied zwischen FFT und DFT nicht ganz so genau nehmen. Ob das auch hier der Fall ist, kann ich allerdings nicht sagen.

Aber so wie Marcus es erklärt hat, funktioniert ja eh die FFT. Die zerlegt das Signal so lange, bis nur noch ein Glied übrig bleibt und dann wird das ganze wieder zusammen gesetzt. Funktioniert halt super, wenn es auf geht. Wenn es nicht aufgeht, muss man eben extra Algorithmen haben, die den Teil mit der DFT berechnen, der nicht aufgeht.

[Tyrdal]

Ja jetzt wo ihr es sagt hab ich auch ein Papier von einem Glassman gefunden wo genau sowas beschrieben ist, sogar mit Fortran-Code. Dann werd ich das so machen.

[geri.]

warum braucht man diesen komplexen drehzeiger? und was ist so besonders mit dem drehzeiger?

bye

[knivil]

Warum benutzt du keine Bibliothek wie fftw? Wobei bei den Benchmarks deutlich zu sehen ist, dass die Performance stark fluktuiert, wenn die Eingabelaenge keiner Zweierpotenz entspricht.