www.iap.uni-jena.de

Die Fast-Fourier-Transformation

1

Konvention

KonventionKonvention

Konvention

2Fourier-Transformation, Fourier-Reihe und DFTWas ist der Unterschied?

Fourier‐Transformation

Vorwärts‐Transformation Rückwärts‐Transformation

Auch Konvention mit umge‐kehrten  Vorzeichen ist üblich.

→ 2 ,→ , → 2 Mit den Ersetzungen ergibt sich die oftmals gefundene Darstellung

Man beachte, dass hier keine Vorfaktoren vor den Integralen mehr stehen.

Stellt sicher, dass gilt.

Auch umgekehrte oder symmetrische Faktoren   , sind üblich.

3Fourier-Transformation, Fourier-Reihe und DFTWas ist der Unterschied?

Fourier‐Transformation

kontinuierliche Funktion mitunendlichem Definitionsgebiet

kontinuierliche Funktion mitunendlichem Definitionsgebiet

4Fourier-Transformation, Fourier-Reihe und DFTWas ist der Unterschied?

Fourier‐Reihe für eine periodische Funktion

Fourier‐Koeffizienten Fourier‐Entwicklung

beliebiger Startpunkt der Integration

kontinuierliche, periodische Funktion unendlich viele, diskrete Koeffizienten

5Fourier-Transformation, Fourier-Reihe und DFTWas ist der Unterschied?

„Inverse“ Fourier‐Reihe für eine unendliche diskrete Reihe 

kontinuierliche, periodische Funktionunendlich viele, diskrete Koeffizienten

Findet selten Verwendung, da es praktisch keine unendlich ausgedehnten diskreten Systeme gibt.

Fourier‐KoeffizientenFourier‐Entwicklung

2

6Fourier-Transformation, Fourier-Reihe und DFTWas ist der Unterschied?

Diskrete Fourier‐Transformation für eine periodische diskrete Reihe

endlich viele, diskrete Koeffizienten

Rückwärts‐TransformationVorwärts‐Transformation

0, … , 1 0,… , 1

endlich viele, diskrete Koeffizienten

Diskrete Fourier-Transformation7

0, … , 1

Es sind  N Multiplikationen N‐mal durchzuführen

Aufwand der DFT skaliert mit

DFT wird zu FFT8

0, … , 1

0     1    2     3    4     5    6     7

⁄ · ⁄

DFT des geraden Anteils DFT des ungeraden Anteils

DFT wird zu FFT9

⁄ · ⁄

DFT des geraden Anteils DFT des ungeraden Anteils

für  0,… , 2 1 für  0,… , 2 1

· 0, … , 2 1

Was ist mit  ?

0

Aufgrund der Periodizität der DFT gilt:

DFT wird zu FFT10

0,… , 2 1 ·

·

·

·

·0, … , 2 1

FFT‐Schema nach Cooley und Tukey (radix‐2 Decimation‐in‐time):

Fast-Fourier-Transformation11

·

·0, … , 2 1

FFT‐Schema nach Cooley und Tukey (radix‐2 Decimation‐in‐time):

Rekursion:

Teile und herrsche!

Rekursionsende:  Array hat Länge 1    ∈für

Fast-Fourier-Transformation12

·

·0, … , 2 1

FFT‐Schema nach Cooley und Tukey (radix‐2 Decimation‐in‐time):

Komplexität des Algorithmus: log

log

Eigenschaften der diskreten Spektren13

Periodizität:

Symmetrie:

1

≡ ∗

∗

∗

0     1    2     3    4     5    6     7 0     1    2     3    4     5    6     70     1    2     3    4     5    6     7

Null‐Frequenz Maximalfrequenz (Nyquist‐Frequenz)