Problem bei FFT

[gammatester]

Zitat von 3_of_8:

Was ist eine FFTw? O_o

Also, ich sags nochmal so: Eine FFT ist ein Spezialfall einer DFT, die auf dem Divide and Conquer-Verfahren beruht (das kennen wir aus der Schönhagen-Strasse-Matrixmultiplikation oder dem Quicksort-Algorithmus). Divide-and-Conquer-Algorithmen funktionieren nur mit Zweierpotenzen.

Wie kommst Du darauf? Divide-and-Conquer geht natürlich auch mit 3, 5 usw. ZB bei den Multiplikationsalgorithmen: 2 -> Karatsuba, 3 usw -> Toom-Cook

Zitat von 3_of_8:

Bei Zahlen, die mit 2 teilerfremd sind, muss also immer eine DFT angewandt werden.

Auch das ist nicht richtig, bzw nicht mehr richtig. Die ersten FFTs arbeiteten mit 2er-Potenzen. Inwischen gibt's FFTs auch für andere Samplegrößen. Hier eine Delphi-Implementation: http://www.simdesign.nl/fft.html

Zitat:

This library provides a free Delphi implementation (source included) for a complex Fast Fourier Transform (FFT) on an arbitrary length data series.

Gruß Gammatester