Diskrete Fourier-Transformation

Die Diskrete Fourier-Transformation oder DFT ist die Fourier-Transformation 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 schnelle Fourier-Transformation.

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

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).

Inhaltsverzeichnis

Definition

Berechnung der DFT

Input: Ein Vektor x von reellen Zahlen der Länge N, x=(x0,...,xN-1).
Output: Ein Vektor y von komplexen Zahlen der Länge N, y=(y0,...,yN-1).

Es wird berechnet:

y_n=\sum_{k=0}^{N-1}e^{-2\pi i\cdot\frac{nk}{N}}\cdot x_k

Bemerkung: Es gilt allgemein ei = 1 und \overline{e^{i\phi}}=e^{-i\phi}, und daher bei reellem Input x.

y_{N-n} =\sum_{k=0}^{N-1}e^{-2\pi i\cdot\frac{Nk}{N}}e^{2\pi i\cdot\frac{nk}{N}}\cdot x_k =\sum_{k=0}^{N-1}\overline{e^{-2\pi i\cdot\frac{nk}{N}}\cdot x_k} =\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.

Berechnung der iDFT

Input: Ein Vektor y von komplexen Zahlen der Länge N, y=(y0,...,yN-1).
Output: Ein Vektor x von komplexen Zahlen der Länge N, x=(x0,...,xN-1).

Es wird berechnet:

x_n=\frac1N\sum_{k=0}^{N-1}e^{2\pi i\cdot\frac{nk}{N}}\cdot y_k

Bemerkung: 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 yn + jN = yn und in der iDFT xn + jN = xn. 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,

tn: = 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 xn = f(tn) 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=\frac1N \sum_{k=1-K}^{N-K}e^{-2\pi i\frac{nkT}{NT}}y_k =\frac1N \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.

right|thumb|250px|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.

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

Mathematische Grundlage

Die in der diskreten Fouriertransformation auftretenden komplexen Zahlen e^{2\pi i\,\frac{n}N} sind N-te Einheitswurzeln, d.h. sie sind Lösungen der Gleichung q^{\,N}-1=0. Sei q:=e^{2\pi i\,\frac{1}N} die „kleinste“, also primitive Wurzel im ersten Quadranten.

Diese genügt folgender Identität geometrischer Summen von Einheitswurzeln:

\sum_{k=0}^{N-1} q^{nk}=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\ne1. Dies ist der "tiefe Grund", weshalb die inverse DFT funktioniert.


Definieren wir in \mathbb C^N die Vektoren f_n:=(e^{i2\pi\frac{nk}N})_{k=0,\dots,N-1}, n=0,...,N-1, so bilden diese eine orthonormale Basis zum Skalarprodukt <x,y>:=\frac1N\sum_{k=0}^{N-1}x_k\bar y_k. Es gilt

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


Jeder Vektor x=(x_0,\dots,x_{N-1})\in\mathbb C^N kann in der Orthonormalbasis dargestellt werden

x=\sum_{n=0}^{N-1}<x,f_n>\cdot f_n.

Die Koeffizienten < x,fn > heißen (auch allgemein bei beliebigem Orthonormalsystem) Fourier-Koeffizienten, die DFT ordnet also einem Vektor x den Vektor X=DFT(x) der Fourier-Koeffizienten zu (bis auf konstante Faktoren).

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

<x,y>=\sum_{n=0}^{N-1}<x,f_n><f_n,y>=\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, 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} \,d t

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:

Diskretisierung von Fourier-Reihen

Jede periodische Funktion mit reellem Argument (und wieder Einschränkungen wie: Integrabilität, keine Polstellen) und Periode L kann als Funktionenreihe mit Sinoiden, die Bruchteile von L als Periode haben, dargestellt werden:

f(t)=\sum_{n\in\mathbb Z} c_n(f)e^{i\cdot \omega_nt}, \omega_n=\frac{2\pi n}{L}.

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

f(t_k)=f(kT)\approx \sum_{N=1-M}^{N-M} c_n(f)e^{2\pi i\cdot \frac{nk}{N}},

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

c_n(f)\approx\frac{1}{L}\sum_{N=0}^{N-1} f(kT)e^{-i\cdot \frac{2\pi nk}{N}}\cdot \frac{L}{N}=\frac{1}{L}\sum_{N=0}^{N-1} f(t_k)e^{-i\cdot \frac{2\pi n}{L}t_k}\cdot T

Im Grenzfall eines unendlich großen N ergeben sich die bekannten Koeffizientenintegrale der Fourier-Reihen:

c_n(f)=\frac{1}{L}\int_0^L f(t)e^{-i\cdot \frac{2\pi n}{L}t}\,d t

Faltung endlicher Folgen -- Polynome auf dem Einheitskreis

Eigenschaften

Spektrum abgetasteter Funktionen

thumb|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.

thumb|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)

thumb|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 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.

(siehe Abb.3)

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

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.

Das heißt:

\left\langle \textrm{Zeitaufl}\ddot \textrm{o}\textrm{sung} \right\rangle \cdot \left\langle \textrm{Frequenzaufl}\ddot \textrm{o}\textrm{sung} \right\rangle = 1

oder anders ausgedrückt:

\left\langle \textrm{Fensterbreite} \right\rangle \cdot \left\langle \textrm{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

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.


Kategorie:Digitale Signalverarbeitung

See also: Diskrete Fourier-Transformation, Abtasttheorem, Abtastung, Alias-Effekt, Anti-Aliasing, Basisband, Beugung (Physik), Beugungsscheibchen, Digitale Signalverarbeitung, Digitales Filter