Operation Manual

Seite 16-53
Die folgende Eigenschaft gilt für die Faltung:
F{f*g} = F{f}⋅F{g}.
Fast Fourier-Transformation (FFT)
Die Fast Fourier-Transformation/ schnelle Fourier-Transformation ist ein
Computeralgorithmus, durch welchen eine diskrete Fourier-Transformation (DFT)
sehr effizient berechnet werden kann. Dieser Algorithmus findet in der Analyse
verschiedener zeitabhängiger Signale Anwendung, von der Messung von
Turbulenzen bis zu Kommunikationssignalen.
Die diskrete Fourier-Transformation einer Reihe von Datenwerten {x
j
}, j = 0, 1,
2, …, n-1, ist eine neue endliche Folge {X
k
}, definiert als:
Die direkte Berechnung der Folge X
k
bezieht n
2
Produkte ein, die einen
enormen Aufwand an Computerzeit (oder Taschenrechnerzeit), vor allem für
große Werte von n, benötigen würde. Die Fast Fourier-Transformation reduziert
die benötigte Anzahl an Operationen auf die Ordnung von n⋅log
2
n. Für n =
100 z. B. benötigt die FFT ungefähr 664 Operationen, während die direkte
Berechnung 10.000 Operationen benötigen würde. Somit wird die Anzahl der
Operationen mithilfe der FFT um einen Faktor von 10000/664 ≈ 15 reduziert.
Die FFT arbeitet an der Sequenz {x
j
}, indem sie sie in eine Reihe kleinerer
Sequenzen teilt. Die DFTs der kürzeren Sequenzen werden berechnet und
später auf höchst effiziente Weise zusammengeführt. Details zum Algorithmus
finden Sie z. B. in Kapitel 12 in Newland, D.E., 1993, „An Introduction to
Random Vibrations, Spectral & Wavelet Analysis – Third Edition“ , Longman
Scientific and Technical, New York.
∫
⋅⋅−⋅= .)()(
2
1
))(*( ξξξ
π
dgxfxgf
∑
−
=
−=⋅−⋅=
1
0
1,...,2,1,0),/2exp(
1
n
j
jk
nknkjix
n
X π