Diskrete Fourier-Transformation
Die Diskrete Fourier-Transformation oder DFT ist ein Algorithmus, mit dessen Hilfe die Fourier-Transformierte eines diskretisierten (abgetasteten) Signals berechnet werden kann.
Da das Signal abgetastet ist, ist das entstehende Spektrum periodisch mit der Abtastfrequenz. (Vereinfachung: z-Transformation, da dort nur eine Periode beschrieben wird, da dies bei periodischen Funktionen ausreicht)
Ein weiteres Problem stellt das Abtasttheorem (sampling-theorem) dar. Die Bedingung die es vorgibt muss eingehalten werden. d.h. die Abtastfrequenz muss mindestens doppelt so groß sein wie die Bandbreite des Signals. Für Signale im Basisband muss daher gelten, dass die Abtastfrequenz doppel so groß sein muss, wie die maximal auftretende Frequenz. Bei Verletzung des Abtasttheorems tritt eine Verfälschung des Originalsignals auf (Aliasing im Zeitbereich). -> Anti-Aliasing-Filter (Bandbegrenzung des Signals) am Eingang des Systems, um diesen Effekt zu vermeiden.
Da der Algorithmus zur Berechnung der DFT sehr viel Redundanz enthält, verwendet man in der Praxis einen vereinfachten Algorithmus, die FFT (Fast Fourier Transform), der lediglich eine Redundanzreduktion jedoch keinen Genauigkeitsverlst bedeutet. Die FFT ist KEINE EIGENE Transformation!
Die DFT benötigt 2^n komplexe Rechenoperationen um die Transformation von n Abtastwerten zu berechnen.
Die FFT benötigt hingegen nur n*ld(n) (ld ... Logarithmus dualis ld(x)=ln(x)/ln(2)) komplexe Rechenoperationen. Diese Reduktion erreicht man durch Dezimierung in der Zeit (decimation in time). Dabei werden die zeitlich "geraden und ungeraden" Abtastwerte jeweils getrennt verarbeitet.
Wenn man die Rechenoperationen die zur Ausführung der FFT nötig sind, graphisch darstellt, so entstehen Schmetterling-ähnliche Figuren (Butterfly-Graph).
weitere auftretende Effekte
"Nebenzipfeleffekt"
(en: side-lobe effect)
===Anwendungen===:
Berechnung der Fourier-Transformierten eines Signals.
Analyse von Signalen.
Bearbeitung von Signalen.
Bei der Berechnung von Oberflächenwellenfiltern (= OFW-Filter = SAW-filter = surface acoustic wave - filter) wird die invers - Fouriertransformierte der Übertragungsfunktion benötigt (stellt die Impulsantwort dar). Diese Aufgabe wird von Rechnern übernommen.
Berechnung von Korrellationen.