Diskrete Fourier-Transformation - de.LinkFang.org

Diskrete Fourier-Transformation

Die Diskrete Fourier-Transformation (DFT) ist eine Transformation aus dem Bereich der Fourier-Analysis. 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 (englisch fast Fourier transform, FFT) und ihrer Inversen angewandt.

Die DFT wird in der Signalverarbeitung für viele Aufgaben verwendet, so z. B.

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 discrete-time Fourier transform, DTFT) zu unterscheiden, die aus zeitdiskreten Signalen ein kontinuierliches Frequenzspektrum bildet.

Inhaltsverzeichnis

Definition


Die diskrete Fourier-Transformation verarbeitet eine Folge von Zahlen \({\displaystyle a=(a_{0},\dotsc ,a_{N-1})}\), die zum Beispiel als zeitdiskrete Messwerte entstanden sind. Dabei wird angenommen, dass diese Messwerte einer Periode eines periodischen Signals entsprechen.

Das Ergebnis der Transformation ist eine Zerlegung der Folge in harmonische (Sinus-ähnliche) Anteile, sowie einen "Gleichanteil" \({\displaystyle {\hat {a}}_{0}}\), der dem Mittelwert der Eingangsfolge entspricht. Das Ergebnis nennt man "diskrete Fourier-Transformierte" \({\displaystyle {\hat {a}}=({\hat {a}}_{0},\dotsc ,{\hat {a}}_{N-1})\in \mathbb {C} ^{N}}\) von a. Die Koeffizienten von \({\displaystyle {\hat {a}}}\) sind die Amplituden der Zerlegungs-Anteile.

Aus der Summe dieser Amplituden (Zerlegungsanteile) lässt sich umgekehrt wiederum die Eingangsfolge ermitteln (inverse Transformation).

Die Einträge der Folge a werden durch die Transformation in die Werte \({\displaystyle a_{k}=A(z_{k})}\) eines Polynoms

\({\displaystyle A(z)={\tfrac {1}{N}}\left({\hat {a}}_{0}+{\hat {a}}_{1}z+\dots +{\hat {a}}_{N-1}z^{N-1}\right)}\)

mit komplexen Koeffizienten gewandelt. Als Argumente \({\displaystyle z_{0},z_{1},\dotsc ,z_{N-1}}\) werden \({\displaystyle N}\) Punkte auf dem Einheitskreis der komplexen Zahlenebene gewählt, die gleichmäßig verteilt sind, d. h. die \({\displaystyle N}\)–ten Einheitswurzeln

\({\displaystyle z_{k}=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)}\).

Wird nun das Polynom \({\displaystyle A(z)}\) mit einer gleichmäßig den Einheitskreis umlaufenden Funktion \({\displaystyle z(t)=e^{\mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}}\) verknüpft, so ergibt sich eine zeitkontinuierliche periodische Funktion

\({\displaystyle f(t)=A(z(t))={\tfrac {1}{N}}\left({\hat {a}}_{0}+{\hat {a}}_{1}e^{\mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}+{\hat {a}}_{2}e^{2\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}+\dotsb +{\hat {a}}_{N-1}e^{(N-1)\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}\right),}\)

die zu den Zeiten \({\displaystyle t_{k}=t_{0}+{\tfrac {k}{N}}T}\) gerade die Funktionswerte \({\displaystyle a_{k}=A(z_{k})}\) annimmt.

Die Potenzen von \({\displaystyle z(t)}\) haben die Gestalt

\({\displaystyle z(t)^{k}=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}})}\)

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

Diese oben angegebene Interpolationsfunktion ist nicht die einzige, die sich auf diese Art konstruieren lässt. Jede der Funktionen

\({\displaystyle {\begin{matrix}f(t)={\frac {1}{N}}&\left({\hat {a}}_{0}+{\hat {a}}_{1}e^{\mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}+{\hat {a}}_{2}e^{2\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}+\dots +{\hat {a}}_{M-1}e^{(M-1)\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}\right.\\&\left.+{\hat {a}}_{M}e^{(M-N)\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}+\dots +{\hat {a}}_{N-1}e^{(N-1-N)\cdot \mathrm {i} 2\pi {\frac {t-t_{0}}{T}}}\right)\end{matrix}}}\)

hat diese Interpolationseigenschaft.

DFT und iDFT für einen komplexen Vektor

Die diskrete Fourier-Transformierte \({\displaystyle {\hat {a}}=({\hat {a}}_{0},\dotsc ,{\hat {a}}_{N-1})\in \mathbb {C} ^{N}}\) eines komplexen Vektors \({\displaystyle a=(a_{0},\dotsc ,a_{N-1})\in \mathbb {C} ^{N}}\) hat die Koeffizienten

\({\displaystyle {\hat {a}}_{k}=\sum _{j=0}^{N-1}e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot a_{j}}\) für \({\displaystyle k=0,\dotsc ,N-1}\).

Dabei nennt man die \({\displaystyle {\hat {a}}_{k}}\) auch Fourierkoeffizienten oder Fourierkomponenten.

Die inverse DFT (iDFT) \({\displaystyle a}\) von \({\displaystyle {\hat {a}}\in \mathbb {C} ^{N}}\) hat die Koeffizienten

\({\displaystyle a_{k}={\frac {1}{N}}\sum _{j=0}^{N-1}e^{2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot {\hat {a}}_{j}}\) für \({\displaystyle k=0,\dotsc ,N-1}\).

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 (\({\displaystyle g(-{\vec {x}})={\overline {g({\vec {x}})}}}\)) im Frequenzraum:

\({\displaystyle {\hat {a}}_{N-k}={\overline {{\hat {a}}_{k}}}}\)

Dies bedeutet, dass im Frequenzraum nur \({\displaystyle N/2}\) unabhängige komplexe Koeffizienten \({\displaystyle {\hat {a}}_{k}}\) 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 \({\displaystyle N}\) (wie bei der vollen DFT), sondern nur \({\displaystyle N/2}\) komplexe Zahlen nötig. Die anderen \({\displaystyle N/2}\) komplexen Zahlen können durch elementare Rechnung rekonstruiert werden (siehe Formel oben). Die hermitesche Symmetrie bezieht sich auf das mittlere Element \({\displaystyle k=N/2}\) des Signals \({\displaystyle {\hat {a}}_{k}}\).

Beweis: Wegen der Eulerschen Identität \({\displaystyle e^{2\pi \mathrm {i} }=1}\) und wegen \({\displaystyle {\overline {e^{\mathrm {i} \phi }}}=e^{-\mathrm {i} \phi }}\) gilt im reellen Fall \({\displaystyle a\in \mathbb {R} ^{N}}\):
\({\displaystyle {\hat {a}}_{N-k}=\sum _{j=0}^{N-1}e^{-2\pi \mathrm {i} \cdot {\frac {Nj}{N}}}e^{2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot a_{j}=\sum _{j=0}^{N-1}{\overline {e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot a_{j}}}={\overline {{\hat {a}}_{k}}}}\)

Umgekehrt gilt entsprechend: Erfüllt \({\displaystyle {\hat {a}}\in \mathbb {C} ^{N}}\) die Bedingung \({\displaystyle {\hat {a}}_{N-k}={\overline {{\hat {a}}_{k}}}}\) für alle \({\displaystyle k=1,\dotsc ,N-1}\) sowie \({\displaystyle {\hat {a}}_{0}\in \mathbb {R} }\), so ist die inverse DFT ein reeller Vektor \({\displaystyle a\in \mathbb {R} ^{N}}\).

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 \({\displaystyle R}\) ein kommutativer unitärer Ring, in dem die Zahl \({\displaystyle N}\) (das ist die \({\displaystyle N}\)-fache Summe der \({\displaystyle 1}\)) eine Einheit ist. Des Weiteren gebe es in \({\displaystyle R}\) eine primitive \({\displaystyle N}\)-te Einheitswurzel \({\displaystyle w}\). Zu einem Tupel \({\displaystyle a=(a_{0},\dotsc ,a_{N-1})\in R^{N}}\) ist dann die diskrete Fouriertransformierte \({\displaystyle {\hat {a}}}\) durch

\({\displaystyle {\hat {a}}_{k}=\sum _{j=0}^{N-1}w^{-\,j\cdot k}\cdot a_{j}}\) für \({\displaystyle k=0,\dotsc ,N-1}\)

erklärt. Unter den getroffenen Voraussetzungen existiert damit zu \({\displaystyle {\hat {a}}\in R^{N}}\) auch die diskrete inverse Fouriertransformierte \({\displaystyle a}\) mit den Koeffizienten

\({\displaystyle a_{k}={1 \over N}\sum _{j=0}^{N-1}w^{j\cdot k}\cdot {\hat {a}}_{j}}\) für \({\displaystyle k=0,\dotsc ,N-1}\).

Im überaus wichtigen Spezialfall \({\displaystyle R=\mathbb {C} }\) wird für die DFT üblicherweise die \({\displaystyle N}\)-te Einheitswurzel \({\displaystyle w=\exp \left(2\pi \,\mathrm {i} /N\right)}\) 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:

\({\displaystyle {\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}}}}\) für \({\displaystyle k=0,\dotsc ,M-1}\) und \({\displaystyle l=0,\dotsc ,N-1}\)

Die Rücktransformation lautet entsprechend:

\({\displaystyle a_{m,n}={\frac {1}{MN}}\sum _{k=0}^{M-1}\sum _{l=0}^{N-1}{\hat {a}}_{k,l}\cdot e^{2\pi \mathrm {i} \cdot {\frac {mk}{M}}}e^{2\pi \mathrm {i} \cdot {\frac {nl}{N}}}}\) für \({\displaystyle m=0,\dotsc ,M-1}\) und \({\displaystyle n=0,\dotsc ,N-1}\)

Verschiebung und Skalierung in Zeit und Frequenz


In den Berechnungsformeln von DFT und iDFT kann die Summation (Indexvariable \({\displaystyle j}\) oben) statt über \({\displaystyle 0,\dotsc ,N-1}\) ebenso über einen verschobenen Bereich \({\displaystyle k,\dotsc ,N-1+k}\) laufen, wenn der Vektor \({\displaystyle \textstyle a=(a_{0},\dotsc ,a_{N-1})}\) periodisch auf alle ganzzahligen Indizes fortgesetzt wird, denn es gilt \({\displaystyle \textstyle w^{N+k}=w^{k}}\). Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge \({\displaystyle N}\) 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,

\({\displaystyle t_{n}:=nT}\) für \({\displaystyle n=1-M,\cdots ,N-M}\),

die ebenfalls die Länge \({\displaystyle N}\) hat. Auch ist es wünschenswert, den berechneten Koeffizienten Frequenzen zuzuordnen, die um \({\displaystyle 0}\) zentriert sind,

\({\displaystyle \omega _{n}:=2\pi {\frac {n}{NT}}}\) für \({\displaystyle n=1-K,\dotsc ,N-K}\)

und \({\displaystyle K}\) in der Nähe von \({\displaystyle N/2}\).

Eine zu den gewählten Zeitpunkten „gemessene“ Funktion \({\displaystyle f}\) ergibt den Beobachtungsvektor \({\displaystyle \textstyle x\in \mathbb {C} ^{N}}\) mit den Koeffizienten \({\displaystyle \textstyle x_{n}=f(t_{n})}\), dessen DFT \({\displaystyle \textstyle y_{n}={\hat {f}}(\omega _{n})=F(\omega _{n})}\) in der Fourier-Analyse betrachtet wird. Dann ist

\({\displaystyle F(\omega _{n})=\sum _{k=1-M}^{N-M}e^{-2\pi \mathrm {i} {\frac {nkT}{NT}}}x_{k}=\sum _{k=1-M}^{N-M}e^{-\mathrm {i} \,\omega _{n}\cdot t_{k}}f(t_{k})}\)

und

\({\displaystyle f(t_{n})=x_{n}={\frac {1}{N}}\sum _{k=1-K}^{N-K}e^{2\pi \mathrm {i} {\frac {nkT}{NT}}}y_{k}={\frac {1}{N}}\sum _{k=1-K}^{N-K}e^{\mathrm {i} \omega _{k}\cdot t_{n}}F(\omega _{k})}\).

Beispiele


Die Fourier-Transformation transformiert eine Funktion \({\displaystyle f(t)}\) nach \({\displaystyle g(v)^{*}}\) von einer Zeitdarstellung \({\displaystyle t}\) in den reziproken Frequenzraum \({\displaystyle v:=1/t}\). 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

Die Bilder rechts veranschaulichen zweidimensionale Fourier-Transformationen (2D FFT) an geometrischen Mustern, gerechnet für Quadrate der diskreten Größe von \({\displaystyle a\times a}\) Pixeln. Das Bild oben links zeigt einen Spalt der Größe \({\displaystyle e\times f}\) Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable \({\displaystyle r}\) wird überführt in reziproke komplexe Werte \({\displaystyle r^{*}}\). Bei den gewählten Größen wird ein Pixel auf den reziproken Wert von \({\displaystyle 1/a}\) reziproken Pixeln überführt. Die Breite des Spalts von \({\displaystyle e}\) Pixeln erscheint im Reziprokraum als Wert der Größe \({\displaystyle r^{*}=a/e}\), die Höhe \({\displaystyle r^{*}=a/f}\), mit harmonischen Frequenzen höherer Ordnung. Die berechneten Beugungsbilder geben die Intensitätsverteilungen der komplexen Größe \({\displaystyle r^{*}}\) 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

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 Grundlage


Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen

\({\displaystyle e^{i\,2\pi {\frac {n}{N}}}}\)

sind \({\displaystyle N}\)-te Einheitswurzeln, d. h., sie sind Lösungen der Gleichung \({\displaystyle q^{N}=1}\). Sei \({\displaystyle q:=e^{2\pi \,i/N}}\) die „kleinste“, also primitive Wurzel im ersten Quadranten. Diese genügt folgender Identität geometrischer Summen von Einheitswurzeln

\({\displaystyle \displaystyle \sum _{k=0}^{N-1}q^{nk}=N\delta _{0,n}}\) mit \({\displaystyle n=0,\dotsc ,N-1}\)

wegen \({\displaystyle \displaystyle \sum _{k=0}^{N-1}x^{k}={\frac {x^{N}-1}{x-1}}}\) für \({\displaystyle x\neq 1}\).

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

Definieren wir in \({\displaystyle \mathbb {C} ^{N}}\) die Vektoren

\({\displaystyle f_{n}:=(e^{i2\pi {\frac {nk}{N}}})_{k=0,\dots ,N-1}}\) für \({\displaystyle n=0,\dotsc ,N-1,}\)

so bilden diese eine orthonormale Basis zum Skalarprodukt

\({\displaystyle \langle x,y\rangle ={\frac {1}{N}}\sum _{k=0}^{N-1}x_{k}{\bar {y}}_{k}}\).

Es gilt

\({\displaystyle \langle f_{n},f_{m}\rangle ={\frac {1}{N}}\sum _{k=0}^{N-1}e^{i2\pi {\frac {(n-m)k}{N}}}=\delta _{n,m}={\begin{cases}1&n=m\\0&n\neq m\end{cases}}}\).

Jeder Vektor \({\displaystyle x=(x_{0},\dotsc ,x_{N-1})\in \mathbb {C} ^{N}}\) kann in der Orthonormalbasis dargestellt werden:

\({\displaystyle \displaystyle x=\sum _{n=0}^{N-1}\langle x,f_{n}\rangle \cdot f_{n}}\)

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

Ist \({\displaystyle Y=\operatorname {DFT} (y)}\) mit einem weiteren Vektor \({\displaystyle y=(y_{0},\dotsc ,y_{N-1})\in \mathbb {C} ^{N}}\), so gilt die Parsevalsche Gleichung für Fourier-Koeffizienten:

\({\displaystyle \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}}\)

Interpretationen der DFT


Diskretisierung der Fourier-Transformation

Die Fourier-Transformation erlaubt es, sich Funktionen mit reellem Argument (und diversen Einschränkungen wie: Integrabilität, Periodizität oder Abfall im Unendlichen) aus Schwingungen zusammengesetzt zu denken:

\({\displaystyle f(t)={\frac {1}{\sqrt {2\pi }}}\int _{-\infty }^{\infty }{\hat {f}}(\omega )e^{i\omega t}\,\mathrm {d} \omega }\)

Eine wichtige Erkenntnis der Fouriertheorie ist, dass die Amplitude \({\displaystyle {\hat {f}}(\omega )}\) sich ähnlich bestimmen lässt zu

\({\displaystyle {\hat {f}}(\omega )={\frac {1}{\sqrt {2\pi }}}\int _{-\infty }^{\infty }f(t)e^{-i\omega t}\,\mathrm {d} t.}\)

Wählen wir einen Radius \({\displaystyle R}\) so groß, dass außerhalb des Intervalls \({\displaystyle [-R,R]}\) nur noch ein unwesentlicher Teil von \({\displaystyle f}\) liegt, ist \({\displaystyle f}\) außerdem stetig und eine Zahl \({\displaystyle N}\) so groß gewählt, dass \({\displaystyle T:=R/N}\) klein genug ist, um \({\displaystyle f}\) sinnvoll singulär, d. h. durch Funktionswerte \({\displaystyle f(kT)}\), abzutasten, so kann das Fourierintegral in der Transformationsformel sinnvoll durch eine Summe ersetzt werden:

\({\displaystyle {\hat {f}}(\omega )\approx F(\omega )={\frac {1}{\sqrt {2\pi }}}\sum _{k=-N}^{N}e^{-i\omega kT}f(kT)\,T}\)

Das entspricht, bis auf einen konstanten Faktor \({\displaystyle T/{\sqrt {2\pi }}}\), der Berechnungsformel der DFT. Der Vektor \({\displaystyle x=(f(-NT),\dotsc ,f(NT))}\) hat \({\displaystyle 2N+1}\) Elemente. Wir wissen bereits, dass es ausreicht, die Frequenzkoeffizienten für die \({\displaystyle 2N+1}\) Frequenzen \({\displaystyle \omega _{n}:=2\pi \cdot {\frac {n}{(2N+1)T}}}\) mit \({\displaystyle n=-N,\dotsc ,-1,0,1,\dotsc ,N}\) zu bestimmen, um die Funktionswerte im Vektor \({\displaystyle x}\) zu rekonstruieren. Mit der notwendigen Anpassung der Konstanten in der iDFT erhalten wir

\({\displaystyle f(nT)={\frac {1}{\sqrt {2\pi }}}\sum _{k=-N}^{N}e^{i\omega _{k}nT}F(\omega _{k})\,{\frac {2\pi }{(2N+1)T}}.}\)

Der Diskretisierungsabstand im Frequenzbereich ist proportional zu \({\displaystyle 1/R}\), 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:

Diskretisierung von Fourier-Reihen

Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode \({\displaystyle L}\) kann als Funktionenreihe mit Sinusoiden, die Bruchteile von \({\displaystyle L}\) als Periode haben, dargestellt werden (sogenannte Fourier-Reihen):

\({\displaystyle f(t)=\sum _{n\in \mathbb {Z} }c_{n}(f)e^{\mathrm {i} \cdot \omega _{n}t}}\) mit \({\displaystyle \omega _{n}={\frac {2\pi n}{L}}}\)

Brechen wir die Reihenentwicklung bei großen Grenzen \({\displaystyle 1-M}\) unten und \({\displaystyle N-M}\) oben ab, so erhalten wir mit \({\displaystyle T:=L/N}\)

\({\displaystyle f(t_{k})=f(kT)\approx \sum _{n=1-M}^{N-M}c_{n}(f)e^{2\pi \mathrm {i} \cdot {\frac {nk}{N}}},}\)

d. h., wir erhalten eine Form der inversen DFT. Damit können die Koeffizienten mittels DFT approximiert werden zu

\({\displaystyle c_{n}(f)\approx {\frac {1}{L}}\sum _{k=0}^{N-1}f(kT)e^{-\mathrm {i} \cdot {\frac {2\pi nk}{N}}}\cdot {\frac {L}{N}}={\frac {1}{L}}\sum _{k=0}^{N-1}f(t_{k})e^{-\mathrm {i} \cdot {\frac {2\pi n}{L}}t_{k}}\cdot T.}\)

Im Grenzfall eines unendlich großen \({\displaystyle N}\) ergeben sich die bekannten Koeffizientenintegrale der Fourier-Reihen:

\({\displaystyle c_{n}(f)={\frac {1}{L}}\int _{0}^{L}f(t)e^{-\mathrm {i} \cdot {\frac {2\pi n}{L}}t}\,\mathrm {d} t}\)

Eigenschaften


Spektrum abgetasteter Funktionen

Die diskrete Fourier-Transformation besitzt ein periodisches Spektrum, es wiederholt sich mit der Abtastfrequenz und ist symmetrisch zur Abtastfrequenz. Es gilt:

\({\displaystyle F\left(\omega +{\frac {2\pi }{T}}m\right)=C\sum _{k=0}^{N-1}f(kT)e^{-\mathrm {i} \omega kT}e^{-\mathrm {i} {\frac {2\pi }{T}}mkT}=F(\omega )}\) (wegen \({\displaystyle e^{-\mathrm {i} mk}=1}\) für natürliche Zahlen \({\displaystyle m}\) und \({\displaystyle k}\))
\({\displaystyle F\left({\frac {2\pi }{T}}-\omega \right)=C\sum _{k=0}^{N-1}f(kT)e^{-\mathrm {i} {\frac {2\pi }{T}}kT}e^{+\mathrm {i} \omega kT}=F^{*}(\omega )}\)

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

In der Regel entsteht das zeitdiskrete Signal durch 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 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 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.

Eine zeitbegrenzte diskrete Funktion \({\displaystyle g(kT)}\) kann man aus einer periodischen diskreten Funktion \({\displaystyle f(kT)}\) ableiten, indem man über ein Zeitfenster \({\displaystyle w(t)}\) genau eine Periode herausschneidet:

\({\displaystyle g(kT)=f(kT)\cdot w(t)}\)

Da bei der Fourier-Transformation eine Multiplikation von Funktionen im Zeitbereich einer Faltung der Fourier-Transformierten im Frequenzbereich entspricht, ergibt sich die DFT der zeitbegrenzten Funktion \({\displaystyle G(\omega )}\) durch die Faltung der DFT der periodischen Funktion \({\displaystyle F(\omega )}\) mit der Fourier-Transformierten des Zeitfensters \({\displaystyle W(\omega )}\):

\({\displaystyle G(\omega )=F(\omega )\star W(\omega )}\)

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)

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

Durch die Wahl einer geeigneten Zeitfenster-Funktion kann man die Eigenschaften der Bandfilter verändern.

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.

FFT


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

Goertzel-Algorithmus


Für beliebige Blocklängen \({\displaystyle N}\) 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


Bei der Berechnung von Oberflächenwellenfiltern (= OFW-Filter = SAW-Filter = surface acoustic wave–filter) wird die Invers–Fouriertransformierte der Übertragungsfunktion benötigt (stellt die Impulsantwort dar). Diese Aufgabe wird von Rechnern übernommen.

Siehe auch


Literatur





Kategorien: Digitale Signalverarbeitung | Diskrete Transformation

Werbung:


Quelle: Wikipedia - https://de.wikipedia.org/wiki/Diskrete Fourier-Transformation (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 29.02.2020 09:36:08 CET - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.