Grundlegendes zur FFT-Ausgabe

87

Ich brauche Hilfe beim Verständnis der Ausgabe der DFT / FFT-Berechnung.

Ich bin ein erfahrener Softwareentwickler und muss einige Messwerte des Smartphone-Beschleunigungsmessers interpretieren, z. B. das Ermitteln der Hauptfrequenzen. Leider habe ich vor fünfzehn Jahren die meisten meiner College-EE-Klassen durchgeschlafen, aber ich habe in den letzten Tagen über DFT und FFT gelesen (anscheinend ohne Erfolg).

Bitte keine Antworten von "Nehmen Sie an einem EE-Kurs teil". Ich habe tatsächlich vor, das zu tun, wenn mein Arbeitgeber mich bezahlt. :) :)

Also hier ist mein Problem:

Ich habe ein Signal mit 32 Hz aufgenommen. Hier ist eine 1-Sekunden-Stichprobe von 32 Punkten, die ich in Excel aufgezeichnet habe.

Geben Sie hier die Bildbeschreibung ein

Ich habe dann einen FFT-Code in Java von der Columbia University geschrieben (nachdem ich den Vorschlägen in einem Beitrag zu " Zuverlässige und schnelle FFT in Java " gefolgt bin ).

Die Ausgabe dieses Programms ist wie folgt. Ich glaube, es wird eine direkte FFT ausgeführt, daher wird der gleiche Puffer sowohl für die Eingabe als auch für die Ausgabe wiederverwendet.

Before: 

Re: [0.887  1.645  2.005  1.069  1.069  0.69  1.046  1.847  0.808  0.617  0.792  1.384  1.782  0.925  0.751  0.858  0.915  1.006  0.985  0.97  1.075  1.183  1.408  1.575  1.556  1.282  1.06  1.061  1.283  1.701  1.101  0.702  ]

Im: [0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  ]

After: 

Re: [37.054  1.774  -1.075  1.451  -0.653  -0.253  -1.686  -3.602  0.226  0.374  -0.194  -0.312  -1.432  0.429  0.709  -0.085  0.0090  -0.085  0.709  0.429  -1.432  -0.312  -0.194  0.374  0.226  -3.602  -1.686  -0.253  -0.653  1.451  -1.075  1.774  ]

Im: [0.0  1.474  -0.238  -2.026  -0.22  -0.24  -5.009  -1.398  0.416  -1.251  -0.708  -0.713  0.851  1.882  0.379  0.021  0.0  -0.021  -0.379  -1.882  -0.851  0.713  0.708  1.251  -0.416  1.398  5.009  0.24  0.22  2.026  0.238  -1.474  ]

An diesem Punkt kann ich also weder Kopf noch Zahl der Ausgabe machen. Ich verstehe die DFT-Konzepte, wie der reale Teil die Amplituden der Komponenten-Cosinuswellen und der Imaginärteil die Amplituden der Komponenten-Sinuswellen sind. Ich kann diesem Diagramm auch aus dem großartigen Buch " Der Leitfaden für Wissenschaftler und Ingenieure zur digitalen Signalverarbeitung " folgen : Geben Sie hier die Bildbeschreibung ein

Meine spezifischen Fragen sind also:

  1. Wie finde ich am Ausgang der FFT die "am häufigsten auftretenden Frequenzen"? Dies ist Teil meiner Analyse meiner Beschleunigungsmesserdaten. Soll ich die realen (Cosinus) oder imaginären (Sinus) Arrays lesen?

  2. Ich habe eine 32-Punkte-Eingabe im Zeitbereich. Sollte die Ausgabe der FFT nicht ein 16-Elemente-Array für Real und ein 16-Elemente-Array für Imaginäre sein? Warum gibt mir das Programm reale und imaginäre Array-Ausgaben der Größe 32?

  3. Wie analysiere ich im Zusammenhang mit der vorherigen Frage die Indizes in den Ausgabearrays? Angesichts meiner Eingabe von 32 Abtastwerten, die mit 32 Hz abgetastet wurden, sollte nach meinem Verständnis der Index eines 16-Element-Array-Ausgangs gleichmäßig auf die Hälfte der Abtastrate (von 32 Hz) verteilt sein des Arrays repräsentiert (32 Hz * 1/2) / 16 = 1 Hz?

  4. Warum hat der FFT-Ausgang negative Werte? Ich dachte, die Werte repräsentieren Amplituden einer Sinuskurve. Zum Beispiel sollte der Ausgang von Real [3] = -1,075 eine Amplitude von -1,075 für eine Kosinuswelle der Frequenz 3 bedeuten. Ist das richtig? Wie kann eine Amplitude negativ sein?

stackoverflowuser2010
quelle
Was möchten Sie aus den Beschleunigungsmesserwerten berechnen: Geschwindigkeit, Entfernung? Das Rauschen der Beschleunigungsmesser-Messwerte folgt der Gaußschen Verteilung, und ich kann nicht sehen, wie die Anpassung einer Sinuswelle Abhilfe schaffen würde.
Ali
2
Das Java-Tag sollte entfernt werden, da es allgemeiner ist als eine bestimmte Sprache
user3791372
Wenn man die Quelle der Columbia University betrachtet, ist sie überhaupt nicht effizient. Es ist eine einfache, nicht optimierte Implementierung von Cooley-Tucky mit Schmetterlings-Nachschlagetabellen, und die Bitumkehr erfolgt manuell, anstatt vorhandene Bibliotheksfunktionen zu verwenden
Mark Jeronimus
@ MarkJeronimus: Können Sie eine effiziente FFT-Implementierung in Java empfehlen? Wenn ich mich richtig erinnere, war der Grund, warum ich mich für den Code der Columbia University entschieden habe, dass die FFTW-Bibliothek zu komplex war, um auf einem Android-Smartphone ausgeführt zu werden.
stackoverflowuser2010
Ich habe einige verstreute 'optimierte' Implementierungen gefunden, aber es handelt sich im Grunde genommen um einen Algorithmus pro N-Größe. Wenn Sie also einen Größenbereich benötigen, benötigen Sie alle diese Routinen. In der Praxis habe ich hauptsächlich Intel Integrated Performance Primitives verwendet (ja, von Java über JNA), aber das ist nicht kostenlos. Zu Hause verwende ich im Grunde den gleichen Algorithmus, den Sie verlinkt haben, der jedoch 2005 mit einem Lehrbuch von Grund auf neu geschrieben wurde. Es ist nur FFT (Fast Fourier Transform), nichts so "Fast", um den Namen "Fast FFT" zu rechtfertigen.
Mark Jeronimus

Antworten:

85
  1. Sie sollten weder nach dem realen noch nach dem imaginativen Teil einer komplexen Zahl suchen (das ist Ihr reales und imaginäres Array). Stattdessen möchten Sie nach der Größe der Frequenz suchen, die als sqrt (real * real + imag * imag) definiert ist. Diese Zahl wird immer positiv sein. Jetzt müssen Sie nur noch nach dem Maximalwert suchen (ignorieren Sie den ersten Eintrag in Ihrem Array. Dies ist Ihr DC-Offset und enthält keine frequenzabhängigen Informationen).

  2. Sie erhalten 32 reale und 32 imaginäre Ausgaben, da Sie eine komplexe bis komplexe FFT verwenden. Denken Sie daran, dass Sie Ihre 32 Samples in 64 Werte (oder 32 komplexe Werte) konvertiert haben, indem Sie sie mit null Imaginärteilen erweitert haben. Dies führt zu einer symetrischen FFT-Ausgabe, bei der das Frequenzergebnis zweimal auftritt. Einmal einsatzbereit in den Ausgängen 0 bis N / 2 und einmal gespiegelt in den Ausgängen N / 2 bis N. In Ihrem Fall ist es am einfachsten, die Ausgänge N / 2 bis N einfach zu ignorieren. Sie brauchen sie nicht, sie sind es Nur ein Artefakt darüber, wie Sie Ihre FFT berechnen.

  3. Die Frequenz-zu-Fft-Bin-Gleichung lautet (bin_id * freq / 2) / (N / 2), wobei freq Ihre Abtastfrequenz ist (auch bekannt als 32 Hz, und N die Größe Ihrer FFT). In Ihrem Fall vereinfacht sich dies auf 1 Hz pro Bin. Die Bins N / 2 bis N repräsentieren negative Frequenzen (seltsames Konzept, ich weiß). Für Ihren Fall enthalten sie keine signifikanten Informationen, da sie nur ein Spiegel der ersten N / 2-Frequenzen sind.

  4. Ihre Real- und Imaginärteile jedes Behälters bilden eine komplexe Zahl. Es ist in Ordnung, wenn Real- und Imaginärteile negativ sind, während die Größe der Frequenz selbst positiv ist (siehe meine Antwort auf Frage 1). Ich schlage vor, dass Sie sich über komplexe Zahlen informieren. Die Erklärung, wie sie funktionieren (und warum sie nützlich sind), geht über das hinaus, was in einer einzelnen Stackoverflow-Frage erklärt werden kann.

Hinweis: Möglicherweise möchten Sie auch nachlesen, was Autokorrelation ist und wie sie zum Ermitteln der Grundfrequenz eines Signals verwendet wird. Ich habe das Gefühl, dass Sie das wirklich wollen.

Nils Pipenbrinck
quelle
1
Vielen Dank. Zu 1: Ich habe diese Matlab-Seite gesehen, die ein Frequenzspektrum zeigt ( mathworks.com/help/techdoc/ref/fft.html ). Auf dieser Seite befindet sich eine Darstellung mit dem Titel "Einseitiges Amplitudenspektrum von y (t)". Zeichnet das die Größe der Frequenz, wie Sie vorgeschlagen haben, sqrt (real ^ 2 + img ^ 2)? Zu 3: Ich erhalte immer noch nicht das Ergebnis von 2 Hz pro Bin. In meinem Fall ist N = 32 und freq = 32, richtig? Es gibt also N / 2 = 32/2 = 16 Bins, und die höchste Frequenz (Nyquist) ist freq / 2 = 32/2 = 16 Hz, was zu 16 Hz pro 16 Bins führt, was 1 Hz pro Bin ergibt?
stackoverflowuser2010
1
Ja, das Diagramm zeigt die Größe des Spektrums - | Y (f) |. Die Absolutwertbalken bedeuten Größe. Behälterbreite = Abtastrate / FFT-Größe. Ihre Abtastrate beträgt 32 Hz, Ihre FFT-Größe beträgt 32. Ja, Sie haben Recht mit der Behälterbreite!
Matt Montag
Die Bin-Frequenz wurde korrigiert.
André Chalella
1
Schöne Antwort, danke! Es tut mir leid, dass ich etwas zu spät zur Party komme, aber vielleicht könnten Sie mir antworten, um welche Einheit die Größe der Frequenz (wie von Ihnen in Punkt 1 erwähnt) im Allgemeinen ist? In meinem Fall auf ein Signal von Werten von einem Beschleunigungsmesser (ist m / s ^ 2). Ich kann es nicht ganz herausfinden.
Markus Wüstenberg
Faszinierend! Meine Frequenzbalken für die Musikvisualisierung kamen alle von links nach rechts gespiegelt heraus; Antwort 2 erklärt dies !! Verrückt!!
Ryan S
11

Sie haben bereits einige gute Antworten, aber ich möchte nur hinzufügen, dass Sie vor der FFT wirklich eine Fensterfunktion auf Ihre Zeitbereichsdaten anwenden müssen , da Sie sonst aufgrund von Spektralleckagen böse Artefakte in Ihrem Spektrum erhalten .

Paul R.
quelle
Ich weiß zu schätzen, dass seit dieser Antwort ziemlich viel Zeit vergangen ist. Könnten Sie jedoch näher erläutern, welche Art von Artefakten Sie meinen?
MattHusz
1
@MattHusz: Der allgemeine Begriff für den Ursprung dieser Artefakte lautet "spektrale Leckage" - ich habe jetzt einen Link zur Antwort hinzugefügt, der dies erklärt. Der beste Weg, den Effekt zu beschreiben, ist jedoch, dass Ihr Spektrum aufgrund des impliziten rechteckigen Fensters „verschmiert“ wird.
Paul R
6

1) Suchen Sie nach den Indizes im realen Array mit den höchsten Werten neben dem ersten (das ist die DC-Komponente). Sie benötigen wahrscheinlich eine Abtastrate von deutlich mehr als 32 Hz und eine größere Fenstergröße, um aussagekräftige Ergebnisse zu erzielen.

2) Die zweite Hälfte beider Arrays ist der Spiegel der ersten Hälfte. Beachten Sie beispielsweise, dass das letzte Element des realen Arrays (1.774) mit dem zweiten Element (1.774) identisch ist und das letzte Element des imaginären Arrays (1.474) das Negativ des zweiten Elements ist.

3) Die maximale Frequenz, die Sie mit einer Abtastrate von 32 Hz aufnehmen können, beträgt 16 Hz ( Nyquist-Grenze ), sodass jeder Schritt 2 Hz beträgt. Wie bereits erwähnt, ist das erste Element 0 Hz (dh der Gleichstromversatz).

4) Sicher, eine negative Amplitude ist absolut sinnvoll. Es bedeutet nur, dass das Signal "gespiegelt" wird - eine Standard-FFT basiert auf einem Kosinus, der normalerweise bei t = 0 den Wert = 1 hat, sodass ein Signal mit dem Wert = -1 zum Zeitpunkt = 0 eine negative Amplitude haben würde .

Dämmerung -inaktiv-
quelle
Danke für die Antwort. (1) Meinen Sie damit, dass ich das imaginäre (Sinus-) Array ignorieren kann, und wenn ja, warum? Sicherlich muss die Sinuskomponente wichtig sein? (2) Warum tritt diese Spiegelung auf? Ist es nur das Ergebnis des FFT-Algorithmus? Ignorieren die meisten Leute die gespiegelte Hälfte? (3) Wie haben Sie die Schritte von 2 Hz berechnet? Ich verstehe die Nyquist-Grenze von 16 Hz. Wenn also 16 (nicht gespiegelte) Array-Elemente vorhanden sind, muss jedes Element 16 Hz / 16 = 1 Hz betragen. (4) Um Hauptfrequenzen zu finden, nehme ich einfach den Absolutwert der Amplitudenwerte in den Ausgangsarrays?
stackoverflowuser2010
Sie sollten nicht im realen Array nach dem höchsten Wert suchen und das Sinus / I-Array nicht ignorieren. Stattdessen möchten Sie die Größe des zusammengesetzten komplexen Vektors. Die Spiegelung erfolgt, weil die Hälfte der Eingabe (das I-Array) aus Nullen besteht, sodass das Ergebnis die Hälfte der Freiheitsgrade aufweist. Sie können es ignorieren, wenn Ihre Daten streng echt sind.
hotpaw2
@duskwuff Vielen Dank: Sie haben eine Antwort auf eine Frage gegeben, die ich posten wollte, wenn ich Ihre Antwort nicht gefunden hätte: Wie interpretiere ich den ZWEITEN Teil der FFT? Ich möchte die Daten ändern und die Umkehrung durchführen, und ich habe immer nur die Hälfte der Ergebnisse erhalten, weil ich die falschen Daten in diesem Teil geändert habe. Danke noch einmal.
Martin
(3), der Wert von Schritt = 2 Hz bleibt mir bisher implizit. Wir haben 16 Fächer, dargestellt durch ein Array von Länge = 16. Wir müssen alle Frequenzen von 0 Hz bis 16 Hz beschreiben. Ich nehme an, jeder Behälter beschreibt ein Stück dieses Bereichs, nicht wahr?
Krafter
@krafter Ich denke, es ist halbiert, weil man eine Frequenz nicht aus einem einzelnen Wert ableiten kann (da es keine Wiederholung gibt).
JVE999
5

Beachten Sie, dass die "am häufigsten auftretende Frequenz" auch mit einer Fensterfunktion in mehrere FFT-Bins gespritzt werden kann. Daher müssen Sie möglicherweise ein längeres Fenster, mehrere Fenster oder eine Interpolation verwenden, um die Frequenz von Spektralspitzen besser abschätzen zu können.

hotpaw2
quelle