Schnelle Fourier-Transformation (FFT)
Bild 1: Die Überlagerung der Grundschwingung (gelb) mit der dritten Harmonischen (türkis) ergibt bereits eine Annäherung an ein Rechtecksignal (rot).
Bild 2: Durch Hinzufügen der fünften Harmonischen wird die Annäherung an das Rechtecksignal weiter verbessert.
Bild 3: Frequenzspektrum des aus Grundschwingung und Oberwellen zusammengesetzten Rechtecksignals
Bild 1: Die Überlagerung der Grundschwingung (gelb) mit der dritten Harmonischen (türkis) ergibt bereits eine Annäherung an ein Rechtecksignal (rot).
Bild 2: Durch Hinzufügen der fünften Harmonischen wird die Annäherung an das Rechtecksignal weiter verbessert.
Bild 3: Frequenzspektrum des aus Grundschwingung und Oberwellen zusammengesetzten Rechtecksignals
Bild 1: Die Überlagerung der Grundschwingung (gelb) mit der dritten Harmonischen (türkis) ergibt bereits eine Annäherung an ein Rechtecksignal (rot).
Bild 2: Durch Hinzufügen der fünften Harmonischen wird die Annäherung an das Rechtecksignal weiter verbessert.
Bild 3: Frequenzspektrum des aus Grundschwingung und Oberwellen zusammengesetzten Rechtecksignals
Schnelle Fourier-Transformation (FFT)
Die Grundlagen der Fourieranalyse wurden durch den französischen Mathematiker Jean Baptiste Joseph Fourier entwickelt und 1822 in seinem Werk Théorie analytique de la chaleur veröffentlicht. Bei der Radarsignalverarbeitung werden unter anderem die Amplitude und die Phase der empfangenen Echosignale ausgewertet. Aus dem Phasenverlauf aufeinanderfolgender Echos kann beispielsweise die Dopplerfrequenz bestimmt werden. Dazu werden die zeitlich erfassten Signalwerte mithilfe der Fourier-Transformation in den Frequenzbereich überführt.
Die Fourier-Transformation ist zu einem fundamentalen Verfahren in der Signalverarbeitung geworden, da bei einem Radarecho eine Vielzahl von Informationen in der Signalform enthalten sind. Diese Informationen werden durch die Fourier-Transformation in eine Darstellung im Frequenzbereich überführt, die sich für die rechnergestützte Weiterverarbeitung eignet.
Die Fourier-Transformation ist ein mathematisches Verfahren, mit dem ein Signal in seine Frequenzanteile zerlegt werden kann. Diese Frequenzanteile lassen sich durch Sinus- und Cosinusfunktionen unterschiedlicher Frequenz, Phase und Amplitude beschreiben. Für digital abgetastete Signale wird die Diskrete Fourier-Transformation (DFT) verwendet. Die Fast Fourier Transformation (FFT) ist ein besonders effizientes Verfahren zur Berechnung dieser DFT.
In der nebenstehenden Diagrammreihe wird anhand einer Fourier-Reihe gezeigt, wie sich ein periodisches Rechtecksignal durch die Überlagerung einer Grundschwingung mit ihren ungeraden harmonischen Oberwellen annähern lässt. Mit jeder weiteren geeigneten Oberwelle wird die Annäherung an die Rechteckform verbessert. Die Darstellung eines Signals als Frequenzspektrum lässt sich in einer Tabelle mit Angaben zu Frequenz und Amplitude zusammenfassen. Solche Daten eignen sich gut für eine rechnergestützte Weiterverarbeitung.
Für die effiziente Berechnung der DFT wurden verschiedene FFT-Algorithmen entwickelt, beispielsweise der Cooley–Tukey– Algorithmus und der Sande–Tukey– Algorithmus. Bei bestimmten Implementierungen kommt zusätzlich eine Umordnung der Daten nach dem sogenannten Bit-Reversing-Verfahren zum Einsatz. Ein weiteres Anwendungsbeispiel ist die Schnelle Faltung. Dabei werden zwei Signale nicht unmittelbar im Zeitbereich gefaltet, sondern zunächst in den Frequenzbereich transformiert, dort miteinander multipliziert und anschließend wieder in den Zeitbereich zurücktransformiert. Dieses Verfahren kann den Rechenaufwand erheblich verringern.
Die direkte Berechnung der DFT ist bei einer großen Anzahl von Abtastwerten sehr rechenaufwendig. Eine Fast Fourier Transformation ist ein Algorithmus, mit dem die Diskrete Fourier-Transformation wesentlich schneller und effizienter berechnet werden kann. Dies wird erreicht durch:
- die Zerlegung einer großen Transformation in kleinere Teilberechnungen,
- die mehrfache Nutzung bereits berechneter Zwischenergebnisse,
- die Verringerung der insgesamt erforderlichen Rechenoperationen.
Während der Rechenaufwand einer direkten DFT bei N Abtastwerten ungefähr mit dem Quadrat der Anzahl der Abtastwerte wächst, steigt er bei verbreiteten FFT-Verfahren nur etwa proportional zu N · log2(N). Bei ausreichend großen Datenmengen kann eine FFT deshalb weniger als ein Hundertstel der Rechenzeit einer direkten DFT benötigen. Mithilfe der schnellen Fourier-Transformation können charakteristische Frequenzanteile von Radarechos ermittelt werden. Diese Merkmale lassen sich mit vergleichsweise wenigen Daten speichern und können bei der automatischen Zielerkennung zur Unterscheidung verschiedener Zielarten beitragen.
mathematische Grundlagen: www.mathepower.com
weiterführend: www.iti.fh-flensburg.de
Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/;
The Design and Implementation of FFTW3, Proceedings of the IEEE 93 (2), 216–231 (2005).