www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP DFT implementieren


Autor: hase (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Mandrake (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: hase (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke Leute, alle Unklarheiten beseitigt (hoffe ich doch) :D

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.