Diskrete Fourier-Transformation

Die Diskrete Fourier-Transformation oder DFT ist ein Algorithmus ist die Fourier-Transformierte eines zeitdiskreten endlichen oder periodischen Signals. Die DFT ist das wichtigste Werkzeug in der Praxis der digitalen Signalverarbeitung, da es schnelle Algorithmen zum Durchführen der Transformation gibt, am bekanntesten ist die FFT (Fast Fourier Transformation), die schnellen Fourier-Transformation.

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

• zur näherungsweisen Bestimmung der in einem abgetasteten Signal enthaltenen Frequenzen,
• zur effizienten Implementierung digitaler Filter mit großen Filterlängen.

Mit der inversen DFT (iDFT) kann aus den Frequenzanteilen wiederum das Ausgangssignal rekonstruiert werden. Durch Kopplung von DFT und iDFT kann ein Signal im Frequenzbereich manipuliert werden (Equalizer, Filter).

Was ist die Diskrete Fouriertransformation

Hier soll beschrieben werden, wie die Algorithmen der DFT funktionieren. Auf die Interpretation dieser Algorithmen und einige Anwendungen wird weiter unten eingegangen. Die Implementierungen der DFT, wie z.B. die fft() und ifft()-Funktionen im Computeralgebrasystem MatLab, berechnen die folgenden Ausdrücke.

Algorithmus der DFT

Input: Ein Vektor x von reellen Zahlen der Länge N, x=(x₀,...,x_N-1</sub). Output: Ein Vektor yvon komplexen Zahlen der Länge N, y=(x₀,...,y_N-1</sub).

Es wird berechnet:

$y_{n}=\sum _{k=0}^{N-1}e^{-2\pi i\cdot {\frac {nk}{N}}}\cdot x_{k}$

Es gilt (bei reellem Input) $y_{N-n}={\overline {y_{n}}}$, d.h. zählt man die unabhängigen reellen Zahlen in Real- und Imaginärteil des Output, so ergeben sich wieder N reelle Zahlen im Ergebnis.

Algorithmus der iDFT

Input: Ein Vektor yvon komplexen Zahlen der Länge N, y=(x₀,...,y_N-1</sub). Output: Ein Vektor x von komplexen Zahlen der Länge N, x=(x₀,...,x_N-1</sub).

Es wird berechnet:

$x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}e^{2\pi i\cdot {\frac {nk}{N}}}\cdot y_{k}$

Erfüllt der Input die Bedingung $y_{N-n}={\overline {y_{n}}}$, so hat das Ergebnis immer den Imaginärteil 0, ist also reell.

Verschiebung und Skalierung in Zeit und Frequenz

Beide Berechnungsformeln können auch für ganzzahlige Indizes n außerhalb des Segments 0,...,N-1 ausgeführt werden. Jedoch ergeben sich keine neuen Werte, da die Formeln periodisch mit Periode N sind, d.h. es gilt in der DFT $y_{n+jN}=y_{n}$ und in der iDFT $x_{n+jN}=x_{n}$. Wir können also die Summationsgrenzen beliebig verschieben, solange ein Segment der Länge N überstrichen wird.

In praktischen Anwendungen möchte man die Indizes mit einer äquidistanten Folge von Zeitpunkten verbinden,

$t_{n}:=nT$, n=1-M,...,N-M,

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

$\omega _{n}:=2\pi {\frac {n}{NT}}$, n=1-K,..., N-K,

K in der Nähe von N/2.

Wir bezeichnen $x_{n}=f(t_{n})$ und $y_{n}={\hat {f}}(\omega _{n})=F(\omega _{n})$, um in den Sprachbereich der Fourier-Analyse zu gelangen. Dann ist

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

und

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

Rechen-Beispiele

Die Fourier-Transformation transformiert eine Funktion von einer Zeitdarstellung in einen "reziproken" Frequenzraum. Dies gilt auch für Ortsfunktionen, die auf zwei 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. Nur bei der Holographie wird sie durch einen Trick mit aufgezeichnet.

Wir zeigen Beispiele für eine zweidimensionale Fourier-Transformation an geometrischen Mustern, gerechnet für Quadrate der diskreten Größe von 256x256 Pixeln. Das erste Bild oben links zeigt einen Spalt der Größe 8x32 Pixel, daneben die Intensitätsverteilung des Beugungsbildes. Die Ortsvariable r wird überführt in reziproke (und komplexe) Werte r*. Bei den gewählten Größen wird 1 Pixel auf den reziproken Wert von 512 reziproken Pixeln überführt. Die Breite des Spalts von 8 Pixeln erscheint im Reziprok-Raum als Wert der Größe r*=512/8="64," die Höhe r*=512/32="16," mit harmonischen Frequenzen höherer Ordnung. Die Intensitätsverteilung einer Schnittlinie durch den Bildmittelpunkt reduziert die zweidimensionale Fouriertransformation auf eine eindimensionale. Das Einschub-Bild im unteren Drittel der oberen Bildreihe misst die Intensität entlang einer horizontalen Linie. Links sehen wir die Rechteckfunktion, den Wechsel von Schwarz auf Weiß auf Schwarz. Im Transformationsbild erkennen wir periodische Peaks. Sie entsprechen den Ortsfrequenzen höherer Ordnung eines Rechtecksignals, die unter dem Stichwort Fourieranalyse genauer beschrieben werden (siehe auch das Bild einer kontinuierlichen Rechteck-Fouriertransformation unter Beugungsscheibchen). Im zweiten Bild 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, wirkt sich nur in der Phasenbeziehung aus, die in der gewählten Darstellung als Intensitätsverteilung nicht zu erkennen ist. Das untere Bild zeigt rechts das gerechnete Beugungsmuster eines Dreiecks. Auf den ersten Blick glaubt man ebenfalls eine 6-zählige Symmetrie zu erkennen, wenn man nicht die fehlende Modulation der Beugungslinien beachten würde.

Gerechnete Fourier-Transformationen. Links Ausgangsbild, rechts Intensitätsverteilung der Fouriertransformation. Das kleine Bild zeigt die Intensitätsverteilung einer horizontalen Linie durch den Ursprung der oberen beiden Bilder (siehe Text).

Der nächste Bildblock vergleicht die Beugung zweier Kreisöffnungen. Ein großer Kreis erzeugt ein kleines Beugungsmuster, und umgekehrt. Die Lichtbeugung an der Linsenöffnung begrenzt die Auflösung eines Fernrohrs. Je größer der Durchmesser ist, desto kleiner ist das Beugungsbild eines Sterns, desto besser können nahe beieinander liegende Sterne von einander unterschieden werden. Das untere Bild ist ein Beispiel für eine Beugung an einer Kreis-Struktur ohne scharfe Begrenzung. Die Beugungen höherer Ordnung, die Obertöne, sind deutlich abgeschwächt.

Gerechnete Fourier-Transformationen, zweiter Block. Links Ausgangsbild, rechts Intensitätsverteilung der Fouriertransformation (siehe Text).

Mathematische Grundlage

Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen $q_{n}:=e^{2\pi i\,{\frac {n}{N}}}$ sind N-te Einheitswurzeln, d.h. sie sind Lösungen der Gleichung $q_{n}^{\,N}-1=0$. Als solche genügen sie folgender Identität geometrischer Summen von Einheitswurzeln: $\sum _{k=0}^{N-1}(q_{n})^{k}=N\delta _{0,n}$, n=0,...,N-1, denn $\sum _{k=0}^{N-1}x^{k}={\frac {x^{N}-1}{x-1}}$ für $x\neq 1$. Dies ist der "tiefe Grund", weshalb die inverse DFT funktioniert. Seien ein Block der Länge N eines Signals bzw. ein N-Tupel von Zahlen (Vektoren, Matrizen,...) $x_{0},\dots ,x_{N-1}$ gegeben, so kann man deren DFT als $y_{n}=\sum _{k=0}^{N-1}q_{N-k}^{\,n}\cdot x_{k}$ definieren, aus obiger Identität ergibt sich die Formel der inversen DFT zu $x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}q_{k}^{\,n}\cdot y_{k}$. Man könnte beide Formeln auch symmetrisch gestalten und beidesmal einen Faktor ${\sqrt {1/N}}$ vor die Summe stellen.

Interpretationen der DFT

Diskretisierung der Fourier-Transformation

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

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

Eine wichtige Erkenntnis der Fourier-Theorie ist, dass die Amplitude ${\hat {f}}(\omega )$ sich ähnlich bestimmen läßt zu

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

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

${\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 $T/{\sqrt {2\pi }}$, der Berechnungsformel der DFT. Der Vektor x=( f(-NT), ... ,f(NT) ) hat 2N+1 Elemente. Wir wissen bereits, dass es ausreicht, die Frequenzkoeffizienten für die 2N+1 Frequenzen $\omega _{n}:=2\pi \cdot {\frac {n}{(2N+1)T}}$, n=-N,...,-1,0,1,...,N, zu bestimmen, um die Funktionswerte im Vektor x zu rekonstruieren. Mit der notwendigen Anpassung der Konstanten in der iDFT erhalten wir

$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 1/R, also nach Voraussetzung ebenfalls klein, so dass 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 diskreten, äquidistanten Zeitpunkten vor (T: Abstand zweier aufeinanderfolgender Zeitpunkte), 0 ist einer dieser Zeitpunkte.
• Das Signal hat eine endliche Länge (2N+1: Anzahl der Werte), welche als Werte innerhalb eines großen Intervalls [-NT,NT] 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 (ω = (2 π)·n/(N·T); n = -N,...,-1,0, 1, 2,...,N) und ist periodisch in der Frequenz, wobei die Periode (2 π)/T nach Voraussetzung (T klein) sehr groß ist.

Diskretisierung von Fourier-Reihen

Aber eigentlich brauchen wir die Fourier-Reihen: Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode T kann als Funktionenreihe mit Sinoiden, die Bruchteile von T als Periode haben, dargestellt werden:

$f(t)={\frac {1}{\sqrt {2\pi }}}\sum _{n\in \mathbb {Z} }c_{n}(f)e^{i\cdot {\frac {2\pi n}{T}}t}\cdot {\frac {1}{T}}$

Die Koeffizienten lassen sich durch Integrale bestimmen, die ähnlich wie die der Fourier-Transformation aussehen:

$c_{n}(f)={\frac {1}{\sqrt {2\pi }}}\int _{0}^{T}f(t)e^{-i\cdot {\frac {2\pi n}{T}}t}\,dt$

Eigenschaften

Spektrum abgetasteter Funktionen

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:

$F(\omega +{\frac {2\pi }{T}}m)=C\sum _{k=0}^{N-1}f(kT)e^{-i\omega kT}e^{-i{\frac {2\pi }{T}}mkT}=F(\omega )$

(Denn für natürliche Zahlen m und k gilt: e^{-i2π m k}=1)

$F({\frac {2\pi }{T}}-\omega )=C\sum _{k=0}^{N-1}f(kT)e^{-i{\frac {2\pi }{T}}kT}e^{+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 (sampling-theorem) nicht verletzt wurde. Für Signale im Basisband muss gelten, dass die Abtastfrequenz mehr als doppelt so groß (Nyquist-Frequenz) sein muss, wie die maximal auftretende Frequenz. Bei Verletzung des Abtasttheorems tritt eine Verfälschung des Originalsignals auf (Aliasing im Zeitbereich). Eine Möglichkeit des Anti-Aliasing 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.

Abb.2: Fourier-Transformierte eines Rechteck-Fensters

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

$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 G(ω) durch die Faltung der DFT der periodischen Funktion F(ω) mit der Fourier-Transformierten des Zeitfensters W(ω).

$G(\omega )=F(\omega )\star W(\omega )$

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 bereichnet, als ob eine periodische Funktion dahinter stände. Als Effekt des Zeitfensters steht nun jede berechnete Frequenzlinie stellvertretend für einen ganzen Frequenzbereich, nämlich dem 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 (en: Leakage-Effect) bezeichnet.

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 Rechteck-förmigem Zeitfenster mit Unstetigkeits-Stellen an den Fenster-Grenzen werden Frequenzen außerhalb des Übertragungs-Bereichs des Bandfilters mit 1/Frequenz abgeschwächt; man erzielt Flankensteilheiten von 6 dB/Oktave (siehe Abb.2)
• Ist die Fenster-Funktion stetig, werden Frequenzen außerhalb des Übertragungs-Bereichs des Bandfilters mit 1/Frequenz² abgeschwächt; man erzielt Flankensteilheiten von 12 dB/Oktave

• Ist die 1.Ableitung der Fenster-Funktion stetig, werden Frequenzen außerhalb des Übertragungs-Bereichs des Bandfilters mit 1/Frequenz³ abgeschwächt; die Flankensteilheit beträgt von 18 dB/Oktave

• usw.

Bestimmt man die Fourier-Transformierte von jeweils aufeinander folgenden 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 Frequenz-Auflö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.

Das heißt:

$\left\langle Zeitaufloesung\right\rangle \cdot \left\langle Frequenzaufloesung\right\rangle =1$

oder anders ausgedrückt:

$\left\langle Fensterbreite\right\rangle \cdot \left\langle Frequenzlinienabstand\right\rangle =1$

FFT

Für Blocklängen 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, N=KM, so gibt es eine Zerlegung der DFT der Länge N in ein Produkt von DFTs der Längen K und M sowie zweier einfacher Matrizen.

Anwendungen

• Berechnung der Fourier-Transformierten eines Signals.
• Analyse von Signalen.
• Schwingungsanalyse und Modalanalyse
• Bearbeitung von Signalen.
• Berechnung von Korrelationen.

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.