DFT implementieren

[hase (Gast)]

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).

[Mandrake (Gast)]

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:

$$(a(k) + jb(k)) \cdot e^{j\xi} = |(a(k)+jb(k))| \cdot e^{j(\xi+atan(b(k)/ a(k))}$$

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.

[Rüdiger K. (sleipnir)]

Die allgemeine Formel für die DFT lautet ja:

$$U(jk\Delta\Omega) = \sum\limits^{N-1}_{n=0} u[n]\cdot e^{-jkn\frac{2\pi}{N}}$$

Dies kann man auch als Matrix-Vektor-Multiplikation schreiben:

$$\mathbf{U}=\mathbf{T}_{DFT}\cdot\mathbf{u}$$

wobei sich die Elemente der Matrix zu

$$\mathbf{T}_{DFT}(k,n) = e^{-jkn\frac{2\pi}{N}}$$

ergeben. Wenn man sich jetzt noch daran erinnert das

$$e^{-jkn\frac{2\pi}{N}} = \cos\left(jkn\frac{2\pi}{N}\right)-i\cdot\sin\left(jkn\frac{2\pi}{N}\right)$$

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.

[Rüdiger K. (sleipnir)]

> 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.

[hase (Gast)]

Danke Leute, alle Unklarheiten beseitigt (hoffe ich doch) :D

[Christoph db1uq K. (christoph_kessler)]

>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