DFT implementieren

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.

> 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