Fast Fourier Transformation

n einer Meßreihe Periodizitäten zu finden ist eine häufige Aufgabe, nicht nur in der astronomischen, sondern auch in der physikalischen und technischen Programmierung.

Als einfachstes Beispiel nehmen wir die Sinuskurve f(t) = a sin(ωt). Die Periode erkennt man leicht: T = 2p/ω. Was aber, wenn man eine Kurve der Form

vorliegen hat? Hier liegen die Dinge nicht so trivial. Man erkennt zwar, daß es sich um eine Überlagerung irgendwelcher Frequenzen handelt, aber nicht mehr auf Anhieb, wieviele und vor allem welche Frequenzen beteiligt sind.

Ab hier beginnt das Einsatzgebiet der Fourier-Transformation. Die Fourier-Transformation konvertiert eine gegebene Funktion der Zeit f(t) in eine Funktion der Frequenz g(ω). Wenn man g(ω) hat, lassen sich die Frequenzanteile direkt ablesen. Die Fourier-Transformation ist obendrein umkehrbar.

Bei der Fourier-Transformation wird versucht, eine gegebene Kurve als Summe mehrerer trigonometrischer (sin, cos) Funktionen mit aufsteigenden Frequenzen aufzufassen, und zwar in der Form

Dieses Prinzip läßt sich auch auf diskrete Daten, z.B. äquidistante Meßwerte, anwenden. Es gibt mehrere Varianten zur Berechnung der Fourier-Transformation. Die sicherlich meistverbreitete ist die Fast Fourier Transformation (FFT), die am Rechner relativ leicht zu implementieren ist. Es gibt zahlreiche Beispielimplementationen hierzu. Der Wikipedia habe ich eine recht eingängige Musterimplementation in Pseudocode entnommen:

Mit der obigen Darstellung möchte man am liebsten drauflos programmieren. Der Wertebereich des resultierenden Arrays erstreckt sich von -Abtastfrequenz bis +Abtastfrequenz, wobei sich die Abtastfrequenz aus dem zeitlichen Abstand zweier benachbarter Meßpunkte ergibt.

Die Ausführungsgeschwindigkeit der FFT skaliert mit der Ordnung O(N*log²N). Ein Nachteil ist, daß die Anzahl der Elemente des Eingabearrays einer Zweierpotenz entsprechen muß. Das Array kann allerdings bis zur nächsten Zweierpotenz mit Nullen aufgefüllt werden.

Wer die FFT auf die Daten der obenstehenden Grafik anwendet, wird einen Graphen für das Ergebnis-Array bekommen, welche die Frequenzanteile enthält und ähnlich wie diese aussieht:

Daraus kann man ablesen, daß für die ursprüngliche Funktion drei Frequenzen beteiligt sind, und zwar 1.0, 0.4 und 0.25. Streng genommen sollten bei periodischen Funktionen auch negative Frequenzen beachtet werden - aus Symmetriegründen beschränkt man sich auf die positiven Anteile.

Die Fourier-Transformation leistet in der Astronomie und Physik wichtige Dienste. Hier ein paar Beispiele:

  • Analyse des Sonnenzyklus
  • Analyse der Lichtkurve bei Veränderlichen (z.B. beim Algol-Typ)
  • Bild- und Signalverarbeitung (Tiefpass zur Rauschunterdrückung, Bewegungsdetektion z.B. bei adaptiver Optik (Stichwort Kreuzkorrelation))

Auch ein optisches Prisma wirkt gewissermaßen wie eine Fourier-Transformation.

Theoretische Physiker nutzen die Fourier-Transformation ebenfalls oft. Wenn z.B. eine Differentialgleichung nicht lösbar ist, so kann man sie in den Frequenzraum transformieren, um zu sehen, ob sie dort lösbar ist. Falls ja, so löst man dort die Gleichung und nutzt die Umkehrbarkeit für eine Rücktransformation der gefundenen Lösung aus.

Kein Beispiel aus der Astronomie, sondern eine eher alltägliche Anwendung ist der HiFi-Equalizer.

Das Anwendungsgebiet der Fourier-Transformation ist vielgestaltig. Wer mit wechselnden astronomischen Programmierprojekten zu tun hat, wird wahrscheinlich früher oder später damit konfrontiert.