Schnelle Fourier-Transformation

Die schnelle Fourier-Transformation (SFT; englisch fast Fourier transform, daher häufig FFT) ist ein Algorithmus zur schnellen Berechnung der Werte einer diskreten Fourier-Transformation (DFT). Die Beschleunigung gegenüber der direkten Berechnung beruht auf der Vermeidung mehrfacher Berechnung sich gegenseitig aufhebender Terme. Der Algorithmus wird Cooley und Tukey zugeschrieben, die ihn 1965 veröffentlichten. Genaugenommen wurde eine Form des Algorithmus jedoch bereits 1805 von Carl Friedrich Gauss entworfen, der ihn zur Berechnung der Flugbahnen der Asteroiden Pallas und Juno verwendete. Darüber hinaus wurden eingeschränkte Formen des Algorithmus noch mehrfach vor Cooley und Tukey entwickelt, so z.B. von Good (1960). Nach Cooley und Tukey hat es darüber hinaus zahlreiche Verbesserungsvorschläge und Variationen gegeben, so etwa von Bruun, Rader und Bluestein.

Auch für die FFT ist eine Umkehroperation (inverse FFT - iFFT) definiert. Somit kann auch die Kombination aus FFT und iFFT zur Manipulation von Signalen auf Frequenzebene eingesetzt werden. Kompressionsalgorithmen wie der des MP3-Formats basieren hierauf. Ein weiteres wichtiges Anwendungsbeispiel ist die Breitbanddatenübertragung per OFDM, die Grundlage für ADSL und WLAN (Internet), DVB-T (Fernsehen), DRM und DAB (Radio) ist.

Inhaltsverzeichnis

1 Informelle Beschreibung des Algorithmus (Cooley und Tukey)

2 Formelle Beschreibung des Algorithmus (Cooley und Tukey)

3 Komplexität

4 FFT-Software zur Signalanalyse mit dem PC mit Hilfe der PC-Soundkarte

5 Anwendung

6 Weblinks

Informelle Beschreibung des Algorithmus (Cooley und Tukey)

Der Algorithmus von Cooley und Tukey ist ein klassisches Teile und herrsche-Verfahren. Voraussetzung für seine Anwendung ist, dass die Anzahl der Stützstellen bzw. Abtastpunkte eine Zweierpotenz ist. Da die Anzahl solcher Punkte im Rahmen von Messverfahren jedoch im allgemeinen frei gewählt werden kann, handelt es sich dabei nicht um eine gravierende Einschränkung. Das Problem der Berechnung einer DFT der Größe n wird nun zunächst in zwei Berechnungen der DFT der Größe n/2 aufgeteilt - der Vektor der Messwerte wird in die Teilvektoren der Einträge zu geraden bzw. ungeraden Indizes aufgeteilt und von beiden die DFT bestimmt. Die beiden Teilergebnisse werden dann wieder zu einem Gesamtergebnis zusammengefügt. Zur Berechnung der beiden Hälften werden die Eigenschaften der Einheitswurzeln aus der Fouriermatrix ausgenutzt. Eine rekursive Anwendung dieser Grundidee ermöglicht schließlich eine Berechnung in O(n log₂ n) Zeit.

Formelle Beschreibung des Algorithmus (Cooley und Tukey)

Zunächst sei in Erinnerung gerufen, dass die DFT durch folgende Formel definiert ist:

$f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2\pi i}{n} jk } \qquad j = 0,\dots,n-1.$

Setzen wir n' = n/2 und notieren die Einträge zu geraden Indizes als

x'₀ = x₀, x'₁ = x₂, ..., x'_n'-1 = x_n-2

und bezeichnen deren Transformierte nach DFT der Größe n' mit

f'₀, ..., f'_n'-1;

die Einträge zu ungeraden Indizes notieren wir entsprechend als

x"₀ = x₁, x"₁ = x₃, ..., x"_n'-1 = x_n-1

und bezeichnen deren Transformierte nach DFT der Größe n' mit

f"₀, ..., f"_n'-1.

Dann folgt:

$\begin{matrix} f_j & = & \sum_{k=0}^{\frac{n}{2}-1} x_{2k} e^{-\frac{2\pi i}{n} j(2k)} + \sum_{k=0}^{\frac{n}{2}-1} x_{2k+1} e^{-\frac{2\pi i}{n} j(2k+1)} \\ \\ & = & \sum_{k=0}^{n'-1} x'_{k} e^{-\frac{2\pi i}{n'} jk} + e^{-\frac{2\pi i}{n}j} \sum_{k=0}^{n'-1} x''_k e^{-\frac{2\pi i}{n'} jk} \\ \\ & = & \left\{ \begin{matrix} f'_j + e^{-\frac{2\pi i}{n}j} f''_j & \mbox{falls } j<n' \\ \\ f'_{j-n'} - e^{-\frac{2\pi i}{n}(j-n')} f''_{j-n'} & \mbox{falls } j \geq n' \end{matrix} \right. \end{matrix}$

Komplexität

Die klassische FFT ist im Gegensatz zur DFT nur möglich, wenn die Länge des Eingangsvektors einer Zweierpotenz entspricht. Die Anzahl der Abtastpunkte kann also beispielsweise 1, 2, 4, 8, 16, 32 usw. betragen. Man spricht hier von einer Radix-2-FFT. Wenn man die Längen auf Potenzen von vier beschränkt, kann man analog eine Radix-4-FFT einsetzen usw.. Der Rechenaufwand reduziert sich für eine Radix-2-FFT von

$T \left( N \right)=O(N^2)$

für die DFT auf

$T \left( N \right)=O(N \cdot \log(N)).$

Bei $N = 2 4 = 16$ gilt für die Effizienz der FFT $N l o g (N) = 64$ , das heißt, die FFT ist schon für kurze Folgen schneller als eine DFT ( $N 2 = 256$ ). Bei $N = 2 10 = 1024$ benötigt die DFT schon 341 mal mehr Zeit als die FFT.

Bei einer Faltung zweier Signale reduziert sich der Rechenaufwand gar von

$T \left( N \right)=O(N^4)$

auf

$T \left( N \right)=O(N^2 \cdot \log(N)).$

Die Struktur des Datenflusses kann durch einen Schmetterlingsgraphen beschrieben werden, der die Reihenfolge der Berechnung festlegt. Diese Struktur ist identisch zur Sortiermethode Quicksort.

Zur Abschätzung der Rechenleistung für die Berechnung eines Algorithmus siehe auch Komplexitätstheorie.

FFT-Software zur Signalanalyse mit dem PC mit Hilfe der PC-Soundkarte

Sonogram (Freeware, Java-basiert)
SpecLab (Freeware)
Spectran (Freeware)
Spectrogram (Shareware)
Audiotester (Shareware)

Anwendung

Schwingungsmesstechnik - Umrechnung Zeit in Frequenzendarstellung
Audiomessungen - Berechnung von Spektrogrammen (Diagramme mit der Darstellung der Amplituden von den jeweiligen Frequenzanteilen)
Längstwellenempfang mit dem PC
Teil schneller Polynome verarbeitender Algorithmen (z.B. Polynommultiplikation in $O (n log n)$ ) in der Computeralgebra.
Berechnung digitaler Filter

Weblinks

http://www.fftw.org
http://www.nr.com/ (Buch Numerical Recipes, engl., auch online verfügbar)