Wikipedia - Benutzerbeiträge [de]

Visual Computing

2023-11-05T12:44:32Z

CompVisExp:

{{Dieser Artikel|behandelt den Oberbegriff. Zum Studiengang siehe [[Visual Computing (Studiengang)]].}}

'''Visual Computing''' ist ein Oberbegriff für alle Informatikdisziplinen, die sich mit Bildinformationen und 3D-Modellen beschäftigen.

Dazu zählen [[Computergrafik]], [[Bildverarbeitung]], [[Visualisierung]], [[Maschinelles Sehen|Computer Vision]], [[Virtual Reality]] und [[Augmented Reality]], [[Videobearbeitung]], aber auch Aspekte von [[Mustererkennung]], der [[Mensch-Computer-Interaktion]], des [[Maschinelles Lernen|maschinellen Lernens]] und [[Digitale Bibliothek|digitaler Bibliotheken]]. Dabei geht es um die Erfassung, Verarbeitung, Analyse und Darstellung visueller Informationen (hauptsächlich Bilder und Videos).

Anwendungsbereiche sind z. B. industrielle [[Qualitätskontrolle]], [[medizinische Bildverarbeitung]] und -visualisierung, [[Vermessung]], [[Robotik]], [[Multimedia|multimediale Systeme]], [[Virtual Heritage]], [[Visueller Effekt|Visuelle Effekte]] in Film und Fernsehen, und [[Computerspiel]]e.

An mehreren deutschsprachigen Universitäten werden eigene [[Visual Computing (Studiengang)|Studiengänge aus Visual Computing]] angeboten.<ref>[https://www.hs-coburg.de/studium/bachelor/technik-informatik/visual-computing.html Hochschule Coburg]</ref>

== Geschichte und Überblick ==
Visual Computing ist noch ein relativ junger Begriff, der erst ab 2005<ref>[http://www.isvc.net/ International Symposium on Visual Computing]</ref> seine heutige Bedeutung erlangte, als die in der Informationstechnologie etablierten Disziplinen [[Computergrafik]], [[Bildverarbeitung]], [[Maschinelles Sehen|Computer Vision]] u. ä. in ihrer Methodik und ihren Anwendungen immer näher zusammenrückten und ein Oberbegriff dafür benötigt wurde. Viele der verwendeten mathematischen und algorithmischen Methoden sind bei allen Bereichen, die Bilder verwenden, die gleichen: [[Grafikformat|Bildformate]], [[Filter (Bildverarbeitung)|Filtermethoden]], [[Farbmodell]]e, [[Bildmetrik]]en und andere. Auch die Programmiermethoden auf Graphik-Hardware, die Verarbeitung großer [[Datenmenge]]n, die Lehrbücher und die Kongresse, die wissenschaftlichen Communities dieser Disziplinen und die Arbeitsgruppen in Firmen vermischen sich immer mehr.

Dazu kommt, dass Anwendungen immer öfter Techniken aus mehreren dieser Disziplinen gleichzeitig benötigen. Um detailgenaue Modelle komplexer Gegenstände zu generieren benötigt man Bilderkennung, 3D-Sensoren und Rekonstruktionsverfahren. Um diese Modelle glaubwürdig darzustellen benötigt man realistische Renderingverfahren mit komplexer Beleuchtungssimulation. Echtzeitgrafik ist die Basis für brauchbare Virtual- und Augmented-Reality-Software. Eine gute Segmentierung der Organe ist bei der 3D-Darstellung von medizinischen Scans die Basis für interaktive Manipulationen. Robotersteuerung benötigt eine Erkennung der Objekte genauso wie eine Modellierung der Umwelt. Und eine ergonomische grafische Schnittstelle mit den verwendeten Geräten ist ebenfalls notwendig.

Wiewohl viele Aufgabenstellungen der Teildisziplinen in der wissenschaftlichen Welt (also meist unter „Laborbedingungen“) als gelöst gelten, besteht eine wesentliche Aufgabe der Gesamtdisziplin Visual Computing in der Integration der Teillösungen zu verwendbaren Produkten – das beinhaltet auch die Behandlung vieler praktischer Probleme, vom Umgang mit Hardwarevielfalt über die Verwendung echter (meist fehlerhafter oder umfangreicher) Daten bis zur Bedienung durch ungeschulte Benutzer.

== Bereiche des Visual Computing ==
Zumindest die folgenden Bereiche gehören zu Visual Computing. Ausführliche Beschreibungen jedes dieser Gebiete finden sich auf den jeweiligen Spezialseiten für die Begriffe.

=== Computergrafik und Computeranimation ===
[[Computergrafik]] ist ein Oberbegriff für alle Techniken, die Bildinformation als Ergebnis eines Berechnungsprozesses erzeugen. Mit [[Bildsynthese]] (Rendering) werden aus Beschreibungen von Objekten Bilder generiert, die je nach Anwendung meist einen Kompromiss aus Qualität und Rechenzeit darstellen. [[Computeranimation]] nennt man Computergrafik, wenn die Bilder zum Zweck der Erstellung eines Filmes erzeugt werden.

=== Bilderkennung und Computer Vision ===
Techniken, die aus vorhandenen Bildern Information über den Inhalt extrahieren können, fallen unter den Begriff [[Bilderkennung]]. Unter [[Maschinelles Sehen|Computer Vision]] versteht man die Fähigkeit des Computers (oder eines Roboters), die Umgebung zu erkennen und korrekt zu interpretieren.

=== Visualisierung und Interaktive Visuelle Analyse ===
Der Begriff [[Visualisierung]] wird meist verwendet, wenn Daten, die aus irgendeinem Grund einer direkten Darstellung nicht zugänglich sind, möglichst anschaulich dargestellt werden. Insbesondere gilt das für Volumendaten und Daten, die keine unmittelbare geometrische Dimension haben. Mit [[Informationsvisualisierung|Interaktiver Visueller Analyse]] kann man durch interaktive Veränderung der Darstellung unübersichtliche Datenmengen effizient untersuchen.

=== Geometrische Modellierung und 3D-Drucker ===
Die Repräsentation von darstellbaren Objekten im Rechner erfordert spezielle Methoden und Datenstrukturen, die unter dem Begriff [[Geometrische Modellierung]] geläufig sind. Neben beschreibenden und interaktiven geometrischen Techniken werden immer mehr auch Sensordaten zur Rekonstruktion der geometrischen Modelle verwendet. In neuerer Zeit werden auch Algorithmen zur effizienten Ansteuerung von [[3D-Druck]]ern zu Visual Computing gezählt.

=== Bildverarbeitung und Bildbearbeitung ===
Im Gegensatz zur Bilderkennung dient [[Bildverarbeitung]] dazu, aus Bildern bessere Bilder zu berechnen. „Besser“ kann dabei je nach Anwendung sehr unterschiedliche Bedeutungen haben. Zu unterscheiden ist davon die [[Bildbearbeitung]], die sich mit interaktiven Methoden zur manuellen Veränderung von Bildern beschäftigt.

=== Virtual und Augmented Reality sowie Sensorik ===
[[Virtuelle Realität|Virtual Reality]] heißen alle Techniken, die dem Benutzer suggerieren, sich in einer fiktiven Umgebung zu befinden. Dazu braucht man neben guten [[Head-Mounted Display|Datenbrillen]] vor allem exaktes [[Tracking]] und hochqualitative [[Computergrafik#Echtzeitrendern|Echtzeitgrafik]]. Bei [[Erweiterte Realität|Augmented Reality]] sieht man zusätzlich auch die reale Umgebung, wodurch die Anforderungen an die Genauigkeit der visuellen Darstellung und Lokalisierung erheblich steigen.

=== Grafische Komponenten von Mensch-Maschine-Interaktion ===
Das [[Mensch-Computer-Interaktion]] (oder {{enS|''Human Computer Interaction''}}) genannte Gebiet beschäftigt sich mit der benutzergerechten Gestaltung von interaktiven Systemen, wobei den grafischen Komponenten eine besondere Bedeutung zukommt, weil der visuelle Kanal des Menschen die höchste Bandbreite zur Aufnahme von Informationen hat.<ref>[https://https://www.mixedrealitylab.de/ Mixed Reality Lab]</ref>

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=7689894-5}}

[[Kategorie:Angewandte Informatik]]
[[Kategorie:Bildverarbeitung]]
[[Kategorie:Computergrafik]]

Visual Computing

2023-11-05T12:41:31Z

CompVisExp:

{{Dieser Artikel|behandelt den Oberbegriff. Zum Studiengang siehe [[Visual Computing (Studiengang)]].}}

'''Visual Computing''' ist ein Oberbegriff für alle Informatikdisziplinen, die sich mit Bildinformationen und 3D-Modellen beschäftigen.

Dazu zählen [[Computergrafik]], [[Bildverarbeitung]], [[Visualisierung]], [[Maschinelles Sehen|Computer Vision]], [[Virtual Reality]] und [[Augmented Reality]], [[Videobearbeitung]], aber auch Aspekte von [[Mustererkennung]], der [[Mensch-Computer-Interaktion]], des [[Maschinelles Lernen|maschinellen Lernens]] und [[Digitale Bibliothek|digitaler Bibliotheken]]. Dabei geht es um die Erfassung, Verarbeitung, Analyse und Darstellung visueller Informationen (hauptsächlich Bilder und Videos).

Anwendungsbereiche sind z. B. industrielle [[Qualitätskontrolle]], [[medizinische Bildverarbeitung]] und -visualisierung, [[Vermessung]], [[Robotik]], [[Multimedia|multimediale Systeme]], [[Virtual Heritage]], [[Visueller Effekt|Visuelle Effekte]] in Film und Fernsehen, und [[Computerspiel]]e.

An mehreren deutschsprachigen Universitäten werden eigene [[Visual Computing (Studiengang)|Studiengänge aus Visual Computing]] angeboten.<ref>[https://www.hs-coburg.de/studium/bachelor/technik-informatik/visual-computing.html Hochschule Coburg]</ref>

== Geschichte und Überblick ==
Visual Computing ist noch ein relativ junger Begriff, der erst ab 2005<ref>[http://www.isvc.net/ International Symposium on Visual Computing]</ref> seine heutige Bedeutung erlangte, als die in der Informationstechnologie etablierten Disziplinen [[Computergrafik]], [[Bildverarbeitung]], [[Maschinelles Sehen|Computer Vision]] u. ä. in ihrer Methodik und ihren Anwendungen immer näher zusammenrückten und ein Oberbegriff dafür benötigt wurde. Viele der verwendeten mathematischen und algorithmischen Methoden sind bei allen Bereichen, die Bilder verwenden, die gleichen: [[Grafikformat|Bildformate]], [[Filter (Bildverarbeitung)|Filtermethoden]], [[Farbmodell]]e, [[Bildmetrik]]en und andere. Auch die Programmiermethoden auf Graphik-Hardware, die Verarbeitung großer [[Datenmenge]]n, die Lehrbücher und die Kongresse, die wissenschaftlichen Communities dieser Disziplinen und die Arbeitsgruppen in Firmen vermischen sich immer mehr.

Dazu kommt, dass Anwendungen immer öfter Techniken aus mehreren dieser Disziplinen gleichzeitig benötigen. Um detailgenaue Modelle komplexer Gegenstände zu generieren benötigt man Bilderkennung, 3D-Sensoren und Rekonstruktionsverfahren. Um diese Modelle glaubwürdig darzustellen benötigt man realistische Renderingverfahren mit komplexer Beleuchtungssimulation. Echtzeitgrafik ist die Basis für brauchbare Virtual- und Augmented-Reality-Software. Eine gute Segmentierung der Organe ist bei der 3D-Darstellung von medizinischen Scans die Basis für interaktive Manipulationen. Robotersteuerung benötigt eine Erkennung der Objekte genauso wie eine Modellierung der Umwelt. Und eine ergonomische grafische Schnittstelle mit den verwendeten Geräten ist ebenfalls notwendig.

Wiewohl viele Aufgabenstellungen der Teildisziplinen in der wissenschaftlichen Welt (also meist unter „Laborbedingungen“) als gelöst gelten, besteht eine wesentliche Aufgabe der Gesamtdisziplin Visual Computing in der Integration der Teillösungen zu verwendbaren Produkten – das beinhaltet auch die Behandlung vieler praktischer Probleme, vom Umgang mit Hardwarevielfalt über die Verwendung echter (meist fehlerhafter oder umfangreicher) Daten bis zur Bedienung durch ungeschulte Benutzer.

== Bereiche des Visual Computing ==
Zumindest die folgenden Bereiche gehören zu Visual Computing. Ausführliche Beschreibungen jedes dieser Gebiete finden sich auf den jeweiligen Spezialseiten für die Begriffe.

=== Computergrafik und Computeranimation ===
[[Computergrafik]] ist ein Oberbegriff für alle Techniken, die Bildinformation als Ergebnis eines Berechnungsprozesses erzeugen. Mit [[Bildsynthese]] (Rendering) werden aus Beschreibungen von Objekten Bilder generiert, die je nach Anwendung meist einen Kompromiss aus Qualität und Rechenzeit darstellen. [[Computeranimation]] nennt man Computergrafik, wenn die Bilder zum Zweck der Erstellung eines Filmes erzeugt werden.

=== Bilderkennung und Computer Vision ===
Techniken, die aus vorhandenen Bildern Information über den Inhalt extrahieren können, fallen unter den Begriff [[Bilderkennung]]. Unter [[Maschinelles Sehen|Computer Vision]] versteht man die Fähigkeit des Computers (oder eines Roboters), die Umgebung zu erkennen und korrekt zu interpretieren.

=== Visualisierung und Interaktive Visuelle Analyse ===
Der Begriff [[Visualisierung]] wird meist verwendet, wenn Daten, die aus irgendeinem Grund einer direkten Darstellung nicht zugänglich sind, möglichst anschaulich dargestellt werden. Insbesondere gilt das für Volumendaten und Daten, die keine unmittelbare geometrische Dimension haben. Mit [[Informationsvisualisierung|Interaktiver Visueller Analyse]] kann man durch interaktive Veränderung der Darstellung unübersichtliche Datenmengen effizient untersuchen.

=== Geometrische Modellierung und 3D-Drucker ===
Die Repräsentation von darstellbaren Objekten im Rechner erfordert spezielle Methoden und Datenstrukturen, die unter dem Begriff [[Geometrische Modellierung]] geläufig sind. Neben beschreibenden und interaktiven geometrischen Techniken werden immer mehr auch Sensordaten zur Rekonstruktion der geometrischen Modelle verwendet. In neuerer Zeit werden auch Algorithmen zur effizienten Ansteuerung von [[3D-Druck]]ern zu Visual Computing gezählt.

=== Bildverarbeitung und Bildbearbeitung ===
Im Gegensatz zur Bilderkennung dient [[Bildverarbeitung]] dazu, aus Bildern bessere Bilder zu berechnen. „Besser“ kann dabei je nach Anwendung sehr unterschiedliche Bedeutungen haben. Zu unterscheiden ist davon die [[Bildbearbeitung]], die sich mit interaktiven Methoden zur manuellen Veränderung von Bildern beschäftigt.

=== Virtual und Augmented Reality sowie Sensorik ===
[[Virtuelle Realität|Virtual Reality]] heißen alle Techniken, die dem Benutzer suggerieren, sich in einer fiktiven Umgebung zu befinden. Dazu braucht man neben guten [[Head-Mounted Display|Datenbrillen]] vor allem exaktes [[Tracking]] und hochqualitative [[Computergrafik#Echtzeitrendern|Echtzeitgrafik]]. Bei [[Erweiterte Realität|Augmented Reality]] sieht man zusätzlich auch die reale Umgebung, wodurch die Anforderungen an die Genauigkeit der visuellen Darstellung und Lokalisierung erheblich steigen.

=== Grafische Komponenten von Mensch-Maschine-Interaktion ===
Das [[Mensch-Computer-Interaktion]] (oder {{enS|''Human Computer Interaction''}}) genannte Gebiet beschäftigt sich mit der benutzergerechten Gestaltung von interaktiven Systemen, wobei den grafischen Komponenten eine besondere Bedeutung zukommt, weil der visuelle Kanal des Menschen die höchste Bandbreite zur Aufnahme von Informationen hat.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=7689894-5}}

[[Kategorie:Angewandte Informatik]]
[[Kategorie:Bildverarbeitung]]
[[Kategorie:Computergrafik]]

Diskrete Fourier-Transformation

2021-08-30T15:51:43Z

CompVisExp: Korrektur

Die '''Diskrete Fourier-Transformation (DFT)''' ist eine Transformation aus dem Bereich der [[Fourier-Analysis]]<ref>Tilman Butz: ''Fouriertransformation für Fußgänger.'' 7. Auflage. Vieweg+Teubner Verlag, Wiesbaden 2011, ISBN 978-3-8348-0946-9, Kapitel 4.</ref><ref>M. W. Wong: ''Discrete Fourier Analysis.'' Birkhäuser Verlag, Basel 2011, ISBN 978-3-0348-0115-7.</ref>.
Sie bildet ein [[Zeitdiskretes Signal|zeitdiskretes endliches Signal]], das [[Periodische Fortsetzung|periodisch fortgesetzt]] wird, auf ein diskretes, periodisches [[Frequenzraum|Frequenzspektrum]] ab, das auch als [[Bildbereich]] bezeichnet wird. Die DFT besitzt in der [[Digitale Signalverarbeitung|digitalen Signalverarbeitung]] zur Signalanalyse große Bedeutung. Hier werden optimierte Varianten in Form der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] ({{enS|fast Fourier transform}}, ''FFT'') und ihrer Inversen angewandt.

Die DFT wird in der Signalverarbeitung für viele Aufgaben verwendet, so z. B.
* zur Bestimmung der in einem [[Abtastung (Signalverarbeitung)|abgetasteten]] Signal hauptsächlich vorkommenden [[Frequenz]]en,
* zur Bestimmung der [[Amplitude]]n und der zugehörigen [[Phasenverschiebung|Phasenlage]] zu diesen Frequenzen,
* zur Implementierung [[Digitales Filter|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 {{lang|en|''discrete-time Fourier transform,''}} ''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 <math>a=(a_0,\dotsc,a_{N-1})</math>, die zum Beispiel als [[Zeitdiskretes Signal|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 <math>a</math> eine Folge von komplexen Zahlen ist, also: <math>a=(a_0,\dotsc,a_{N-1})\in \Complex^N</math>

Das Ergebnis der Transformation ist eine Zerlegung der Folge in harmonische (sinusförmige) Anteile, sowie einen "Gleichanteil" <math>\hat a_0</math>, der dem Mittelwert der Eingangsfolge entspricht. Das Ergebnis nennt man "diskrete Fourier-Transformierte" <math>\hat a=(\hat a_0,\dotsc,\hat a_{N-1})\in\mathbb C^N</math> von <math>a</math>. Die Koeffizienten von <math>\hat a</math> sind die Amplituden der Zerlegungs-Anteile. Man nennt <math>\hat a_k</math> auch Fourierkoeffizienten oder Fourierkomponenten.

Üblicherweise wird bei der Bestimmung der Frequenzanteile/Phasenlage die kompakte mathematische Schreibweise der [[Polarform]] verwendet ([[Eulersche Formel]]):

:<math>\mathrm{e}^{\mathrm{i}\,\phi} = \cos\left(\phi \right) + \mathrm{i}\,\sin\left( \phi\right)</math>

Die Fourierkoeffizienten <math>\hat a_k</math> werden damit aus der Eingangsfolge berechnet durch:

:{| class="wikitable"
!<math>\hat a_k = \sum_{j=0}^{N-1} \mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j</math>   für   <math>k=0,\dotsc,N-1</math>
|}

Die Gleichung kann auch als [[Matrix-Vektor-Produkt]] geschrieben werden:

:{| class="wikitable"
!<math>\hat a = W\cdot a</math>   mit   <math>W[k,j] = \mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}</math>
|}

Die symmetrische [[Transformationsmatrix]] <math>W</math> mit der Dimension <math>N \times N</math> wird "Fourier-Matrix" genannt.

=== Inverse Diskrete Fourier-Transformation (iDFT) ===
Die Summe der sinusförmigen Zerlegungsanteile ergibt wiederum die ursprüngliche Eingangsfolge <math>a</math>.

Dafür wird das Transformationsergebnis <math>\hat a</math> als Koeffizienten eines [[Polynom]]s verwendet, wobei <math>\hat a_k
</math> die Amplituden von den zugehörigen harmonischen Schwingungen <math>z_k
</math> darstellen.

:<math>A(z_k)=\tfrac1N\left(\hat a_0z_k^0 + \hat a_1z_k^1 + \dots+\hat a_{N-1}z_k^{N-1}\right)\;.</math>

Die Argumente <math>z_0,z_1,\dotsc,z_{N-1}</math> sind <math>N</math> gleichverteilte Punkte auf dem Einheitskreis der [[Komplexe Zahl|komplexen Zahlenebene]], d. h. die <math>N</math>–ten [[Einheitswurzel]]n

:<math>z_k=\mathrm e^{\frac{2\pi \mathrm{i}}{N}k}=\cos \left(\tfrac{2\pi}{N}k \right)+\mathrm{i}\,\sin \left(\tfrac{2\pi}{N}k \right)\;.</math>

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 <math>a</math> lassen sich mit der iDFT aus den Fourierkoeffizienten <math>\hat a_j</math> bestimmen:
:{| class="wikitable"
!<math>a_k=\frac 1 N \sum_{j=0}^{N-1} \mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot \hat a_j</math>   für   <math>k=0,\dotsc,N-1</math>
|}

In der Schreibweise als [[Matrix-Vektor-Produkt]]:

:{| class="wikitable"
!<math>a = W^{-1}\cdot \hat a</math>   mit   <math>W^{-1}[k,j] = \frac 1 N \mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}</math>
|}

wobei hier <math>\hat a</math> mit der [[Inverse Matrix|inversen Matrix]] von <math>W</math> 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 <math>A(z)</math> mit einer gleichmäßig den Einheitskreis umlaufenden Funktion <math>z(t)=\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}</math> verknüpft. So ergibt sich eine zeitkontinuierliche [[periodische Funktion]]

:<math>
f(t)=A(z(t))
=\tfrac1N\left(\hat a_0+\hat a_1\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}+\hat a_2\mathrm e^{2\cdot \mathrm{i}2\pi\frac{t-t_0}T} + \dotsb
+ \hat a_{N-1}\mathrm e^{(N-1)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right),
</math>

die zu den Zeiten <math>t_k=t_0+\tfrac{k}{N}T</math> gerade die Funktionswerte <math>a_k=A(z_k)</math> annimmt.

Die Potenzen von <math>z(t)</math> haben die Gestalt

:<math>
z(t)^k=\mathrm e^{k\cdot \mathrm{i}2\pi\frac{t-t_0}T}=\cos(2k\pi\tfrac{t-t_0}T)+\mathrm{i}\,\sin(2k\pi\tfrac{t-t_0}T)
</math>

und daher die Periode <math>T/k</math> und die Frequenz <math>k/T</math> bzw. die Kreisfrequenz <math>2k\pi/T</math>. Somit ist die Folge der Messwerte durch die Superposition eines konstanten Pegels bei <math>k=0</math>, einer Grundschwingung bei <math>k=1</math> und Oberschwingungen bei <math>k>1</math> dargestellt und interpoliert worden.

Diese oben angegebene [[Interpolation (Mathematik)|Interpolations]]<nowiki />funktion ist nicht die einzige, die sich auf diese Art konstruieren lässt. Jede der Funktionen
:<math>
\begin{matrix}
f(t)
=\frac1N&\left(\hat a_0+\hat a_1\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}+\hat a_2\mathrm e^{2\cdot \mathrm{i}2\pi\frac{t-t_0}T}+\dots+\hat a_{M-1}\mathrm e^{(M-1)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right.\\
&\left.+ \hat a_{M}\mathrm e^{(M-N)\cdot \mathrm{i}2\pi\frac{t-t_0}T}+\dots+\hat a_{N-1}\mathrm e^{(N-1-N)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right)
\end{matrix}
</math>
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 [[hermitesch]]en Signal (<math>g(-\vec x)=\overline{g(\vec x)}</math>) im Frequenzraum:
:<math>
\hat a_{N-k}=\overline{\hat a_k}
</math>
Dies bedeutet, dass im Frequenzraum nur <math>N/2</math> unabhängige komplexe Koeffizienten <math>\hat a_k</math> 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 <math>N</math> (wie bei der vollen DFT), sondern nur <math>N/2</math> komplexe Zahlen nötig. Die anderen <math>N/2</math> komplexen Zahlen können durch elementare Rechnung rekonstruiert werden (siehe Formel oben). Die hermitesche Symmetrie bezieht sich auf das mittlere Element <math>k=N/2</math> des Signals <math>\hat a_k</math>.

::'''Beweis:''' Wegen der [[Eulersche Identität|Eulerschen Identität]] <math>\mathrm e^{2\pi \mathrm{i}}=1</math> und wegen <math>\overline{\mathrm e^{\mathrm{i}\phi}}=\mathrm e^{-\mathrm{i}\phi}</math> gilt im [[Reelle Zahlen|reellen]] Fall <math>a\in\R^N</math>:
:::<math>
\hat a_{N-k}
=\sum_{j=0}^{N-1}\mathrm e^{-2\pi \mathrm{i}\cdot\frac{Nj}{N}}\mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j
=\sum_{j=0}^{N-1}\overline{\mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j}
=\overline{\hat a_k}
</math>
Umgekehrt gilt entsprechend: Erfüllt <math>\hat a\in\Complex^N</math> die Bedingung <math>\hat a_{N-k}=\overline{\hat a_k}</math> für alle <math>k=1,\dotsc,N-1</math> sowie <math>\hat a_0 \in \R</math>, so ist die inverse DFT ein reeller Vektor <math>a\in\R^N</math>.

=== 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 <math>R</math> ein [[Kommutativität|kommutativer]] [[unitärer Ring]], in dem die Zahl <math>N</math> (das ist die <math>N</math>-fache Summe der <math>1</math>) eine [[Einheit (Mathematik)|Einheit]] ist. Des Weiteren gebe es in <math>R</math> eine primitive <math>N</math>-te [[Einheitswurzel]] <math>w</math>. Zu einem Tupel <math>a=(a_0,\dotsc,a_{N-1})\in R^N</math> ist dann die '''diskrete Fouriertransformierte''' <math>\hat a</math> durch
:<math>\hat a_k = \sum_{j=0}^{N-1} w^{-\,j\cdot k}\cdot a_j</math> für <math>k=0,\dotsc,N-1</math>
erklärt. Unter den getroffenen Voraussetzungen existiert damit zu <math>\hat a\in R^N</math> auch die '''diskrete inverse Fouriertransformierte''' <math>a</math> mit den Koeffizienten
:<math>a_k = {1\over N}\sum_{j=0}^{N-1} w^{j\cdot k}\cdot \hat a_j</math> für <math>k=0,\dotsc,N-1</math>.

Im überaus wichtigen Spezialfall <math>R= \Complex</math> wird für die DFT üblicherweise die <math>N</math>-te Einheitswurzel <math>w = \exp\left(2\pi\,\mathrm{i}/N\right)</math> 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:
:<math>\hat a_{k,l} = \sum_{m=0}^{M-1}\sum_{n=0}^{N-1}a_{m,n}\cdot \mathrm{e}^{-2\pi \mathrm{i}\cdot\frac{mk}{M}} \mathrm{e}^{-2\pi \mathrm{i}\cdot\frac{nl}{N}}</math> für <math>k=0,\dotsc,M-1</math> und <math>l=0,\dotsc,N-1</math>

Die Rücktransformation lautet entsprechend:
:<math>a_{m,n} = \frac{1}{MN} \sum_{k=0}^{M-1}\sum_{l=0}^{N-1}\hat a_{k,l}\cdot \mathrm e^{2\pi \mathrm{i}\cdot\frac{mk}{M}} \mathrm e^{2\pi \mathrm{i}\cdot\frac{nl}{N}}</math> für <math>m=0,\dotsc,M-1</math> und <math>n=0,\dotsc,N-1</math>

== Verschiebung und Skalierung in Zeit und Frequenz ==
In den Berechnungsformeln von DFT und iDFT kann die Summation (Indexvariable <math>j</math> oben) statt über <math>0,\dotsc,N-1</math> ebenso über einen verschobenen Bereich <math>k,\dotsc,N-1+k</math> laufen, wenn der Vektor <math>\textstyle a=(a_0,\dotsc,a_{N-1})</math> [[Periodische Folge|periodisch]] auf alle ganzzahligen Indizes fortgesetzt wird, denn es gilt <math>\textstyle w^{N+k} = w^k</math>. Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge <math>N</math> 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,
:<math>t_n:=nT</math> für <math>n=1-M,\cdots,N-M</math>,
die ebenfalls die Länge <math>N</math> hat. Auch ist es wünschenswert, den berechneten Koeffizienten Frequenzen zuzuordnen, die um <math>0</math> zentriert sind,
:<math>\omega_n:=2\pi\frac{n}{NT}</math> für <math>n=1-K,\dotsc,N-K</math>
und <math>K</math> in der Nähe von <math>N/2</math>.

Eine zu den gewählten Zeitpunkten „gemessene“ Funktion <math>f</math> ergibt den Beobachtungsvektor <math>\textstyle x\in\mathbb C^N</math> mit den Koeffizienten <math>\textstyle x_n=f(t_n)</math>, dessen DFT <math>\textstyle y_n=\hat f(\omega_n)=F(\omega_n)</math> in der Fourier-Analyse betrachtet wird. Dann ist
:<math>
F(\omega_n)=\sum_{k=1-M}^{N-M}\mathrm e^{-2\pi \mathrm{i}\frac{nkT}{NT}}x_k
=\sum_{k=1-M}^{N-M}\mathrm e^{-\mathrm{i}\,\omega_n\cdot t_k}f(t_k)
</math>
und
:<math>
f(t_n)=x_n=\frac1N \sum_{k=1-K}^{N-K}\mathrm e^{2\pi \mathrm{i}\frac{nkT}{NT}}y_k
=\frac1N \sum_{k=1-K}^{N-K}\mathrm e^{\mathrm{i}\omega_k\cdot t_n}F(\omega_k)
</math>.

== Beispiele ==
Die [[Fourier-Transformation]] transformiert eine Funktion <math>f(t)</math> nach <math>g(v)^*</math> von einer Zeitdarstellung <math>t</math> in den reziproken [[Frequenzraum]] <math>v:=1/t</math>. 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 [[Beugung (Physik)|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 ===
{| align="right"
| valign="top" | [[Datei:Twod fourier 1.png|mini|Berechnete 2D Fourier-Transformationen. Links Ausgangsbild, rechts Intensitätsverteilung der Fourier-Transformation.]]
| valign="top" | [[Datei:twod fourier 2.png|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 <math>a\times a</math> Pixeln. Das Bild oben links zeigt einen Spalt der Größe <math>e\times f</math> Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable <math>r</math> wird überführt in reziproke komplexe Werte <math>r^*</math>. Bei den gewählten Größen wird ein Pixel auf den reziproken Wert von <math>1/a</math> reziproken Pixeln überführt. Die Breite des Spalts von <math>e</math> Pixeln erscheint im Reziprokraum als Wert der Größe <math>r^*=a/e</math>, die Höhe <math>r^*=a/f</math>, mit harmonischen Frequenzen höherer Ordnung. Die berechneten Beugungsbilder geben die Intensitätsverteilungen der komplexen Größe <math>r^*</math> 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]], [[Kontinuierliche Fourier-Transformation|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]]).
<div style="clear:both;"></div>

=== Bild mit periodischen Strukturen ===
[[Datei:Sarwaterp.jpg|mini|links|[[Synthetic Aperture Radar|SAR]]-Bild des indischen Ozeans]]
[[Datei:Sarwaterfftp.jpg|mini|FFT des SAR-Bildes]]

Die Aufnahme links zeigt eine [[Synthetic Aperture Radar|SAR]]-Aufnahme des indischen Ozeans mit Wasserwellen unterschiedlicher Wellenlänge. Die [[Interne Wellen|internen Wellen]] oben rechts haben eine Wellenlänge von ca. 500 m. Die durch Wind erzeugten [[Wasserwelle|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).{{Absatz}}

== Mathematische Grundlage ==
Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen
:<math>\mathrm e^{\mathrm i\,2\pi \frac{n}N}</math>
sind <math>N</math>-te [[Einheitswurzel]]n, d. h., sie sind Lösungen der Gleichung <math>q^N=1</math>. Sei <math>q:=\mathrm e^{2\pi\,i/N}</math> die „kleinste“, also primitive Wurzel im ersten Quadranten. Diese genügt folgender Identität geometrischer Summen von Einheitswurzeln
:<math>\displaystyle \sum_{k=0}^{N-1} q^{nk}=N\delta_{0,n}</math> mit <math>n=0,\dotsc,N-1</math>
wegen
<math>\displaystyle \sum_{k=0}^{N-1} x^k=\frac{x^N-1}{x-1}</math> für <math>x\ne1</math>.

Dieses ist der „tiefe Grund“, weshalb die inverse DFT funktioniert.

Definieren wir in <math>\mathbb C^N</math> die Vektoren
:<math>f_n:=(\mathrm e^{\mathrm i2\pi\frac{nk}N})_{k=0,\dots,N-1}</math> für <math>n=0,\dotsc,N-1,</math>
so bilden diese eine [[Orthonormalbasis|orthonormale Basis]] zum Skalarprodukt
:<math>
\langle x,y\rangle = \frac1N\sum_{k=0}^{N-1}x_k\bar y_k
</math>.

Es gilt
:<math>
\langle f_n,f_m\rangle = \frac1N\sum_{k=0}^{N-1}\mathrm e^{\mathrm i2\pi\frac{(n-m)k}N}=\delta_{n,m}=\begin{cases}1&n=m\\0&n\ne m\end{cases}
</math>.

Jeder Vektor <math>x=(x_0,\dotsc,x_{N-1})\in\mathbb C^N</math> kann in der Orthonormalbasis dargestellt werden:
:<math>
\displaystyle x=\sum_{n=0}^{N-1} \langle x,f_n \rangle \cdot f_n
</math>.

Die Koeffizienten <math>\langle x,f_n\rangle</math> heißen (auch allgemein bei beliebigem Orthonormalsystem) ''Fourier-Koeffizienten,'' die DFT ordnet also einem Vektor <math>x</math> bis auf eine additive Konstante den Vektor <math>X=\operatorname{DFT}(x)</math> der Fourier-Koeffizienten zu.

Ist <math>Y=\operatorname{DFT}(y)</math> mit einem weiteren Vektor <math>y=(y_0,\dotsc,y_{N-1})\in\mathbb C^N</math>, so gilt die [[Parsevalsche Gleichung]] für Fourier-Koeffizienten:
:<math>
\langle x,y\rangle=\sum_{n=0}^{N-1}\langle x,f_n\rangle\langle f_n,y\rangle=\sum_{n=0}^{N-1}X_n\bar Y_n
</math>.

== Interpretationen der DFT ==
=== [[Diskretisierung]] der Fourier-Transformation ===
Die [[Fourier-Transformation]] erlaubt es, sich Funktionen mit reellem Argument (und diversen Einschränkungen wie: [[Lebesgue-Integral|Integrabilität]], Periodizität oder Abfall im Unendlichen) aus Schwingungen zusammengesetzt zu denken:
:<math>
f(t)= \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^\infty \hat f(\omega) \mathrm e^{\mathrm i \omega t} \, \mathrm d \omega
</math>
Eine wichtige Erkenntnis der Fouriertheorie ist, dass die Amplitude <math>\hat f(\omega)</math> sich ähnlich bestimmen lässt zu
:<math>
\hat f(\omega)= \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^\infty f(t) \mathrm e^{-\mathrm i \omega t} \, \mathrm d t.
</math>

Wählen wir einen Radius <math>R</math> so groß, dass außerhalb des Intervalls <math>[-R,R]</math> nur noch ein unwesentlicher Teil von <math>f</math> liegt, ist <math>f</math> außerdem stetig und eine Zahl <math>N</math> so groß gewählt, dass <math>T:=R/N</math> klein genug ist, um <math>f</math> sinnvoll singulär, d. h. durch Funktionswerte <math>f(kT)</math>, abzutasten, so kann das Fourierintegral in der Transformationsformel sinnvoll durch eine Summe ersetzt werden:
:<math>
\hat f(\omega)\approx F(\omega)=\frac{1}{\sqrt{2 \pi}} \sum_{k=-N}^N \mathrm e^{-\mathrm i \omega kT}f(kT) \,T
</math>
Das entspricht, bis auf einen konstanten Faktor <math>T/\sqrt{2 \pi}</math>, der Berechnungsformel der DFT. Der Vektor <math>x=( f(-NT),\dotsc,f(NT))</math> hat <math>2N+1</math> Elemente. Wir wissen bereits, dass es ausreicht, die Frequenzkoeffizienten für die <math>2N+1</math> Frequenzen <math>\omega_n:=2\pi\cdot \frac{n}{(2N+1)T}</math> mit <math>n=-N,\dotsc,-1,0,1,\dotsc,N</math> zu bestimmen, um die Funktionswerte im Vektor <math>x</math> zu rekonstruieren. Mit der notwendigen Anpassung der Konstanten in der iDFT erhalten wir
:<math>
f(nT)=\frac{1}{\sqrt{2 \pi}}\sum_{k=-N}^N \mathrm e^{\mathrm i \omega_k nT}F(\omega_k)\,\frac{2\pi}{(2N+1)T}.
</math>
Der Diskretisierungsabstand im Frequenzbereich ist proportional zu <math>1/R</math>, also nach Voraussetzung ebenfalls klein, sodass diese Berechnung der Diskretisierung der inversen Fourier-Transformation entspricht.

Beim Übergang von der Fourier-Transformation zur DFT sind also folgende Veränderungen zu bemerken:
* Das Signal liegt zu [[Diskretheit|diskreten]], [[Äquidistanz (Mathematik)|äquidistanten]] Zeitpunkten vor (<math>T=</math> Abstand zweier aufeinanderfolgender Zeitpunkte), <math>0</math> ist einer dieser Zeitpunkte.
* Das Signal hat eine endliche Länge (<math>2N+1=</math> Anzahl der Werte), die als Werte innerhalb eines großen Intervalls <math>[-NT,NT]</math> interpretiert werden.
* Die Integrale bei der Berechnung der Fourier-Koeffizienten werden bei der DFT zu Summen.
* Das Spektrum wird nur für eine endliche Anzahl von (Kreis-)Frequenzen berechnet <math>\omega=2\pi n/((2N+1)T)</math> mit <math>n=-N,\dotsc,-1,0,1,2,\dotsc,N</math> und ist periodisch in der Frequenz, wobei die Periode <math>2\pi/T</math> nach Voraussetzung (<math>T</math> klein) sehr groß ist.

=== Diskretisierung von Fourier-Reihen ===
Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode <math>L</math> kann als [[Funktionenreihe]] mit Sinusoiden, die Bruchteile von <math>L</math> als Periode haben, dargestellt werden (sogenannte [[Fourier-Reihe]]n):
:<math>f(t)=\sum_{n\in\mathbb Z} c_n(f)\mathrm e^{\mathrm{i}\cdot \omega_nt}</math> mit <math>\omega_n=\frac{2\pi n}{L}</math>

Brechen wir die Reihenentwicklung bei großen Grenzen <math>1-M</math> unten und <math>N-M</math> oben ab, so erhalten wir mit <math>T:=L/N</math>
:<math>
f(t_k)=f(kT)\approx \sum_{n=1-M}^{N-M} c_n(f)\mathrm e^{2\pi \mathrm{i}\cdot \frac{nk}{N}},
</math>
d. h., wir erhalten eine Form der inversen DFT. Damit können die Koeffizienten mittels DFT approximiert werden zu
:<math>
c_n(f)\approx\frac{1}{L}\sum_{k=0}^{N-1} f(kT)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi nk}{N}}\cdot \frac{L}{N}=\frac{1}{L}\sum_{k=0}^{N-1} f(t_k)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi n}{L}t_k}\cdot T.
</math>

Im Grenzfall eines unendlich großen <math>N</math> ergeben sich die bekannten Koeffizientenintegrale der Fourier-Reihen:
:<math>
c_n(f)=\frac{1}{L}\int_0^L f(t)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi n}{L}t}\, \mathrm d t
</math>

=== Ausgleichsrechnung mit trigonometrischen Funktionen ===
Das Ergebnis einer DFT-Berechnung kann auch als eine Modellierung des Originalsignals mit Hilfe von trigonometrischen Fubktionen interpretiert werden. Ein verständlicher Nachweis der Relation zwischen Ausgleichsrechnung (Methode der kleinsten Fehlerquadrate) und der diskreten Fourier-Transformation findet sich in <ref>Tilo Strutz: Explaining the Discrete Fourier Transform of real signals based on the least-squares approximation of time-discrete signals using trigonometric functions. 2017, TECHP/2017/11, [http://dx.doi.org/10.13140/RG.2.2.34597.81126 "DOI: 10.13140/RG.2.2.34597.81126"], [https://www.researchgate.net/publication/321075372_Explaining_the_Discrete_Fourier_Transform_of_real_signals_based_on_the_least-squares_approximation_of_time-discrete_signals_using_trigonometric_functions "PDF"]</ref>.

== Eigenschaften ==
=== Spektrum abgetasteter Funktionen ===
[[Datei:Dft spektrum.jpg|mini|Abb. 1: Betrag und Phase des Spektrums eines abgetasteten Signals]]

Die diskrete Fourier-Transformation besitzt ein periodisches Spektrum, es wiederholt sich mit der Abtastfrequenz und ist symmetrisch zur Abtastfrequenz. Es gilt:
:<math>
F\left(\omega+\frac{2 \pi}{T} m\right)= C\sum_{k = 0}^{N - 1} f(kT) \mathrm e^{-\mathrm{i} \omega kT}\mathrm e^{-\mathrm{i} \frac{2 \pi}{T}mkT}= F(\omega)
</math> (wegen <math>\mathrm e^{-\mathrm{i} 2 \pi m k}=1</math> für natürliche Zahlen <math>m</math> und <math>k</math>)
:<math>
F\left(\frac{2 \pi}{T}-\omega\right)= C\sum_{k = 0}^{N - 1} f(kT) \mathrm e^{-\mathrm{i} \frac{2\pi}{T} kT} \mathrm e^{+\mathrm{i} \omega kT}= F^{*}(\omega)
</math>

Enthält das abgetastete Signal Frequenzanteile oberhalb der halben Abtastfrequenz, überlappen sich die Spektren des ursprünglichen Signals mit den an der Abtastfrequenz gespiegelten Signalanteilen, und es kommt zum Alias-Effekt.

=== Alias-Effekt ===
{{Hauptartikel|Alias-Effekt}}

In der Regel entsteht das zeitdiskrete Signal durch [[Abtastung (Signalverarbeitung)|Diskretisierung]] eines kontinuierlichen Signals. Die durch die DFT entstehenden Spektren sind nur dann mit den Spektren des zugrundeliegenden kontinuierlichen Signals identisch, wenn bei der Abtastung das [[Nyquist-Shannon-Abtasttheorem|Abtasttheorem]] nicht verletzt wurde. Für Signale im [[Basisband]] muss gelten, dass die Abtastfrequenz mehr als doppelt so groß ist wie die maximal auftretende Frequenz ([[Nyquist-Frequenz]]). Bei Verletzung des Abtasttheorems tritt eine Verfälschung des Originalsignals auf (Aliasing im Zeitbereich). Eine Möglichkeit des [[Antialiasing (Signalverarbeitung)|Antialiasing]] ist die Bandbegrenzung des Signals am Eingang des Systems, um diesen Effekt zu vermeiden.

=== DFT einer zeitbegrenzten Funktion ===
Für periodische Funktionen ergibt sich (analog zur kontinuierlichen [[Fourier-Transformation]]) ein Linienspektrum mit einem Frequenzlinienabstand von 1/Periodenlänge.

[[Datei:Rechteckfenster Spektrum.jpg|mini|Abb. 2: Fourier-Transformierte eines Rechteck-Fensters]]
Eine zeitbegrenzte diskrete Funktion <math>g(kT)</math> kann man aus einer periodischen diskreten Funktion <math>f(kT)</math> ableiten, indem man über ein Zeitfenster <math>w(t)</math> genau eine Periode herausschneidet:
:<math>
g(kT) = f(kT) \cdot w(t)
</math>

Da bei der Fourier-Transformation eine Multiplikation von Funktionen im Zeitbereich einer [[Faltung (Mathematik)|Faltung]] der Fourier-Transformierten im Frequenzbereich entspricht, ergibt sich die DFT der zeitbegrenzten Funktion <math>G(\omega)</math> durch die Faltung der DFT der periodischen Funktion <math>F(\omega)</math> mit der Fourier-Transformierten des Zeitfensters <math>W(\omega)</math>:
:<math>
G(\omega) = F(\omega) \star W(\omega)
</math>

[[Datei:Dft spektrum fenster.jpg|mini|Abb. 3: Zusammensetzung des Spektrums einer zeitbegrenzten Funktion]]

Als Ergebnis erhält man ein Linienspektrum, das durch die Fourier-Transformierte des Zeitfensters ''verschmiert'' ist. In Abb. 3 rechts gestrichelt dargestellt ist der Einfluss des Zeitfensters auf die DFT der periodischen Funktion (dicke Linien). Durch die Zeitbegrenzung kommen Frequenzanteile zwischen den analysierten Frequenzlinien hinzu.

Durch den Übergang von einer periodischen Funktion auf eine zeitbegrenzte Funktion muss nicht das Rechenverfahren zur Bestimmung des Spektrums verändert werden. Es werden weiterhin diskrete Frequenzlinien berechnet, als ob eine periodische Funktion dahinterstände. Als Effekt des Zeitfensters steht nun jede berechnete Frequenzlinie stellvertretend für einen ganzen Frequenzbereich, nämlich für den Frequenzbereich, der durch die Fourier-Transformierte des Zeitfensters hinzugekommen ist. Dieses Verhalten bezeichnet man auch als ''Leck-Effekt.''

=== Leck-Effekt (Leakage effect) ===
{{Hauptartikel|Leck-Effekt}}

Aufgrund der zeitlichen Begrenzung des Signals kann es dazu kommen, dass das Eingangssignal abgeschnitten wird. Ein abgeschnittenes Eingangssignal kann nur dann korrekt mit der DFT transformiert werden, wenn es periodisch fortsetzbar ist. Falls das Signal nicht periodisch fortsetzbar ist, enthält es Frequenzen, die nicht zu den von der DFT berechneten diskreten Frequenzen gehören. Die DFT „nähert“ diese Frequenzen durch die benachbarten Frequenzen an, dabei wird die Energie auf diese Frequenzen verteilt. Dies wird als Leck-Effekt (englisch {{lang|en|leakage effect}}) bezeichnet.

Die zeitliche Begrenzung kommt einer Multiplikation mit einer [[Rechteckfunktion]] gleich und entspricht einer Faltung mit der [[si-Funktion]] im Frequenzbereich. Dies ist eine andere Betrachtungsweise, um den Leck-Effekt zu erklären. Das gilt natürlich auch im Falle anderer [[Fensterfunktion]]en (z. B. Hamming, von Hann, Gauss). Somit ist das Spektrum der Fensterfunktion (bzw. die Breite des Spektrums) ausschlaggebend für das Leck. Die Amplitudengenauigkeit ist das andere Kriterium einer Fensterfunktion.

=== Gleitende DFT als Bandfilterbank ===
Eine DFT einer zeitbegrenzten Funktion kann man auch als Bandfilterbank ansehen.
* Die Mittenfrequenzen dieser Bandfilter entsprechen den Frequenzlinien der Funktion, die entsteht, wenn man den betrachteten Zeitabschnitt periodisch wiederholt (Vielfache von 1/Fensterbreite).
* Die Breite und [[Flankensteilheit]] der Bandfilter wird durch die Fourier-Transformierten des Zeitfensters bestimmt (siehe Abb. 3).

Durch die Wahl einer geeigneten Zeitfenster-Funktion kann man die Eigenschaften der Bandfilter verändern.
* Bei einem rechteckförmigen Zeitfenster mit Unstetigkeitsstellen an den Fenstergrenzen werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz abgeschwächt; man erzielt Flankensteilheiten von 6 dB/Oktave (siehe Abb. 2).
* Ist die Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz<sup>2</sup> abgeschwächt; man erzielt Flankensteilheiten von 12 dB/Oktave.
* Ist die 1. Ableitung der Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz<sup>3</sup> abgeschwächt; die Flankensteilheit beträgt 18 dB/Oktave.
* usw.

Bestimmt man die Fourier-Transformierte von jeweils aufeinanderfolgenden Zeitabschnitten, erhält man die '''gleitende Fourier-Transformation.''' Mit der Analyse eines neuen Zeitabschnitts erhält man dann neue Abtastwerte für den Zeitverlauf der Spektrallinien (das heißt den Zeitverlauf der Signale an den Ausgängen der „Bandfilter“).

=== Unschärfe-Relation der gleitenden DFT ===
Zeit- und Frequenzauflösung der gleitenden DFT können nicht unabhängig voneinander gewählt werden.
* Will man Signale mit hoher [[Frequenzauflösung]] analysieren, muss man die Zeitfenster sehr groß machen, man erhält eine geringe Zeitauflösung.
* Benötigt man eine hohe Zeitauflösung, muss man die Breite der Zeitfenster sehr kurz machen, dann kann man aber nur wenige Frequenzlinien bestimmen.
* Es gilt: Frequenzauflösung ≈ 1/Zeitfensterbreite (wird eine Frequenzauflösung von 1 kHz gewünscht, muss das Zeitfenster mindestens 1 ms lang sein).

== FFT ==
Für Blocklängen <math>N</math>, die sich als Potenz von 2 darstellen lassen, kann die Berechnung mit dem Algorithmus der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT) erfolgen. Allgemein gilt: Kann die Blocklänge faktorisiert werden, <math>N=KM</math>, so gibt es eine Zerlegung der DFT der Länge <math>N</math> in ein Produkt von DFTs der Längen <math>K</math> und <math>M</math> sowie zweier einfacher Matrizen.

== Goertzel-Algorithmus ==
Für beliebige Blocklängen <math>N</math> und zur Bestimmung einer einzigen oder einiger weniger spektraler Komponenten kann auch der [[Goertzel-Algorithmus]] verwendet werden. Der Vorteil besteht in einer sehr effizienten Implementierung in Computersystemen, da die Berechnung pro Spektralkomponente nur eine komplexe Multiplikation und zwei komplexe Additionen umfasst.

== Anwendungen ==
* Berechnung der Fourier-Transformierten eines Signals
* [[Signalanalyse]]
* [[Schwingungsanalyse]] und [[Modalanalyse]]
* Bearbeitung von Signalen
* Berechnung von [[Korrelation]]en
* Berechnung von Polynomprodukten in <math>\mathcal{O}(n \cdot \log(n))</math>

Bei der Berechnung von [[Oberflächenwellenfilter]]n (= 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.

== Siehe auch ==
* [[Faltung (Mathematik)|Faltung]]
* [[Gabor-Transformation]]
* [[Laplace-Transformation]]
* [[z-Transformation]]
* [[Diskrete Kosinustransformation]]
* [[Wavelet-Transformation]]
* [[Fensterfunktion]]
* [[Fourierreihe]]
* [[Short-Time-Fourier-Transformation]]

== Literatur ==

[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Diskrete Transformation]]

[[cs:Fourierova transformace#Diskrétní Fourierova transformace]]
[[fi:Fourier'n muunnos#Diskreetti Fourier'n muunnos]]
[[pt:Transformada de Fourier#Transformada discreta de Fourier]]

Diskrete Fourier-Transformation

2021-08-30T15:50:47Z

CompVisExp: eine dritte Variante der Interpretation wurde hinzu gefügt, mit Referenz; andere Referenzen in Text eingebettet

Die '''Diskrete Fourier-Transformation (DFT)''' ist eine Transformation aus dem Bereich der [[Fourier-Analysis]]<ref>Tilman Butz: ''Fouriertransformation für Fußgänger.'' 7. Auflage. Vieweg+Teubner Verlag, Wiesbaden 2011, ISBN 978-3-8348-0946-9, Kapitel 4.</ref><ref>M. W. Wong: ''Discrete Fourier Analysis.'' Birkhäuser Verlag, Basel 2011, ISBN 978-3-0348-0115-7.</ref>.
Sie bildet ein [[Zeitdiskretes Signal|zeitdiskretes endliches Signal]], das [[Periodische Fortsetzung|periodisch fortgesetzt]] wird, auf ein diskretes, periodisches [[Frequenzraum|Frequenzspektrum]] ab, das auch als [[Bildbereich]] bezeichnet wird. Die DFT besitzt in der [[Digitale Signalverarbeitung|digitalen Signalverarbeitung]] zur Signalanalyse große Bedeutung. Hier werden optimierte Varianten in Form der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] ({{enS|fast Fourier transform}}, ''FFT'') und ihrer Inversen angewandt.

Die DFT wird in der Signalverarbeitung für viele Aufgaben verwendet, so z. B.
* zur Bestimmung der in einem [[Abtastung (Signalverarbeitung)|abgetasteten]] Signal hauptsächlich vorkommenden [[Frequenz]]en,
* zur Bestimmung der [[Amplitude]]n und der zugehörigen [[Phasenverschiebung|Phasenlage]] zu diesen Frequenzen,
* zur Implementierung [[Digitales Filter|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 {{lang|en|''discrete-time Fourier transform,''}} ''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 <math>a=(a_0,\dotsc,a_{N-1})</math>, die zum Beispiel als [[Zeitdiskretes Signal|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 <math>a</math> eine Folge von komplexen Zahlen ist, also: <math>a=(a_0,\dotsc,a_{N-1})\in \Complex^N</math>

Das Ergebnis der Transformation ist eine Zerlegung der Folge in harmonische (sinusförmige) Anteile, sowie einen "Gleichanteil" <math>\hat a_0</math>, der dem Mittelwert der Eingangsfolge entspricht. Das Ergebnis nennt man "diskrete Fourier-Transformierte" <math>\hat a=(\hat a_0,\dotsc,\hat a_{N-1})\in\mathbb C^N</math> von <math>a</math>. Die Koeffizienten von <math>\hat a</math> sind die Amplituden der Zerlegungs-Anteile. Man nennt <math>\hat a_k</math> auch Fourierkoeffizienten oder Fourierkomponenten.

Üblicherweise wird bei der Bestimmung der Frequenzanteile/Phasenlage die kompakte mathematische Schreibweise der [[Polarform]] verwendet ([[Eulersche Formel]]):

:<math>\mathrm{e}^{\mathrm{i}\,\phi} = \cos\left(\phi \right) + \mathrm{i}\,\sin\left( \phi\right)</math>

Die Fourierkoeffizienten <math>\hat a_k</math> werden damit aus der Eingangsfolge berechnet durch:

:{| class="wikitable"
!<math>\hat a_k = \sum_{j=0}^{N-1} \mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j</math>   für   <math>k=0,\dotsc,N-1</math>
|}

Die Gleichung kann auch als [[Matrix-Vektor-Produkt]] geschrieben werden:

:{| class="wikitable"
!<math>\hat a = W\cdot a</math>   mit   <math>W[k,j] = \mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}</math>
|}

Die symmetrische [[Transformationsmatrix]] <math>W</math> mit der Dimension <math>N \times N</math> wird "Fourier-Matrix" genannt.

=== Inverse Diskrete Fourier-Transformation (iDFT) ===
Die Summe der sinusförmigen Zerlegungsanteile ergibt wiederum die ursprüngliche Eingangsfolge <math>a</math>.

Dafür wird das Transformationsergebnis <math>\hat a</math> als Koeffizienten eines [[Polynom]]s verwendet, wobei <math>\hat a_k
</math> die Amplituden von den zugehörigen harmonischen Schwingungen <math>z_k
</math> darstellen.

:<math>A(z_k)=\tfrac1N\left(\hat a_0z_k^0 + \hat a_1z_k^1 + \dots+\hat a_{N-1}z_k^{N-1}\right)\;.</math>

Die Argumente <math>z_0,z_1,\dotsc,z_{N-1}</math> sind <math>N</math> gleichverteilte Punkte auf dem Einheitskreis der [[Komplexe Zahl|komplexen Zahlenebene]], d. h. die <math>N</math>–ten [[Einheitswurzel]]n

:<math>z_k=\mathrm e^{\frac{2\pi \mathrm{i}}{N}k}=\cos \left(\tfrac{2\pi}{N}k \right)+\mathrm{i}\,\sin \left(\tfrac{2\pi}{N}k \right)\;.</math>

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 <math>a</math> lassen sich mit der iDFT aus den Fourierkoeffizienten <math>\hat a_j</math> bestimmen:
:{| class="wikitable"
!<math>a_k=\frac 1 N \sum_{j=0}^{N-1} \mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot \hat a_j</math>   für   <math>k=0,\dotsc,N-1</math>
|}

In der Schreibweise als [[Matrix-Vektor-Produkt]]:

:{| class="wikitable"
!<math>a = W^{-1}\cdot \hat a</math>   mit   <math>W^{-1}[k,j] = \frac 1 N \mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}</math>
|}

wobei hier <math>\hat a</math> mit der [[Inverse Matrix|inversen Matrix]] von <math>W</math> 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 <math>A(z)</math> mit einer gleichmäßig den Einheitskreis umlaufenden Funktion <math>z(t)=\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}</math> verknüpft. So ergibt sich eine zeitkontinuierliche [[periodische Funktion]]

:<math>
f(t)=A(z(t))
=\tfrac1N\left(\hat a_0+\hat a_1\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}+\hat a_2\mathrm e^{2\cdot \mathrm{i}2\pi\frac{t-t_0}T} + \dotsb
+ \hat a_{N-1}\mathrm e^{(N-1)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right),
</math>

die zu den Zeiten <math>t_k=t_0+\tfrac{k}{N}T</math> gerade die Funktionswerte <math>a_k=A(z_k)</math> annimmt.

Die Potenzen von <math>z(t)</math> haben die Gestalt

:<math>
z(t)^k=\mathrm e^{k\cdot \mathrm{i}2\pi\frac{t-t_0}T}=\cos(2k\pi\tfrac{t-t_0}T)+\mathrm{i}\,\sin(2k\pi\tfrac{t-t_0}T)
</math>

und daher die Periode <math>T/k</math> und die Frequenz <math>k/T</math> bzw. die Kreisfrequenz <math>2k\pi/T</math>. Somit ist die Folge der Messwerte durch die Superposition eines konstanten Pegels bei <math>k=0</math>, einer Grundschwingung bei <math>k=1</math> und Oberschwingungen bei <math>k>1</math> dargestellt und interpoliert worden.

Diese oben angegebene [[Interpolation (Mathematik)|Interpolations]]<nowiki />funktion ist nicht die einzige, die sich auf diese Art konstruieren lässt. Jede der Funktionen
:<math>
\begin{matrix}
f(t)
=\frac1N&\left(\hat a_0+\hat a_1\mathrm e^{\mathrm{i}2\pi\frac{t-t_0}T}+\hat a_2\mathrm e^{2\cdot \mathrm{i}2\pi\frac{t-t_0}T}+\dots+\hat a_{M-1}\mathrm e^{(M-1)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right.\\
&\left.+ \hat a_{M}\mathrm e^{(M-N)\cdot \mathrm{i}2\pi\frac{t-t_0}T}+\dots+\hat a_{N-1}\mathrm e^{(N-1-N)\cdot \mathrm{i}2\pi\frac{t-t_0}T}\right)
\end{matrix}
</math>
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 [[hermitesch]]en Signal (<math>g(-\vec x)=\overline{g(\vec x)}</math>) im Frequenzraum:
:<math>
\hat a_{N-k}=\overline{\hat a_k}
</math>
Dies bedeutet, dass im Frequenzraum nur <math>N/2</math> unabhängige komplexe Koeffizienten <math>\hat a_k</math> 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 <math>N</math> (wie bei der vollen DFT), sondern nur <math>N/2</math> komplexe Zahlen nötig. Die anderen <math>N/2</math> komplexen Zahlen können durch elementare Rechnung rekonstruiert werden (siehe Formel oben). Die hermitesche Symmetrie bezieht sich auf das mittlere Element <math>k=N/2</math> des Signals <math>\hat a_k</math>.

::'''Beweis:''' Wegen der [[Eulersche Identität|Eulerschen Identität]] <math>\mathrm e^{2\pi \mathrm{i}}=1</math> und wegen <math>\overline{\mathrm e^{\mathrm{i}\phi}}=\mathrm e^{-\mathrm{i}\phi}</math> gilt im [[Reelle Zahlen|reellen]] Fall <math>a\in\R^N</math>:
:::<math>
\hat a_{N-k}
=\sum_{j=0}^{N-1}\mathrm e^{-2\pi \mathrm{i}\cdot\frac{Nj}{N}}\mathrm e^{2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j
=\sum_{j=0}^{N-1}\overline{\mathrm e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot a_j}
=\overline{\hat a_k}
</math>
Umgekehrt gilt entsprechend: Erfüllt <math>\hat a\in\Complex^N</math> die Bedingung <math>\hat a_{N-k}=\overline{\hat a_k}</math> für alle <math>k=1,\dotsc,N-1</math> sowie <math>\hat a_0 \in \R</math>, so ist die inverse DFT ein reeller Vektor <math>a\in\R^N</math>.

=== 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 <math>R</math> ein [[Kommutativität|kommutativer]] [[unitärer Ring]], in dem die Zahl <math>N</math> (das ist die <math>N</math>-fache Summe der <math>1</math>) eine [[Einheit (Mathematik)|Einheit]] ist. Des Weiteren gebe es in <math>R</math> eine primitive <math>N</math>-te [[Einheitswurzel]] <math>w</math>. Zu einem Tupel <math>a=(a_0,\dotsc,a_{N-1})\in R^N</math> ist dann die '''diskrete Fouriertransformierte''' <math>\hat a</math> durch
:<math>\hat a_k = \sum_{j=0}^{N-1} w^{-\,j\cdot k}\cdot a_j</math> für <math>k=0,\dotsc,N-1</math>
erklärt. Unter den getroffenen Voraussetzungen existiert damit zu <math>\hat a\in R^N</math> auch die '''diskrete inverse Fouriertransformierte''' <math>a</math> mit den Koeffizienten
:<math>a_k = {1\over N}\sum_{j=0}^{N-1} w^{j\cdot k}\cdot \hat a_j</math> für <math>k=0,\dotsc,N-1</math>.

Im überaus wichtigen Spezialfall <math>R= \Complex</math> wird für die DFT üblicherweise die <math>N</math>-te Einheitswurzel <math>w = \exp\left(2\pi\,\mathrm{i}/N\right)</math> 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:
:<math>\hat a_{k,l} = \sum_{m=0}^{M-1}\sum_{n=0}^{N-1}a_{m,n}\cdot \mathrm{e}^{-2\pi \mathrm{i}\cdot\frac{mk}{M}} \mathrm{e}^{-2\pi \mathrm{i}\cdot\frac{nl}{N}}</math> für <math>k=0,\dotsc,M-1</math> und <math>l=0,\dotsc,N-1</math>

Die Rücktransformation lautet entsprechend:
:<math>a_{m,n} = \frac{1}{MN} \sum_{k=0}^{M-1}\sum_{l=0}^{N-1}\hat a_{k,l}\cdot \mathrm e^{2\pi \mathrm{i}\cdot\frac{mk}{M}} \mathrm e^{2\pi \mathrm{i}\cdot\frac{nl}{N}}</math> für <math>m=0,\dotsc,M-1</math> und <math>n=0,\dotsc,N-1</math>

== Verschiebung und Skalierung in Zeit und Frequenz ==
In den Berechnungsformeln von DFT und iDFT kann die Summation (Indexvariable <math>j</math> oben) statt über <math>0,\dotsc,N-1</math> ebenso über einen verschobenen Bereich <math>k,\dotsc,N-1+k</math> laufen, wenn der Vektor <math>\textstyle a=(a_0,\dotsc,a_{N-1})</math> [[Periodische Folge|periodisch]] auf alle ganzzahligen Indizes fortgesetzt wird, denn es gilt <math>\textstyle w^{N+k} = w^k</math>. Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge <math>N</math> 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,
:<math>t_n:=nT</math> für <math>n=1-M,\cdots,N-M</math>,
die ebenfalls die Länge <math>N</math> hat. Auch ist es wünschenswert, den berechneten Koeffizienten Frequenzen zuzuordnen, die um <math>0</math> zentriert sind,
:<math>\omega_n:=2\pi\frac{n}{NT}</math> für <math>n=1-K,\dotsc,N-K</math>
und <math>K</math> in der Nähe von <math>N/2</math>.

Eine zu den gewählten Zeitpunkten „gemessene“ Funktion <math>f</math> ergibt den Beobachtungsvektor <math>\textstyle x\in\mathbb C^N</math> mit den Koeffizienten <math>\textstyle x_n=f(t_n)</math>, dessen DFT <math>\textstyle y_n=\hat f(\omega_n)=F(\omega_n)</math> in der Fourier-Analyse betrachtet wird. Dann ist
:<math>
F(\omega_n)=\sum_{k=1-M}^{N-M}\mathrm e^{-2\pi \mathrm{i}\frac{nkT}{NT}}x_k
=\sum_{k=1-M}^{N-M}\mathrm e^{-\mathrm{i}\,\omega_n\cdot t_k}f(t_k)
</math>
und
:<math>
f(t_n)=x_n=\frac1N \sum_{k=1-K}^{N-K}\mathrm e^{2\pi \mathrm{i}\frac{nkT}{NT}}y_k
=\frac1N \sum_{k=1-K}^{N-K}\mathrm e^{\mathrm{i}\omega_k\cdot t_n}F(\omega_k)
</math>.

== Beispiele ==
Die [[Fourier-Transformation]] transformiert eine Funktion <math>f(t)</math> nach <math>g(v)^*</math> von einer Zeitdarstellung <math>t</math> in den reziproken [[Frequenzraum]] <math>v:=1/t</math>. 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 [[Beugung (Physik)|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 ===
{| align="right"
| valign="top" | [[Datei:Twod fourier 1.png|mini|Berechnete 2D Fourier-Transformationen. Links Ausgangsbild, rechts Intensitätsverteilung der Fourier-Transformation.]]
| valign="top" | [[Datei:twod fourier 2.png|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 <math>a\times a</math> Pixeln. Das Bild oben links zeigt einen Spalt der Größe <math>e\times f</math> Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable <math>r</math> wird überführt in reziproke komplexe Werte <math>r^*</math>. Bei den gewählten Größen wird ein Pixel auf den reziproken Wert von <math>1/a</math> reziproken Pixeln überführt. Die Breite des Spalts von <math>e</math> Pixeln erscheint im Reziprokraum als Wert der Größe <math>r^*=a/e</math>, die Höhe <math>r^*=a/f</math>, mit harmonischen Frequenzen höherer Ordnung. Die berechneten Beugungsbilder geben die Intensitätsverteilungen der komplexen Größe <math>r^*</math> 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]], [[Kontinuierliche Fourier-Transformation|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]]).
<div style="clear:both;"></div>

=== Bild mit periodischen Strukturen ===
[[Datei:Sarwaterp.jpg|mini|links|[[Synthetic Aperture Radar|SAR]]-Bild des indischen Ozeans]]
[[Datei:Sarwaterfftp.jpg|mini|FFT des SAR-Bildes]]

Die Aufnahme links zeigt eine [[Synthetic Aperture Radar|SAR]]-Aufnahme des indischen Ozeans mit Wasserwellen unterschiedlicher Wellenlänge. Die [[Interne Wellen|internen Wellen]] oben rechts haben eine Wellenlänge von ca. 500 m. Die durch Wind erzeugten [[Wasserwelle|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).{{Absatz}}

== Mathematische Grundlage ==
Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen
:<math>\mathrm e^{\mathrm i\,2\pi \frac{n}N}</math>
sind <math>N</math>-te [[Einheitswurzel]]n, d. h., sie sind Lösungen der Gleichung <math>q^N=1</math>. Sei <math>q:=\mathrm e^{2\pi\,i/N}</math> die „kleinste“, also primitive Wurzel im ersten Quadranten. Diese genügt folgender Identität geometrischer Summen von Einheitswurzeln
:<math>\displaystyle \sum_{k=0}^{N-1} q^{nk}=N\delta_{0,n}</math> mit <math>n=0,\dotsc,N-1</math>
wegen
<math>\displaystyle \sum_{k=0}^{N-1} x^k=\frac{x^N-1}{x-1}</math> für <math>x\ne1</math>.

Dieses ist der „tiefe Grund“, weshalb die inverse DFT funktioniert.

Definieren wir in <math>\mathbb C^N</math> die Vektoren
:<math>f_n:=(\mathrm e^{\mathrm i2\pi\frac{nk}N})_{k=0,\dots,N-1}</math> für <math>n=0,\dotsc,N-1,</math>
so bilden diese eine [[Orthonormalbasis|orthonormale Basis]] zum Skalarprodukt
:<math>
\langle x,y\rangle = \frac1N\sum_{k=0}^{N-1}x_k\bar y_k
</math>.

Es gilt
:<math>
\langle f_n,f_m\rangle = \frac1N\sum_{k=0}^{N-1}\mathrm e^{\mathrm i2\pi\frac{(n-m)k}N}=\delta_{n,m}=\begin{cases}1&n=m\\0&n\ne m\end{cases}
</math>.

Jeder Vektor <math>x=(x_0,\dotsc,x_{N-1})\in\mathbb C^N</math> kann in der Orthonormalbasis dargestellt werden:
:<math>
\displaystyle x=\sum_{n=0}^{N-1} \langle x,f_n \rangle \cdot f_n
</math>.

Die Koeffizienten <math>\langle x,f_n\rangle</math> heißen (auch allgemein bei beliebigem Orthonormalsystem) ''Fourier-Koeffizienten,'' die DFT ordnet also einem Vektor <math>x</math> bis auf eine additive Konstante den Vektor <math>X=\operatorname{DFT}(x)</math> der Fourier-Koeffizienten zu.

Ist <math>Y=\operatorname{DFT}(y)</math> mit einem weiteren Vektor <math>y=(y_0,\dotsc,y_{N-1})\in\mathbb C^N</math>, so gilt die [[Parsevalsche Gleichung]] für Fourier-Koeffizienten:
:<math>
\langle x,y\rangle=\sum_{n=0}^{N-1}\langle x,f_n\rangle\langle f_n,y\rangle=\sum_{n=0}^{N-1}X_n\bar Y_n
</math>.

== Interpretationen der DFT ==
=== [[Diskretisierung]] der Fourier-Transformation ===
Die [[Fourier-Transformation]] erlaubt es, sich Funktionen mit reellem Argument (und diversen Einschränkungen wie: [[Lebesgue-Integral|Integrabilität]], Periodizität oder Abfall im Unendlichen) aus Schwingungen zusammengesetzt zu denken:
:<math>
f(t)= \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^\infty \hat f(\omega) \mathrm e^{\mathrm i \omega t} \, \mathrm d \omega
</math>
Eine wichtige Erkenntnis der Fouriertheorie ist, dass die Amplitude <math>\hat f(\omega)</math> sich ähnlich bestimmen lässt zu
:<math>
\hat f(\omega)= \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^\infty f(t) \mathrm e^{-\mathrm i \omega t} \, \mathrm d t.
</math>

Wählen wir einen Radius <math>R</math> so groß, dass außerhalb des Intervalls <math>[-R,R]</math> nur noch ein unwesentlicher Teil von <math>f</math> liegt, ist <math>f</math> außerdem stetig und eine Zahl <math>N</math> so groß gewählt, dass <math>T:=R/N</math> klein genug ist, um <math>f</math> sinnvoll singulär, d. h. durch Funktionswerte <math>f(kT)</math>, abzutasten, so kann das Fourierintegral in der Transformationsformel sinnvoll durch eine Summe ersetzt werden:
:<math>
\hat f(\omega)\approx F(\omega)=\frac{1}{\sqrt{2 \pi}} \sum_{k=-N}^N \mathrm e^{-\mathrm i \omega kT}f(kT) \,T
</math>
Das entspricht, bis auf einen konstanten Faktor <math>T/\sqrt{2 \pi}</math>, der Berechnungsformel der DFT. Der Vektor <math>x=( f(-NT),\dotsc,f(NT))</math> hat <math>2N+1</math> Elemente. Wir wissen bereits, dass es ausreicht, die Frequenzkoeffizienten für die <math>2N+1</math> Frequenzen <math>\omega_n:=2\pi\cdot \frac{n}{(2N+1)T}</math> mit <math>n=-N,\dotsc,-1,0,1,\dotsc,N</math> zu bestimmen, um die Funktionswerte im Vektor <math>x</math> zu rekonstruieren. Mit der notwendigen Anpassung der Konstanten in der iDFT erhalten wir
:<math>
f(nT)=\frac{1}{\sqrt{2 \pi}}\sum_{k=-N}^N \mathrm e^{\mathrm i \omega_k nT}F(\omega_k)\,\frac{2\pi}{(2N+1)T}.
</math>
Der Diskretisierungsabstand im Frequenzbereich ist proportional zu <math>1/R</math>, also nach Voraussetzung ebenfalls klein, sodass diese Berechnung der Diskretisierung der inversen Fourier-Transformation entspricht.

Beim Übergang von der Fourier-Transformation zur DFT sind also folgende Veränderungen zu bemerken:
* Das Signal liegt zu [[Diskretheit|diskreten]], [[Äquidistanz (Mathematik)|äquidistanten]] Zeitpunkten vor (<math>T=</math> Abstand zweier aufeinanderfolgender Zeitpunkte), <math>0</math> ist einer dieser Zeitpunkte.
* Das Signal hat eine endliche Länge (<math>2N+1=</math> Anzahl der Werte), die als Werte innerhalb eines großen Intervalls <math>[-NT,NT]</math> interpretiert werden.
* Die Integrale bei der Berechnung der Fourier-Koeffizienten werden bei der DFT zu Summen.
* Das Spektrum wird nur für eine endliche Anzahl von (Kreis-)Frequenzen berechnet <math>\omega=2\pi n/((2N+1)T)</math> mit <math>n=-N,\dotsc,-1,0,1,2,\dotsc,N</math> und ist periodisch in der Frequenz, wobei die Periode <math>2\pi/T</math> nach Voraussetzung (<math>T</math> klein) sehr groß ist.

=== Diskretisierung von Fourier-Reihen ===
Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode <math>L</math> kann als [[Funktionenreihe]] mit Sinusoiden, die Bruchteile von <math>L</math> als Periode haben, dargestellt werden (sogenannte [[Fourier-Reihe]]n):
:<math>f(t)=\sum_{n\in\mathbb Z} c_n(f)\mathrm e^{\mathrm{i}\cdot \omega_nt}</math> mit <math>\omega_n=\frac{2\pi n}{L}</math>

Brechen wir die Reihenentwicklung bei großen Grenzen <math>1-M</math> unten und <math>N-M</math> oben ab, so erhalten wir mit <math>T:=L/N</math>
:<math>
f(t_k)=f(kT)\approx \sum_{n=1-M}^{N-M} c_n(f)\mathrm e^{2\pi \mathrm{i}\cdot \frac{nk}{N}},
</math>
d. h., wir erhalten eine Form der inversen DFT. Damit können die Koeffizienten mittels DFT approximiert werden zu
:<math>
c_n(f)\approx\frac{1}{L}\sum_{k=0}^{N-1} f(kT)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi nk}{N}}\cdot \frac{L}{N}=\frac{1}{L}\sum_{k=0}^{N-1} f(t_k)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi n}{L}t_k}\cdot T.
</math>

Im Grenzfall eines unendlich großen <math>N</math> ergeben sich die bekannten Koeffizientenintegrale der Fourier-Reihen:
:<math>
c_n(f)=\frac{1}{L}\int_0^L f(t)\mathrm e^{-\mathrm{i}\cdot \frac{2\pi n}{L}t}\, \mathrm d t
</math>

=== Ausgleichsrechnung mit trigonometrischen Funktionen ===
Das Ergebnis einer DFT-Berechnung kann auch als eine Modellierung des Originalsignals mit Hilfe von trigonometrischen Fubktionen interpretiert werden. Ein verständlicher Nachweis der Relation zwischen Ausgleichsrechnung (Methode der kleinsten Fehlerquadrate) und der diskreten Fourier-Transformation findet sich in <ref>Tilo Strutz: Explaining the Discrete Fourier Transform of real signals based on the least-squares approximation of time-discrete signals using trigonometric functions. 2017, TECHP/2017/11, [http://dx.doi.org/10.13140/RG.2.2.34597.81126 "DOI: 10.13140/RG.2.2.34597.81126"], [https://www.researchgate.net/publication/321075372_Explaining_the_Discrete_Fourier_Transform_of_real_signals_based_on_the_least-squares_approximation_of_time-discrete_signals_using_trigonometric_functions "PDF"]</ref>.

[https://www.bundestag.de/abgeordnete18/biografien/M/merkel_angela/258788 ''Dr. Angela Merkel, CDU/CSU – Biografie.'']

== Eigenschaften ==
=== Spektrum abgetasteter Funktionen ===
[[Datei:Dft spektrum.jpg|mini|Abb. 1: Betrag und Phase des Spektrums eines abgetasteten Signals]]

Die diskrete Fourier-Transformation besitzt ein periodisches Spektrum, es wiederholt sich mit der Abtastfrequenz und ist symmetrisch zur Abtastfrequenz. Es gilt:
:<math>
F\left(\omega+\frac{2 \pi}{T} m\right)= C\sum_{k = 0}^{N - 1} f(kT) \mathrm e^{-\mathrm{i} \omega kT}\mathrm e^{-\mathrm{i} \frac{2 \pi}{T}mkT}= F(\omega)
</math> (wegen <math>\mathrm e^{-\mathrm{i} 2 \pi m k}=1</math> für natürliche Zahlen <math>m</math> und <math>k</math>)
:<math>
F\left(\frac{2 \pi}{T}-\omega\right)= C\sum_{k = 0}^{N - 1} f(kT) \mathrm e^{-\mathrm{i} \frac{2\pi}{T} kT} \mathrm e^{+\mathrm{i} \omega kT}= F^{*}(\omega)
</math>

Enthält das abgetastete Signal Frequenzanteile oberhalb der halben Abtastfrequenz, überlappen sich die Spektren des ursprünglichen Signals mit den an der Abtastfrequenz gespiegelten Signalanteilen, und es kommt zum Alias-Effekt.

=== Alias-Effekt ===
{{Hauptartikel|Alias-Effekt}}

In der Regel entsteht das zeitdiskrete Signal durch [[Abtastung (Signalverarbeitung)|Diskretisierung]] eines kontinuierlichen Signals. Die durch die DFT entstehenden Spektren sind nur dann mit den Spektren des zugrundeliegenden kontinuierlichen Signals identisch, wenn bei der Abtastung das [[Nyquist-Shannon-Abtasttheorem|Abtasttheorem]] nicht verletzt wurde. Für Signale im [[Basisband]] muss gelten, dass die Abtastfrequenz mehr als doppelt so groß ist wie die maximal auftretende Frequenz ([[Nyquist-Frequenz]]). Bei Verletzung des Abtasttheorems tritt eine Verfälschung des Originalsignals auf (Aliasing im Zeitbereich). Eine Möglichkeit des [[Antialiasing (Signalverarbeitung)|Antialiasing]] ist die Bandbegrenzung des Signals am Eingang des Systems, um diesen Effekt zu vermeiden.

=== DFT einer zeitbegrenzten Funktion ===
Für periodische Funktionen ergibt sich (analog zur kontinuierlichen [[Fourier-Transformation]]) ein Linienspektrum mit einem Frequenzlinienabstand von 1/Periodenlänge.

[[Datei:Rechteckfenster Spektrum.jpg|mini|Abb. 2: Fourier-Transformierte eines Rechteck-Fensters]]
Eine zeitbegrenzte diskrete Funktion <math>g(kT)</math> kann man aus einer periodischen diskreten Funktion <math>f(kT)</math> ableiten, indem man über ein Zeitfenster <math>w(t)</math> genau eine Periode herausschneidet:
:<math>
g(kT) = f(kT) \cdot w(t)
</math>

Da bei der Fourier-Transformation eine Multiplikation von Funktionen im Zeitbereich einer [[Faltung (Mathematik)|Faltung]] der Fourier-Transformierten im Frequenzbereich entspricht, ergibt sich die DFT der zeitbegrenzten Funktion <math>G(\omega)</math> durch die Faltung der DFT der periodischen Funktion <math>F(\omega)</math> mit der Fourier-Transformierten des Zeitfensters <math>W(\omega)</math>:
:<math>
G(\omega) = F(\omega) \star W(\omega)
</math>

[[Datei:Dft spektrum fenster.jpg|mini|Abb. 3: Zusammensetzung des Spektrums einer zeitbegrenzten Funktion]]

Als Ergebnis erhält man ein Linienspektrum, das durch die Fourier-Transformierte des Zeitfensters ''verschmiert'' ist. In Abb. 3 rechts gestrichelt dargestellt ist der Einfluss des Zeitfensters auf die DFT der periodischen Funktion (dicke Linien). Durch die Zeitbegrenzung kommen Frequenzanteile zwischen den analysierten Frequenzlinien hinzu.

Durch den Übergang von einer periodischen Funktion auf eine zeitbegrenzte Funktion muss nicht das Rechenverfahren zur Bestimmung des Spektrums verändert werden. Es werden weiterhin diskrete Frequenzlinien berechnet, als ob eine periodische Funktion dahinterstände. Als Effekt des Zeitfensters steht nun jede berechnete Frequenzlinie stellvertretend für einen ganzen Frequenzbereich, nämlich für den Frequenzbereich, der durch die Fourier-Transformierte des Zeitfensters hinzugekommen ist. Dieses Verhalten bezeichnet man auch als ''Leck-Effekt.''

=== Leck-Effekt (Leakage effect) ===
{{Hauptartikel|Leck-Effekt}}

Aufgrund der zeitlichen Begrenzung des Signals kann es dazu kommen, dass das Eingangssignal abgeschnitten wird. Ein abgeschnittenes Eingangssignal kann nur dann korrekt mit der DFT transformiert werden, wenn es periodisch fortsetzbar ist. Falls das Signal nicht periodisch fortsetzbar ist, enthält es Frequenzen, die nicht zu den von der DFT berechneten diskreten Frequenzen gehören. Die DFT „nähert“ diese Frequenzen durch die benachbarten Frequenzen an, dabei wird die Energie auf diese Frequenzen verteilt. Dies wird als Leck-Effekt (englisch {{lang|en|leakage effect}}) bezeichnet.

Die zeitliche Begrenzung kommt einer Multiplikation mit einer [[Rechteckfunktion]] gleich und entspricht einer Faltung mit der [[si-Funktion]] im Frequenzbereich. Dies ist eine andere Betrachtungsweise, um den Leck-Effekt zu erklären. Das gilt natürlich auch im Falle anderer [[Fensterfunktion]]en (z. B. Hamming, von Hann, Gauss). Somit ist das Spektrum der Fensterfunktion (bzw. die Breite des Spektrums) ausschlaggebend für das Leck. Die Amplitudengenauigkeit ist das andere Kriterium einer Fensterfunktion.

=== Gleitende DFT als Bandfilterbank ===
Eine DFT einer zeitbegrenzten Funktion kann man auch als Bandfilterbank ansehen.
* Die Mittenfrequenzen dieser Bandfilter entsprechen den Frequenzlinien der Funktion, die entsteht, wenn man den betrachteten Zeitabschnitt periodisch wiederholt (Vielfache von 1/Fensterbreite).
* Die Breite und [[Flankensteilheit]] der Bandfilter wird durch die Fourier-Transformierten des Zeitfensters bestimmt (siehe Abb. 3).

Durch die Wahl einer geeigneten Zeitfenster-Funktion kann man die Eigenschaften der Bandfilter verändern.
* Bei einem rechteckförmigen Zeitfenster mit Unstetigkeitsstellen an den Fenstergrenzen werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz abgeschwächt; man erzielt Flankensteilheiten von 6 dB/Oktave (siehe Abb. 2).
* Ist die Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz<sup>2</sup> abgeschwächt; man erzielt Flankensteilheiten von 12 dB/Oktave.
* Ist die 1. Ableitung der Fensterfunktion stetig, werden Frequenzen außerhalb des Übertragungsbereichs des Bandfilters mit 1/Frequenz<sup>3</sup> abgeschwächt; die Flankensteilheit beträgt 18 dB/Oktave.
* usw.

Bestimmt man die Fourier-Transformierte von jeweils aufeinanderfolgenden Zeitabschnitten, erhält man die '''gleitende Fourier-Transformation.''' Mit der Analyse eines neuen Zeitabschnitts erhält man dann neue Abtastwerte für den Zeitverlauf der Spektrallinien (das heißt den Zeitverlauf der Signale an den Ausgängen der „Bandfilter“).

=== Unschärfe-Relation der gleitenden DFT ===
Zeit- und Frequenzauflösung der gleitenden DFT können nicht unabhängig voneinander gewählt werden.
* Will man Signale mit hoher [[Frequenzauflösung]] analysieren, muss man die Zeitfenster sehr groß machen, man erhält eine geringe Zeitauflösung.
* Benötigt man eine hohe Zeitauflösung, muss man die Breite der Zeitfenster sehr kurz machen, dann kann man aber nur wenige Frequenzlinien bestimmen.
* Es gilt: Frequenzauflösung ≈ 1/Zeitfensterbreite (wird eine Frequenzauflösung von 1 kHz gewünscht, muss das Zeitfenster mindestens 1 ms lang sein).

== FFT ==
Für Blocklängen <math>N</math>, die sich als Potenz von 2 darstellen lassen, kann die Berechnung mit dem Algorithmus der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] (FFT) erfolgen. Allgemein gilt: Kann die Blocklänge faktorisiert werden, <math>N=KM</math>, so gibt es eine Zerlegung der DFT der Länge <math>N</math> in ein Produkt von DFTs der Längen <math>K</math> und <math>M</math> sowie zweier einfacher Matrizen.

== Goertzel-Algorithmus ==
Für beliebige Blocklängen <math>N</math> und zur Bestimmung einer einzigen oder einiger weniger spektraler Komponenten kann auch der [[Goertzel-Algorithmus]] verwendet werden. Der Vorteil besteht in einer sehr effizienten Implementierung in Computersystemen, da die Berechnung pro Spektralkomponente nur eine komplexe Multiplikation und zwei komplexe Additionen umfasst.

== Anwendungen ==
* Berechnung der Fourier-Transformierten eines Signals
* [[Signalanalyse]]
* [[Schwingungsanalyse]] und [[Modalanalyse]]
* Bearbeitung von Signalen
* Berechnung von [[Korrelation]]en
* Berechnung von Polynomprodukten in <math>\mathcal{O}(n \cdot \log(n))</math>

Bei der Berechnung von [[Oberflächenwellenfilter]]n (= 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.

== Siehe auch ==
* [[Faltung (Mathematik)|Faltung]]
* [[Gabor-Transformation]]
* [[Laplace-Transformation]]
* [[z-Transformation]]
* [[Diskrete Kosinustransformation]]
* [[Wavelet-Transformation]]
* [[Fensterfunktion]]
* [[Fourierreihe]]
* [[Short-Time-Fourier-Transformation]]

== Literatur ==

[[Kategorie:Digitale Signalverarbeitung]]
[[Kategorie:Diskrete Transformation]]

[[cs:Fourierova transformace#Diskrétní Fourierova transformace]]
[[fi:Fourier'n muunnos#Diskreetti Fourier'n muunnos]]
[[pt:Transformada de Fourier#Transformada discreta de Fourier]]