Hallo, wollte mich mal mit dem Gebiet DFT/FFT vertraut machen, und das ganze mal in C# programmieren, zuerst die DFT da sie ja etwas einfacher ist. Den mathematischen Algorithmus habe ich soweit verstanden, aber wie baue ich mir z.B. ne komplexe e-funktion in C??! Aufspalten in sin und cos ginge zwar auch, aber ich glaube diese ganzen trigonometrischen Funktionen benutzt man nicht beim Programmieren? (zumindest bei uC sind sie wohl sehr unbeliebt).
So richtig verstanden hast du das ganze wohl doch noch nicht... Ist aber auch kein leichtes Thema!! Du brauchst keine complexe e-Funktion. Was sind denn complexe Zahlen? In kartesischen Koordinaten gibt es einen Real und einen Imaginärteil und in Polarkoordinaten (deine complexe e-Funktion) einen Betrag und eine Phase. Ergo: Du arbeitest eigentlich immer nur mit zweier Vektoren. Bei der DFT multiplizierst du nacheinander die Abtastwerte mit einem e^jx und summierst diese dann auf. Das ist aber gleichbedeutend mit einer Phasenänderung. Oder anders ausgedrückt:
Wenn man genau hinschaut sieht man in der Formel für die DFT, dass dort 360° in gleichgroße Teile aufgeteilt werden und dann die Abtastwerte immer um ein Vielfaches dieses Teilphasenwinkels verschoben werden. Anschließend noch die Summe drüber und fertig. Die FFT benutzt eine geschickte mathematische Umformung, die das ganze in eine Rekursion überführt (Zerlegung des Zeitsignals in mehrere Signalpakete). Hat dann die Rekursion die maximale Tiefe erreicht wird praktisch nur noch ein Abtastwert transformiert. Und dessen Transformierte ist der Abtastwert selbst. Anschließend wird das ganze wieder zusammengesetzt und fertig ist die FFT. Das ganze Thema ist recht komplex und ich bin auch schon ein wenig raus. (Habe mein Diplom im Bereich Sprachsignalverarbeitung gemacht) Empfehlen kann ich dir das Buch "Fourier-Transformation für Fussgänger". Dort ist alles sehr anschaulich erklärt und hergeleitet.
Die allgemeine Formel für die DFT lautet ja:
Dies kann man auch als Matrix-Vektor-Multiplikation schreiben:
wobei sich die Elemente der Matrix zu
ergeben. Wenn man sich jetzt noch daran erinnert das
ist kann man das Problem einfach lösen. Zur Realisierung: entweder man verwendet eine Matrix mit dem Datentyp complex, oder man bildet zwei separate Matrizen für den Real- und Imaginäranteil. Bei dieser Variante kann man den Real- und Imaginäranteil so auch getrennt berechnen.
> Wenn man genau hinschaut sieht man in der Formel für die DFT, dass dort > 360° in gleichgroße Teile aufgeteilt werden und dann die Abtastwerte > immer um ein Vielfaches dieses Teilphasenwinkels verschoben werden. > Anschließend noch die Summe drüber und fertig. Die Idee ist eher mit einer normierten Frequenz zu arbeiten da abgetastete Signale ein mit der Abtastfrequenz fortgesetztes Spektrum haben. Deshalb bildet man für die zDFT den Bereich von 0 bis fT auf die normierten Frequenzen 0..2*pi ab. Für die DFT diskretisiert man das Spektrum noch auf N Werte. > > Die FFT benutzt eine geschickte mathematische Umformung, die das ganze > in eine Rekursion überführt (Zerlegung des Zeitsignals in mehrere > Signalpakete). Hat dann die Rekursion die maximale Tiefe erreicht wird > praktisch nur noch ein Abtastwert transformiert. Die FFT stellt eigentlich eine Teilbandcodierung [Noll, "Digital Coding of Waveforms" etc.] dar. Es müssen log_2(N) Zerlegungen in Hoch/Tiefpaßanteile durchgeführt werden, die dann jeweils 1:2 unterabgetastet werden können. Für jede Zerlegung sind N komplexe Multiplikationen nötig, so daß der Aufwand nur N*log_2(N) ist.
>Empfehlen kann ich dir das Buch "Fourier-Transformation für Fussgänger".
Fußgänger statt Dummies... hab mal bei Amazon geschaut, da gibts vier
Ausgaben
(Broschiert - April 2007) ISBN-10: 3835101358 ISBN-13: 978-3835101357
(Broschiert - Oktober 2005)
(Gebundene Ausgabe - März 2007)
(Taschenbuch - Oktober 2003)
mir wäre ein Buch mit Programmierbeispielen lieber, das scheint eher ein
Lehrbuch zu sein
Bitte 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.