moin, ich habe nun meinen 1. FFT-algorithmus fertig und würde gerne überprüfen, ob er richtig arbeitet. Wie kann ich dies am schnellsten überprüfen? Was wären geeignete Input-Daten, um die Richtigkeit zu verifizieren? Ist ein 64er-Feld. mfg
:
Verschoben durch Admin
FFT schrieb: > moin, > > ich habe nun meinen 1. FFT-algorithmus fertig und würde gerne > überprüfen, ob er richtig arbeitet. > > Wie kann ich dies am schnellsten überprüfen? > > Was wären geeignete Input-Daten, um die Richtigkeit zu verifizieren? > > > Ist ein 64er-Feld. > > > mfg Vorschlag: eine IFFT durchführen.
FFT schrieb: > Was wären geeignete Input-Daten, um die Richtigkeit zu verifizieren? Rechtecksignal: 32 mal 1 und 32 mal -1 (oder 0). Statt 1 u. -1 deiner Realisierung mit float oder integer entsprechend andere Werte ( 10000 -10000) verwenden. Die FFT-Antwort zu einem Rechteck am besten bei google suchen.
Angehängte Dateien:
-
f_und_fft.png
13 KB
Also: Ich habe als Input jetzt mal die Funktion: 25*Cos(2pift)+300 mit f=1,1hz und 64 Abtastpunkten gewählt. Die Abtastpunkte sind: 325 319 305 288 277 276 287 303 318 325 320 306 289 277 276 285 302 317 325 321 308 291 278 275 284 300 316 325 322 309 292 279 275 283 298 315 324 323 311 294 280 275 282 297 313 324 323 312 295 281 275 281 295 312 323 324 313 297 282 275 280 294 311 323 Das FFT-Ergebnis ist 464 2290 79 223 45 211 233 47 52 136 117 138 316 142 175 67 53 192 234 63 63 102 234 223 901 249 56 166 778 264 393 198 463 747 149 145 51 120 178 85 37 90 78 127 445 224 403 219 2756 384 119 93 32 112 244 208 901 213 91 125 445 163 244 124 Eine Fensterfunktion habe ich nicht genutzt. Ihr habt doch allesamt ebenfalls FFT-Algorithmen in den Schubladen. Vielleicht mag also einer mal meine Daten zur Verifikation nachrechnen.
Die Idee hinter der Testfunktion (sin und cos) war eine andere. Bei einer Fouriertransformierten eines Sinus (ungerade Funktion) ist der Realteil Null und der Imaginärteil enthält das entsprechende Amplitudensignal auf der Frequenz des Sinus. Beim Cosinus (gerade Funktion) ist es genau umgekehrt, der Imaginärteil ist Null und der Realteil enthält die Amplitude. Mache also folgenden Versuch. Testsignal ist ein Sinus oder ein Cosinus mit EINER vollen Periode (keine Fensterung nötig, kein Leakage). Dann führst du die FFT durch und schaust dir das Ergebnis nach den obigen Kriterien an.
FFT schrieb: > Ihr habt doch allesamt ebenfalls FFT-Algorithmen in den Schubladen. > Vielleicht mag also einer mal meine Daten zur Verifikation nachrechnen. Etwas eigene Arbeit solltest du schon aufwenden. Mit dem Nachrechnen ist es auch nicht so einfach, solange du uns nichts genaueres über die Organisation deiner Daten für Ei- und Ausgang angibst: Real Imaginärteil? Integer16 oder 32 bit signed unsigned oder float ....
Nachtrag zu deinen Ergebnissen. Die Länge deines Datensatzes im Frequenzbereich (also Realteil oder Imaginärteil oder Betrag) darf nur die Hälfte der Abtastpunkte lang sein (32). Es muß genau zwei Peaks geben (einen Gleichanteil, einen auf der Signalfrequenz). Im Anhang das korrekte Ergebnis.
Eine marginale Ahnung der fouriertransformation und der FFT im speziellen sollte man schon haben. Denn wenn man einfach irgendwas macht, macht man's haeufig falsch.
FFT schrieb: > Also: > > Ich habe als Input jetzt mal die Funktion: > > 25*Cos(2pift)+300 mit f=1,1hz und 64 Abtastpunkten gewählt. Machs nicht so kompliziert. Bei den ersten Tests (egal was), ist es immer so, dass man das korrekte Ergebnis schon im Vorfeld kennt, noch ehe der Code das erste mal läuft.
http://www.random-science-tools.com/maths/FFT.htm vielleicht hilft das, um deine Werte zu verifizieren.
danke allen, ich komme der Sache langsam auf die Spur, bei der Ergebnisinterpration habe ich aber doch noch ein paar Schwierigkeiten: @Joe: Du schreibst, dass nur die Hälfte der Datenpunkte in der Frequenz ausgewertet werden. Wie muss ich denn nun meine Achse skalieren? im obigen Bild habe ich ja erstmal alle 64 Punkte mit reingenommen. Wie müsste ich nun einen x-Wert bezeichnen? Ist ein x-wert nun 0,15625Hz oder ist ein x-Wert 0,078125Hz, was der Ferquenzauflösung delta_f bzw. der halben Frequenzauflösung delta_f/2 entspräche... Reichen meine X von 0 bis 9,9Hz oder von 0 bis 5Hz Vielleicht noch etwas konkreter gefragt: Was genau liegt in welchem "Frequenzfach" Als Beispiel: Was würde in Fach 0 liegen, was liegt in Fach 30, 31, 32 was liegt in Fach 63. Ich habe ja nun eine ganze Menge Literatur zur FFT verschlungen, aber in keinem vorgestellten Algorithmus wird nach der Hälfte der Berechnung abgebrochen... Ich kann mir also nicht vorstellen, dass ich die Frequenzwerte "der zweiten Hälfte" einfach wegschmeißen könnte...
Joe G. schrieb: > Die Länge deines Datensatzes im Frequenzbereich (also Realteil oder > Imaginärteil oder Betrag)... Also nochmals ganz von vorne; Dein Datensatz im Zeitbereich beinhaltet N Werte einer Zeitfunktion y(t)=f(t). Ist N ein Vielfaches einer Zweierpotenz, so kann statt der Fouriertransformation ein vereinfachter Algorithmus verwendet werden. Diesen nennt man dann FFT. Das Ergebnis der FFT ist eine Funktion im Frequenzbereich Y(s)=f(s). Aufgrund der speziellen Transformationseigenschaften der Fouriertransformation ist das Ergebnis der FFT im allgemeinen eine komplexe Zahl bestehend aus einem Realteil Re(Y) und einem Imaginärteil Im(Y). Jede dieser beiden Funktionen beinhaltet somit nur noch N/2 Werte. Wenn du das Ergebnis nun darstellt, so kann es also nur noch N/2 Werte beinhalten. In deinem konkreten Beispiel also y(t) hat 64 Werte dann ist Y(s) komplex und hat 32 Werte für den Realteil und 32 Werte für den Imaginärteil. Selbstverständlich kannst du Re und Im auch in Betrag und Phase umrechnen. Dann hat der Betrag 32 Werte und die Phase 32 Werte.
Das ist doch nicht richtig was du da schreibst... Die FFT geht doch auf die Butterfly-Operation zurück, also die paarweise Verknüpfung von jeweils zwei Abtastwerten. Wenn ich nun eine derartige 2er FFT bilde, also nur eine einzige Butterfly-Operation durchführe, dann habe ich F(0) = x(0) + x(1) F(1) = x(0) - x(1) und dies ist unverkennbar für beide Werte rein reell. Wenn ich größere FFTs berechne, erhalte ich z.B. bei der 8er FFT in der letzten Stufe die Twiddle-Faktoren: 0,5*sqrt(2)*(+/- 1 +/-j), d.h. die araus gewonnenen Werte sind ebenfalls komplex, sprich in den Frequenzfächern stehen Zahlen, die einen Realteil ungleich Null UND einen Imaginärteil ungleich Null aufweisen...
FFT schrieb: > beide Werte rein reell. > > > Wenn ich größere FFTs berechne, erhalte ich z.B. bei der 8er FFT in der > letzten Stufe die Twiddle-Faktoren: > 0,5*sqrt(2)*(+/- 1 +/-j), d.h. die araus gewonnenen Werte sind ebenfalls > komplex, Was denn nun? Behauptest Du nun, dass Du Komplexe Zahlen als Ergebnis bekommen solltest, oder das Gegenteil? Hier ist übrigens die (ernstgemeinte) Antwort auf Deine ursprüngliche Frage : Du vergleichst Deine Ergebnisse mit de von Dir (vorher) implementierten (nicht fast-) DFT.
Nein, ich behaupte, dass Joe G.s Antwort nicht richtig sein kann, weil bei eine N-Punkt FFT eben bis zu N komplexe Werte rauskommen - nicht N/2 Werte. Folglich ist der Ergebnisvektor eben nicht N/2 lang, sondern N lang. Und nicht nur das, er nimmt sogar 2xN Speicherplatz in Anspruch, weil in jedem Fach eben ein Realteil und ein Imaginärteil drin steckt udn wohl auch stecken muss. Das Problem scheint Joe G aber noch garnicht aufgefallen zu sein, da er offenbar nur fertige Algorithmen aus einer Bibliothek verwendet und sich über die Ergebnisinterpretation bisher keinerlei Gedanken gemacht hat... ...aber versteht mich nicht falsch: Ich bin über jede Hilfe dankbar, außer sie ist erkennbar falsch und geschieht darüber hinaus in einem nicht angebrachten Kindergarten-Erklärton, womit der eigentlichen Frage der Ergebnisinterpretation in keiner Weise geholfen wird... @Joe G. Nimms bitte nicht persönlich. Der von dir gezeigte Plot ist leider erkennbar aus einer FFT-Routine die mehr macht, als nur N Eingangswerte zu verarbeiten und ist für meine Fragestellung nicht zielführend. @dadada: Ich habe hier nur einen Mikrocontroller zur Verfügung. Der Speicher ist so begrenzt, dass eine "richtige" DFT von vornherein nicht in Frage kommt. Dort müsste ich jede Ebene komplett speichern, weil das Ergebnis jeder Zeile alle vorherigen Ergebnisse mit benötigt. Bei einer FFT hingegen müssen nur zwei Ebenen zeitgleich im Speicher vorgehalten werden und können danach überschrieben werden. Schön wäre es daher, wenn jemand einen 64-Testvektor (irgendeine Cos-Funktion) bereitstellen würde und die zugehörige FFT Ausgabe gleich mit. Es würde mir schon genügen, wenn ich anhand dieser Vergleiche prüfen könnte, ob ich zumindest eine richtige Implementierung vorgenommen habe. mfg
Ich würde das einfach mit einem tool vergleichen, Octave, Matlab oder so. Excel hat eine integrierte FFT.
Hallo, die Idee einer Testfunktion zum Überprüfen ist ja gerade, das man das Ergebnis vorher kennt. Dafür bieten sich neben "passen vollständigen" Perioden von Sinus und Kosinus z.B. auch eine konstante Funktion an. Wie die Sortierung des Ergebnis aussieht hängt von der Implementierung ab, von daher musst du schon selbst wissen, an welche Stelle du was schreibst. Hierbei gilt aber allgemein, das die Anzahl der Eingangspunkt auch gleich der Anzahl der Ausgangspunkte ist. Wenn du jetzt allerdings 64 reelle Werte als Eingang hast nimmst du die anderen 64 imaginären Werte mit Null an und kannst damit dann 128 Werte als Ausgang erhalten, diese lassen sich aber durch die Symmetrie (Eingang nur reell) wieder auf 64 Werte reduzieren. Solche Darstellungen werden gerne als Halbkomplex bezeichnet. Ein Buch, was das ganze sehr gut verständlich erklärt (mit den ganzen Dingen wir Umklappen und co) heißt "Fouriertransformation für Fußgänger" von Tilman Butz Darin sind auch jede Menge Beispiele, die von Hand durchgerechnet werden, um das ganze zu Veranschaulichen. Gruß Kai
FFT schrieb: > Nein, ich behaupte, dass Joe G.s Antwort nicht richtig sein kann, weil > bei eine N-Punkt FFT eben bis zu N komplexe Werte rauskommen - nicht N/2 > Werte. Wie bei der Fourier-Transformation gelten auch für die DFT gewisse Symmetriegesetze. So wird ein reelles Signal im Zeibereich zu einem hermiteschen Signal im Frequenzbereich. Das bedeutet, dass im Frequenzraum nur N/2 unabhängige komplexe Koeffizienten vorliegen. Diese Tatsache kann bei der Implementierung der DFT ausgenutzt werden, wenn bekannt ist, dass das Eingangssignal rein reell ist. Für die Darstellung des Ergebnisses sind dann keine N (wie bei der vollen DFT), sondern nur N/2 komplexe Zahlen nötig. Die anderen N/2 komplexen Zahlen können durch elementare Rechnung rekonstruiert werden. FFT schrieb: > Nimms bitte nicht persönlich. Ach warum denn? Der Plot stammt ja auch nicht aus einer fertigen FFT Routine sondern den habe ich mit der Summenformel der DFT in Mathcad erzeugt :-)
FFT schrieb: > Ich habe hier nur einen Mikrocontroller zur Verfügung. Und der ist nicht an einem PC angeschlossen? Womit sendest Du Deine Beitraege ab?
Hallo Ich glaube, ihr überseht einen Aspekt: die Zeile mit dem * hier (der logik halber die ganze Überlegung -Für eine FFT muss man 2^n Samples haben - Die Resultatswerte einer FFT von realen sample-werten sind imaginär - Die höchste Grenzfrequenz, die bei FFT rauskommt, ist die halbe Abtastfrequenz - Das Resultat des Ergebnisvektors besteht aus n Elementen (!) * Das Resultat stellt eine symmetrische Reihe dar: in der Mitte ist der DC-Anteil (=Frequenz null) und rechts und links davon je die erste Frequenz mit 1/T, dicht daneben folgen die beiden -1/2T und 1/2T usw.. bis 1/((n/2)-1)T. wobei T die Abtastzeit war. JAHWOHL!!! FFT generiert negative Frequenzkomponenten. Da diese symmetrisch zu den Positiven sind, können wir die negativen wegschmeissen und rechnen mit den Werten DC, 1/T, 1/2T, 1/3T...bis 1/(n_halbe-1)T. Anmerkung: Genau dasselbe machen wir ja auch in der Nachrichtentechnik. Schon mal etwas von SSB gehöhrt?
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.