Wie wichtig ist es, bei Verwendung von FFT eine Potenz von 2 zu verwenden?

8

Hier ist das Problem. Ich habe ein 2D-Array von Daten, die erste Spalte repräsentiert die Zeitdaten und die zweite Spalte repräsentiert die sinusförmigen Antwortdaten, basierend auf den Zeitdaten. Ich wende fft an und erhalte meine Frequenz (mit der ich angefangen habe) in einem bestimmten Bin, wie ich erwartet hatte, und ich finde die Amplitude und den Phasenwinkel von diesem Bin. Jetzt ist das Problem, dass ich das gleiche Setup habe, aber mit mehr Datenpunkten wende ich das fft erneut an und die Bin-Nummer ändert sich (was normal ist und wo ich es erwarte), die Amplitude ist die gleiche, aber der Phasenwinkel ist anders) zuerst ist das normal? Zweitens, wie soll ich vorgehen? Vielen Dank

PS: Keine der oben genannten Einstellungen gibt Daten mit einer Potenzlänge von 2 an, beispielsweise die erste mit 1620 Datenpunkten und die zweite mit 1745 Datenpunkten. Daher sollte die nächste Potenz von 2 für beide aus der Anfang?

Lamia
quelle

Antworten:

5

Moderne FFT-Bibliotheken wie FFTW und das Accelerate-Framework von Apple können Nicht-Power-of-2-FFTs sehr effizient ausführen, solange alle Hauptteiler der zusammengesetzten Länge relativ klein sind (2,3,5 usw.)

Eine Potenz von 2 macht es einfacher (ca. 1 Seite Quellcode), wenn Sie aus irgendeinem Grund Ihre eigene FFT codieren müssen oder anderweitig hinsichtlich der maximalen Programmlänge (oder FPGA-Gates usw.) eingeschränkt sind.

Für die Phasenmessung ist es möglicherweise einfacher, eine fftshift (Vorrotation der Daten um N / 2) durchzuführen, um die FFT-Phase auf die Mitte des Datenfensters zu beziehen, wo sich das Verhältnis von Gleichmäßigkeit zu Seltsamkeit und damit die Phase nicht ändert oder wechseln Sie mit der Bin-Nummer (für eine Phase, die in der Mitte dieses Datenfensters gleich ist), auch für Signale, die in der FFT-Länge nicht periodisch sind, wenn Sie die Länge variieren.

hotpaw2
quelle
Hallo hotpaw2, tut mir leid, ich habe vergessen zu erwähnen, dass ich matlab FFT verwende. Macht das einen Unterschied? Danke nochmal.
Lamia
Matlab kann intern eine moderne FFT-Bibliothek wie FFTW verwenden. Überprüfen Sie die Matlab-Dokumentation für Ihre Version.
hotpaw2
Auch, @ hotpaw2, ich benutze bereits fftshift ...
Lamia
Platzieren Sie mit fftshift das Datenfenster in der Mitte, in der Sie die Phase messen möchten. Oder berechnen Sie die Phase von der Mitte nach hinten mit einer guten Frequenzschätzung.
hotpaw2
5

O(Nlog(N))O(N2)

Ich wende das fft erneut an und die Bin-Nummer ändert sich (was normal ist und wo ich es erwarte), die Amplitude ist gleich, aber der Phasenwinkel ist unterschiedlich. Ist das zuerst normal?

Wenn Sie eine größere DFT als Ihren Datenvektor ausführen, werden Sie im Wesentlichen im Frequenzbereich interpolieren. Daher ist Ihr neuer Peak möglicherweise nicht der alte äquivalente Peak, den Sie zuerst erkannt haben, bevor Sie eine größere DFT genommen haben. Und da es nicht dasselbe ist, wählen Sie diesmal im Wesentlichen eine andere komplexe Exponentialbasis (Sinus plus Cosinus), was bedeutet, dass Sie wahrscheinlich einen anderen Phasenwert haben würden, ja.

PS: Keine der oben genannten Einstellungen gibt Daten mit einer Potenzlänge von 2 an, beispielsweise die erste mit 1620 Datenpunkten und die zweite mit 1745 Datenpunkten. Daher sollte die nächste Potenz von 2 für beide aus der Anfang?

Ja, wenn Sie eine Potenz von 2 FFT verwenden möchten, wählen Sie einfach die nächste Potenz von 2 Längen FFT, die größer als Ihre Datensatzlänge ist.

Ich möchte oder möchte nicht unbedingt die Leistung von 2 FFT nutzen (Zeitleistung ist überhaupt nicht mein Problem). Muss ich eher?

fsN

Tarin Ziyaee
quelle
Vielen Dank an user4619 für die Antworten. Ich möchte oder möchte nicht unbedingt die Leistung von 2 FFT nutzen (Zeitleistung ist überhaupt nicht mein Problem). Muss ich eher?
Lamia
Auch @ user4619, da Sie erwähnt haben, dass sich der Phasenwinkel ja ändern könnte, welchem ​​sollte ich vertrauen, das mir die richtige Antwort gibt? (Ich kenne den Phasenwinkel vor der Hand oder die Amplitude nicht, ich kenne nur die Frequenz vor der Hand) ... Danke
Lamia
@lamia Power-of-2 ist nur für Geschwindigkeitsprobleme. Das ist es. Sonst ist nichts Magisches daran. Informationen zum Phasenwinkel - Denken Sie daran, dass sich auch Ihre Spitzenfrequenz ändert, obwohl sich Ihr Phasenwinkel ändert. Wenn Sie eine FFT von 1000 Punkten durchführen, wählen Sie den Frequenzbereich 100 als Peak und ermitteln dessen Phasenwinkel. Das ist richtig. Dann führen Sie eine FFT von 343212 Punkten durch und wählen eine Frequenz 34321 als Spitze aus, die einen anderen Phasenwinkel hat. Das ist immer noch richtig. "Phase" ist eine Funktion der Frequenz. (Wenn Sie dies hilfreich fanden, zögern Sie nicht zu stimmen)
Tarin Ziyaee
@lamia Siehe auch meine Änderungen.
Tarin Ziyaee
Vielen Dank für die Erklärungen, die Sie gegeben haben :)
Lamia
3

Antwort von @ user4619 anzeigen:

Verwenden von IPython, das Matlab ähnelt

In[1]: fft(arange(2**22))
1 loops, best of 3: 354 ms per loop

In[2]: fft(arange(4*1000*90*12)) # close to 2**22
# equal to 2*2 * 2*5*2*5*2*5 * 3*3*2*5 * 2*2*3
1 loops, best of 3: 295 ms per loop

In[2]: fft(arange(2**22+1))
1 loops, best of 3: 14 s per loop

Wenn Sie wirklich Primzahlen verwenden, ist das ziemlich wichtig (Faktor 50!). Wenn Sie Zahlen mit niedrigen Faktoren verwenden, ist dies nicht wichtig. Aber wenn man es nur mit Primzahlen macht, geht es nur schneller - es ändert überhaupt nichts an der Antwort.

Scott
quelle