Fourier-Transformation

Die Fourierreihe ist eine Methode, um periodische Funktionen als Summe von Sinus- und Kosinusfunktionen unterschiedlicher Frequenzen (sog. harmonische Schwingungen) darzustellen. Die Fouriertransformation ist eine Erweiterung der Fourierreihe für nicht-periodische Funktionen. Sie transformiert eine Funktion von der Zeit- (oder Orts-) Domäne in die Frequenzdomäne. Eine visuelle Einführung zur Fourier-Transformation geben 3Blue1Brown. Es ist außerdem gut, Grundkenntnisse über trigonometrische Funktionen und komplexe Zahlen zu haben.

Zeit- & Frequenzdomäne

Wenn man von der Zeitdomäne spricht, betrachtet man, wie sich ein Signal im Laufe der Zeit verhält. Ein Beispiel dafür wäre eine Schallwelle, die durch die Variation des Luftdrucks in Abhängigkeit von der Zeit beschrieben wird. In der Zeitdomäne betrachtet man das Signal direkt, d.h., wie es zu jedem Zeitpunkt aussieht. Die Frequenzdomäne beschreibt ein Signal in Bezug auf seine Frequenzkomponenten, d.h. wie stark bestimmte Frequenzen im Signal enthalten sind. Anstatt zu betrachten, wie das Signal im Laufe der Zeit (oder im Raum) aussieht, beobachtet man, wie viel von jeder Frequenz im Signal vorhanden ist.

Die Fouriertransformation nimmt eine Funktion (oder ein Signal) in der Zeit- oder Ortsdomäne und zerlegt es in eine Summe von Sinus- und Kosinuswellen mit unterschiedlichen Frequenzen. Das Ergebnis dieser Transformation ist eine Darstellung des Signals in der Frequenzdomäne, die zeigt, welche Frequenzen im Signal vorhanden sind und wie stark sie sind. Mit "wie stark" ist hier gemeint, welche Amplitude die jeweiligen Frequenzanteile des Signals haben. Weiterhin gibt die Fouriertransformation Auskunft über die Phase der Frequenzanteile, d.h. wie sie zueinander verschoben sind.
Stellt man sich zum Beispiel eine Gitarrensaite vor Stellen Sie sich vor, die angeschlagen wird, kann man ihre Schwingung in der Zeit- oder in der Frequenzdomäne anschauen. Das erzeugte Signal in der Zeitdomäne würde die Schwingung der Saite im Laufe der Zeit darstellen. Wenn wir die Fouriertransformation darauf anwenden, können wir herausfinden, welche Frequenzen (also welche Noten) die Schwingung der Saite ausmachen und wie laut jede dieser Frequenzen ist.

Faltungstheorem

Die Faltung zweier Funktionen f(t) und g(t) in der Zeitdomäne ergibt eine neue Funktion h(t), die als Faltung der beiden Ausgangsfunktionen bezeichnet wird. Die Faltung ist definiert als $h(t)=(f\circledast g)(t)=\sum _{\infty }^{-\infty }f(\tau )\cdot g(t-\tau )d\tau$ mit t als Variable der Ausgabe bzw. des Zeitpunkts, zu dem ein Funktionswert zugeordnet wird, und $\tau$ als Integrationsvariable bzw. dem Punkt, an dem die beiden Funktionen f und g im jeweiligen Schritt multipliziert werden (siehe auch Konvolution).
Das Faltungstheorem besagt, dass die Fouriertransformation der Faltung zweier Funktionen im Zeitbereich gleich dem Produkt der Fouriertransformationen der beiden Funktionen im Frequenzbereich ist. Mit anderen Worten: ${\mathcal {F}}\lbrace f\ast g\rbrace (t)={\mathcal {F}}\lbrace f\rbrace (f)\cdot {\mathcal {F}}\lbrace g\rbrace (f)$ mit ${\mathcal {F}}$ als Bezeichnung der Fouriertransformation.
Wenn zwei Funktionen im Frequenzbereich multipliziert werden, entspricht dies der Faltung ihrer Inversen Fouriertransformationen im Zeitbereich nach: ${\mathcal {F}}^{-1}\lbrace F(f)\cdot G(f)\rbrace =f(t)\ast g(t)$ mit $F$ und $G$ als Stammfunktionen zu f und g.

Das Theorem ermöglicht effiziente Berechnungen, insbesondere unter Verwendung der Schnellen Fouriertransformation (FFT, siehe unten). Durch die Transformation in den Frequenzbereich, Multiplikation und anschließende Rücktransformation in den Zeitbereich kann die Faltung schneller durchgeführt werden. Häufige Anwendungen finden sich in der Audioverarbeitung (z. B. Echoeffekte), Bildverarbeitung (z. B. Schärfung oder Weichzeichnung von Bildern) und bei der Lösung von Differentialgleichungen.

Diskrete Fouriertransformation

Die diskrete Fouriertransformation (DFT) arbeitet auf endlichen, diskreten Daten (z. B. digitalen Signalen). Sie nimmt eine endliche Folge von Werten (z.B. Abtastwerte eines Signals) und zerlegt diese in eine Summe von Sinus- und Kosinusfunktionen mit verschiedenen Frequenzen.
Angenommen, wir haben eine Liste von N Zahlen $x_{0},x_{1},...,x_{N-1}$. Diese Zahlen könnten beispielsweise die Abtastwerte eines Audiosignals sein. Die DFT dieser Liste erzeugt eine neue Liste $X_{0},X_{1},...,X_{N-1}$, die die Frequenzkomponenten des Signals darstellt. Die Formel zur Berechnung jedes X[k] lautet:
$X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i{\frac {2\pi }{N}}\cdot kN}$

Dabei sind die Größen in der Formel wie folgt definiert:

• $x_{n}$ ist der n-te Wert der ursprünglichen Liste, also der Wert des Signals, der zum Zeitpunkt n gemessen wurde.
• $X_{k}$ ist der k-te Wert in der resultierenden Liste und beschreibt die Amplitude und Phase der k-ten Frequenzkomponente im Signal
• N ist die Gesamtzahl der Werte in der Liste, also die Anzahl der Messpunkte
• Der Index k gibt an, welche Frequenzkomponente betrachtet wird.
• $\sum _{n=0}^{N-1}$ bedeutet, dass über alle Werte von n bis N - 1 addiert wird
• $e^{-i{\frac {2\pi }{N}}\cdot kN}$ ist eine komplexe Exponentialfunktion und bildet die Grundlage dafür, das Signal in seine einzelnen Frequenzkomponenten zu zerlegen.
  • aufgrund der Eulerschen Formel $e^{-1\theta }=\cos(\theta )-i\cdot \sin(\theta )$ und $\theta ={\frac {2\pi }{N}}$ gilt:
    $e^{-i{\frac {2\pi }{N}}}=\cos({\frac {2\pi }{N}}\cdot kN)-i\cdot \sin({\frac {2\pi }{N}}\cdot kN)$
  • Diese Darstellung zeigt, dass die komplexe Exponentialfunktion eine Kombination aus einer Kosinus- und einer Sinuswelle ist. Damit ermöglicht sie die Analyse sowohl des realen als auch des imaginären Anteils des Signals, also der Amplituden und Phasen der verschiedenen Frequenzkomponenten.
  • Die komplexe Exponentialfunktion projiziert das Signal auf verschiedene Frequenzen, um zu sehen, wie stark jede Frequenz im Signal vorhanden ist. Dazu dreht sie vereinfacht gesagt das Signal in der komplexen Ebene um den Ursprung. Dabei korrespondiert k mit der Frequenz und n mit der Zeit. Diese Rotation hilft, Phasenverschiebungen zwischen den verschiedenen Frequenzkomponenten zu berücksichtigen und trägt zur vollständigen Rekonstruktion der Signalform in der Frequenzdomäne bei.
  • Diese Drehung des Signals und Projektion auf die Frequenzen haben 3Blue1Brown (Stand August 2024) mit einer visuellen Darstellung erklärt. Diese Visualisierung ist eigentlich für kontinuierliche Daten gemacht, die Funktionsweise der komplexen Exponentialfunktion ist aber analog zu diskreten Signalen.

Am Ende erhält man für jede Frequenzkomponente Phase und Amplitude, also die Stärke und Verschiebung der Frequenz innerhalb des Signals. Damit findet die DFT zum Beispiel Anwendung in der Signal- und Bildverarbeitung, um Frequenzen in Signalen zu untersuchen und zu filtern.

Schnelle Fouriertransformation

Die schnelle Fouriertransformation (Fast Fourier Transform, FFT) ist ein effizienter Algorithmus zur Berechnung der diskreten Fouriertransformation (DFT). Während die DFT selbst eine wichtige Methode zur Analyse der Frequenzkomponenten eines diskreten Signals ist, ist ihre direkte Berechnung bei großen Datensätzen sehr rechenintensiv. Die FFT reduziert diese Rechenaufwand erheblich durch Anwendung des Teile-und-Herrsche-Prinzips.

Grundidee

Die direkte Berechnung der DFT eines Signals mit $N$ Punkten erfordert $N^{2}$ komplexe Multiplikationen. Das bedeutet, dass der Rechenaufwand sehr schnell wächst, wenn das Signal größer wird. Die FFT reduziert diesen Aufwand dramatisch auf etwa $N\log N$ Operationen.

Dazu nutzt sie einerseits die Aufteilung des Signals in mehrere kleine Abschnitte, die erst separat berechnet und dann kombiniert werden. Andererseits ist die komplexe Exponentialfunktion periodisch und symmetrisch. Das macht sich die FFT zunutze und reduziert redundante Berechnungen.

Cooley-Tukey-Algorithmus

Eine der bekanntesten und am häufigsten verwendeten FFT-Algorithmen ist der Cooley-Tukey-Algorithmus, der wie folgt funktioniert:

• das Signal wird in gerade und ungerade Indizes geteilt (gerade und ungerade ns aus der DFT-Formel) und dann weiter zerlegt, bis die DFT auf Gruppen von 2 - 4 Punkten durchgeführt werden kann
• die DFT der kleinen Gruppen wird berechnet
• um die Ergebnisse aus den kleineren Gruppen zu kombinieren, werden sogenannte Butterfly Operations (Stanford Dawn, Stand August 2024) durchgeführt

Fouriertransformation kontinuierlicher Daten

Die Fouriertransformation für kontinuierliche Daten wird verwendet, um ein zeitkontinuierliches Signal in seine Frequenzkomponenten zu zerlegen. Sie hilft auch hier dabei, zu verstehen, welche Frequenzen im Signal enthalten sind und mit welchen Amplituden und Phasen sie auftreten. Sie ist für ein Signal $x(t)$ wie folgt definiert:
$X(f)=\int _{m=\infty }^{-\infty }x(t)\cdot e^{-i2\pi ft}dt$
Dabei sind die Größen wie folgt definiert:

• $x(t)$ ist das ursprüngliche Signal aus der Zeitdomäne
• $X(f)$ ist die Fouriertransformierte des Signals $x(t)$ und ist eine Funktion der Frequenz f. Diese Funktion gibt an, wie stark (Amplitude) die Frequenz f im Signal vertreten ist und wie sie verschoben ist (Phase).
• f ist die Frequenzvariable, welche Frequenzkomponente betrachtet wird (analog zum k der DFT)
• $e^{-i2\pi ft}$ ist der komplexe Exponentialterm, der die Frequenz f repräsentiert und das Signal auf diese Frequenz projiziert. Auch hier sei auf die visuelle Erklärung von 3Blue1Brown (Stand August 2024) verwiesen.
• dt ist das Differentialelement in der Zeitdomäne, das die kontinuierliche Integration anzeigt

Damit erhält man auch hier für jede Frequenzkomponente Phase und Amplitude, also die Stärke und Verschiebung der Frequenz innerhalb des Signals. Wenn man das für mehrere Zeitschritte (Intervalle) des Signals durchführt, kann man beobachten, wie sich die Frequenzanteile über die Zeit des Signals hinweg entwickeln. Dies lässt sich in einem Spektrogramm darstellen. Damit lassen sich zum Beispiel Frequenzkomponenten in EEG-Signalen untersuchen. Zum Spektrogramm gibt es eine kurze Erklärung in Wikipedia und eine ausführliche Erklärung im Buch Digitale Signalverarbeitung mit MATLAB von Martin Werner (Springer Vieweg, 2019, SLUB-Katalog Stand August 2024). Da man aber zur Betrachtung der Frequenzkomponenten über die Zeit hinweg das Signal in diskrete Zeitfenster einteilen muss, wird die Information über die Entwicklung der Frequenzkomponenten verringert. Um diese Entwicklung kontinuierlich abzubilden, eignen sich Wavelet-Transformationen.

Inverse Fouriertransformation

Die ursprüngliche Funktion $x(t)$ kann auch aus der Fouriertransformierten $X(f)$ zurückgewonnen werden durch die Inverse Fouriertransformation. Hierzu integriert man über alle Frequenzen f, um das Signal in der Zeitdomäne $x(t)$ zu rekonstruieren:
$x(t)=\int _{m=\infty }^{-\infty }X(f)\cdot e^{i2\pi ft}df$
Dieses Prinzip macht man sich zum Beispiel in der Audiobearbeitung zunutze. Beispielsweise kann man ein Signal in die Frequenzdomäne transformieren, dort die Stärke einzelner Frequenzen auf Null setzen und das Ergebnis rücktransformieren. So können störende Frequenzen aus Audiosignalen entfernt bzw. gefiltert werden.

Filter

Filter für Signale werden genutzt, um unerwünschte Frequenzkomponenten zu entfernen. Dabei kann man Filter nach den Frequenzbereichen, die sie durchlassen (pass) oder blockieren (stop) unterscheiden:

Tiefpassfilter

• lässt Frequenzen unterhalb einer bestimmten Grenzfrequenz passieren und blockiert höhere Frequenzen
• wird z.B. genutzt, um Daten zu glätten, Hochfrequenzrauschen zu entfernen (z.B. im MR-Signal)

Hochpassfilter

• lässt Frequenzen oberhalb einer bestimmten Grenzfrequenz passieren und blockiert tiefere Frequenzen
• wird z.B. genutzt, um hohe Frequenzen zu verstärken, um u.a. in der Bildverarbeitung Kanten im Bild zu detektieren

Bandpassfilter

• lässt Frequenzen innerhalb eines bestimmten Frequenzbandes passieren und blockiert Frequenzen ober- und unterhalb dieses Bandes
• wird z.B. in der Tonbearbeitung genutzt, um Störungen außerhalb des menschlichen Sprachbereichs zu filtern, um Daten zu sparen und Rauschen zu reduzieren

Bandsperrfilter oder Kerbfilter (notch filter)

• blockiert Frequenzen innerhalb eines bestimmten Frequenzbandes und lässt Frequenzen außerhalb des Bandes passieren
• wird z.B. genutzt, um spezifische Störgeräusche in Audiosignalen zu entfernen