Die Diskrete Fourier-Transformation (DFT) ist eine Transformation aus dem Bereich der Fourier-Analysis.Tilman Butz: Fouriertransformation für Fußgänger. 7. Auflage. Vieweg+Teubner Verlag, Wiesbaden 2011, ISBN 978-3-8348-0946-9, Kapitel 4.M. W. Wong: Discrete Fourier Analysis. Birkhäuser Verlag, Basel 2011, ISBN 978-3-0348-0115-7. Sie bildet ein zeitdiskretes endliches Signal, das periodisch fortgesetzt wird, auf ein diskretes, periodisches Frequenzspektrum ab, das auch als Bildbereich bezeichnet wird. Die DFT besitzt in der digitalen Signalverarbeitung zur Signalanalyse große Bedeutung. Hier werden optimierte Varianten in Form der schnellen Fourier-Transformation (, FFT) und ihrer Inversen angewandt.
Die DFT wird in der Signalverarbeitung für viele Aufgaben verwendet, so z. B. zur Bestimmung der in einem abgetasteten Signal hauptsächlich vorkommenden Frequenzen, zur Bestimmung der Amplituden und der zugehörigen Phasenlage zu diesen Frequenzen, zur Implementierung digitaler Filter mit großen Filterlängen.
Mit der inversen DFT, kurz iDFT kann aus den Frequenzanteilen das Signal im Zeitbereich rekonstruiert werden. Durch Kopplung von DFT und iDFT kann ein Signal im Frequenzbereich manipuliert werden, wie es beim Equalizer angewandt wird. Die Diskrete Fourier-Transformation ist von der verwandten Fouriertransformation für zeitdiskrete Signale (englisch DTFT) zu unterscheiden, die aus zeitdiskreten Signalen ein kontinuierliches Frequenzspektrum bildet.
Definition Diskrete Fourier-Transformation (DFT) Die diskrete Fourier-Transformation verarbeitet eine Folge von Zahlen , die zum Beispiel als zeitdiskrete Messwerte entstanden sind. Dabei wird angenommen, dass diese Messwerte einer Periode eines periodischen Signals entsprechen. Die DFT gilt auch für den Fall, dass eine Folge von komplexen Zahlen ist, also:
Das Ergebnis der Transformation ist eine Zerlegung der Folge in harmonische (sinusförmige) Anteile, sowie einen „Gleichanteil“ , der dem Mittelwert der Eingangsfolge entspricht. Das Ergebnis nennt man „diskrete Fourier-Transformierte“ von . Die Koeffizienten von sind die Amplituden der Zerlegungsanteile. Man nennt auch Fourierkoeffizienten oder Fourierkomponenten.
Üblicherweise wird bei der Bestimmung der Frequenzanteile/Phasenlage die kompakte mathematische Schreibweise der Polarform verwendet (Eulersche Formel):
Die Fourierkoeffizienten werden damit aus der Eingangsfolge berechnet durch:
{| class="wikitable" ! für
Die Gleichung kann auch als Matrix-Vektor-Produkt geschrieben werden:
{| class="wikitable" ! mit
Die symmetrische Transformationsmatrix mit der Dimension wird „Fourier-Matrix“ genannt.
Inverse Diskrete Fourier-Transformation (iDFT) Die Summe der sinusförmigen Zerlegungsanteile ergibt wiederum die ursprüngliche Eingangsfolge .
Dafür wird das Transformationsergebnis als Koeffizienten eines Polynoms verwendet, wobei die Amplituden von den zugehörigen harmonischen Schwingungen darstellen.
Die Argumente sind gleich verteilte Punkte auf dem Einheitskreis der komplexen Zahlenebene, d. h. die –ten Einheitswurzeln
Aus dieser Erklärung wird nebenbei auch der Zusammenhang zwischen der diskreten Fourier-Transformation und der z-Transformation ersichtlich. Der Unterschied besteht im Wesentlichen darin, dass die z-Transformation nicht auf den Einheitskreis beschränkt ist und dadurch auch zeitlich dynamische Vorgänge abbilden kann.
Die Koeffizienten der ursprünglichen Folge lassen sich mit der iDFT aus den Fourierkoeffizienten bestimmen: {| class="wikitable" ! für
In der Schreibweise als Matrix-Vektor-Produkt:
{| class="wikitable" ! mit
wobei hier mit der inversen Matrix von multipliziert wird.
Bestimmung einer zeitkontinuierlichen periodischen Funktion basierend auf der Eingangsfolge Aus der inversen diskreten Fourier-Transformation lässt sich auch eine zeitkontinuierliche Funktion bestimmen, die durch die zeitdiskreten Messwerte (die Eingangsfolge) führt:
Dazu wird das Polynom mit einer gleichmäßig den Einheitskreis umlaufenden Funktion verknüpft. So ergibt sich eine zeitkontinuierliche periodische Funktion
die zu den Zeiten gerade die Funktionswerte annimmt.
Die Potenzen von haben die Gestalt
und daher die Periode und die Frequenz bzw. die Kreisfrequenz . Somit ist die Folge der Messwerte durch die Superposition eines konstanten Pegels bei , einer Grundschwingung bei und Oberschwingungen bei dargestellt und interpoliert worden.
Diese oben angegebene Interpolationsfunktion ist nicht die einzige, die sich auf diese Art konstruieren lässt. Jede der Funktionen
hat diese Interpolationseigenschaft.
Sonderfall: DFT für einen reellen Vektor Wie bei der Fourier-Transformation gelten auch für die DFT gewisse Symmetriegesetze. So wird ein reelles Signal im Zeitraum zu einem hermiteschen Signal () im Frequenzraum:
Dies bedeutet, dass im Frequenzraum nur unabhängige komplexe Koeffizienten vorliegen. Diese Tatsache kann bei der Implementierung der DFT ausgenutzt werden, wenn bekannt ist, dass das Eingangssignal rein reell ist. Für die Darstellung des Ergebnisses sind dann keine (wie bei der vollen DFT), sondern nur komplexe Zahlen nötig. Die anderen komplexen Zahlen können durch elementare Rechnung rekonstruiert werden (siehe Formel oben). Die hermitesche Symmetrie bezieht sich auf das mittlere Element des Signals .
Beweis: Wegen der Eulerschen Identität und wegen gilt im reellen Fall :
Umgekehrt gilt entsprechend: Erfüllt die Bedingung für alle sowie , so ist die inverse DFT ein reeller Vektor .
Verallgemeinerung: Mathematische Definition der DFT In der Mathematik wird die diskrete Fouriertransformation in einem sehr allgemeinen Kontext betrachtet. Sie findet unter anderem in der Computeralgebra bei einer Vielzahl von effizienten Algorithmen zur exakten Arithmetik Anwendung, so zum Beispiel bei der schnellen Multiplikation ganzer Zahlen mit dem Schönhage-Strassen-Algorithmus.
Sei ein kommutativer unitärer Ring, in dem die Zahl (das ist die -fache Summe der ) eine Einheit ist. Des Weiteren gebe es in eine primitive -te Einheitswurzel . Zu einem Tupel ist dann die diskrete Fouriertransformierte durch für erklärt. Unter den getroffenen Voraussetzungen existiert damit zu auch die diskrete inverse Fouriertransformierte mit den Koeffizienten für .
Im überaus wichtigen Spezialfall wird für die DFT üblicherweise die -te Einheitswurzel benutzt. Dies ergibt die Formel im ersten Abschnitt.
Mehrdimensionale DFT Die DFT kann leicht auf mehrdimensionale Signale erweitert werden. Sie wird dann je einmal auf alle Koordinatenrichtungen angewendet. Im wichtigen Spezialfall von zwei Dimensionen (Bildverarbeitung) gilt etwa: für und
Die Rücktransformation lautet entsprechend: für und
Verschiebung und Skalierung in Zeit und Frequenz In den Berechnungsformeln von DFT und iDFT kann die Summation (Indexvariable oben) statt über ebenso über einen verschobenen Bereich laufen, wenn der Vektor periodisch auf alle ganzzahligen Indizes fortgesetzt wird, denn es gilt . Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge in den ganzen Zahlen überstrichen wird.
Wenden wir uns nun wieder dem komplexen Fall zu. In praktischen Anwendungen möchte man die Indizes mit einer äquidistanten Folge von Zeitpunkten verbinden, für , die ebenfalls die Länge hat. Auch ist es wünschenswert, den berechneten Koeffizienten Frequenzen zuzuordnen, die um zentriert sind, für und in der Nähe von .
Eine zu den gewählten Zeitpunkten „gemessene“ Funktion ergibt den Beobachtungsvektor mit den Koeffizienten , dessen DFT in der Fourier-Analyse betrachtet wird. Dann ist
und .
Beispiele Die Fourier-Transformation transformiert eine Funktion nach von einer Zeitdarstellung in den reziproken Frequenzraum . Dies gilt auch für Ortsfunktionen, die auf ein (1D), zwei (2D) oder mehr Raumrichtungen definiert sind. Diese werden durch die Fouriertransformation, nacheinander in jeder Richtung, in Raumfrequenzen überführt. Beugungserscheinungen in der Optik oder Röntgenanalyse können unmittelbar als die Intensitätsverteilung einer Fouriertransformierten interpretiert werden. Die Phasenbeziehung geht bei der Fotografie normalerweise verloren. Lediglich bei der Holografie wird die Phasenbeziehung durch eine Überlagerung mit einem Referenzstrahl mit aufgezeichnet.
Einfache Blenden mini|Berechnete 2D Fourier-Transformationen. Links Ausgangsbild, rechts Intensitätsverteilung der Fourier-Transformation. mini|Berechnete 2D Fourier-Transformationen. Links Ausgangsbild, rechts Intensitätsverteilung der Fourier-Transformation.
Die Bilder rechts veranschaulichen zweidimensionale Fourier-Transformationen (2D FFT) an geometrischen Mustern, gerechnet für Quadrate der diskreten Größe von Pixeln. Das Bild oben links zeigt einen Spalt der Größe Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable wird überführt in reziproke komplexe Werte . Bei den gewählten Größen wird ein Pixel auf den reziproken Wert von reziproken Pixeln überführt. Die Breite des Spalts von Pixeln erscheint im Reziprokraum als Wert der Größe , die Höhe , mit harmonischen Frequenzen höherer Ordnung. Die berechneten Beugungsbilder geben die Intensitätsverteilungen der komplexen Größe wieder. Dass sie nur die Hälfte der Bildinformation tragen, erkennt man an ihrer Rotationssymmetrie.
Die periodischen Peaks entsprechen den Ortsfrequenzen höherer Ordnung eines Rechtecksignals. Ähnliche Beispiele finden sich unter den Stichworten Fourier-Analyse, Fourier-Transformation oder Beugungsscheibchen.
Im zweiten Teilbild wird ein regelmäßiges Sechseck gebeugt. Wieder erscheint die Größe der Figur als Periode im Beugungsbild rechts. Die 6-zählige Symmetrie ist deutlich zu erkennen. Eine Verschiebung des Ausgangsbildes – im Gegensatz zu einer Drehung – würde sich nur in der Phasenbeziehung auswirken, die in der gewählten Darstellung als Intensitätsverteilung nicht zu erkennen ist.
Das untere Teilbild zeigt rechts das berechnete Beugungsmuster eines Dreiecks. Die 6-zählige Symmetrie ist nur vorgetäuscht, was an der fehlenden Modulation der Beugungssterne zu erkennen ist.
Die zweite Bildserie vergleicht die Beugung zweier Kreisöffnungen. Ein großer Kreis erzeugt ein kleines Beugungsmuster, und umgekehrt. Bei einem Fernrohr begrenzt die Lichtbeugung an der Linsenöffnung die Auflösung. Je größer der Durchmesser ist, desto kleiner ist das Beugungsbild eines Sterns, desto besser können nahe beieinander liegende Sterne voneinander unterschieden werden.
Das untere Bild ist ein Beispiel für eine Beugung an einer Kreisstruktur ohne scharfe Begrenzung. Bei einer sinusförmigen Intensitätsabnahme am Rad treten keine Beugungen höherer Ordnung auf (siehe auch Zonenplatte).
Bild mit periodischen Strukturen mini|links|SAR-Bild des Indischen Ozeans mini|FFT des SAR-Bildes
Die Aufnahme links zeigt eine SAR-Aufnahme des Indischen Ozeans mit Wasserwellen unterschiedlicher Wellenlänge. Die internen Wellen oben rechts haben eine Wellenlänge von ca. 500 m. Die durch Wind erzeugten Oberflächenwellen sind in der verkleinerten Darstellung nicht erkennbar. Im gerechneten Beugungsbild geben die beiden dunklen Reflexe (siehe kurzer Pfeil) sowohl die Richtung als auch die mittlere Wellenlänge der regelmäßigen langperiodischen Wasserwellen an. Die Wellenlängen der Oberflächenwellen variieren stärker, weshalb sie keine scharfen Reflexe liefern. Es liegen zwei ausgezeichnete Richtungen für die Wellenausbreitung vor, die im Direktbild nur undeutlich zu sehen sind. Die Wellenlängen betragen ca. 150 m (langer Pfeil) und 160 m (etwas kürzerer Pfeil).
Mathematische Grundlagen Wir betrachten den Vektorraum und statten ihn mit einem Skalarprodukt aus, welches wir unten definieren. Einheitswurzeln Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen