Digital Signal Processing Reference
In-Depth Information
cos(
ω
k
) = cos
2
π
M
W
C
[
k
]
←
(13.63)
13
Einfuhrung in
Spektraltechniken
sin(
ω
k
)=sin
2
π
M
,
W
S
[
k
]
←
wobei 0
k<M
. Aus diesen Tabellen konnen die fur die Berechnung
der DFT notwendigen Kosinus- und Sinuswerte (Gl. 13.46) in der Form
≤
k
(
u
) = cos
2
π
m
M
=
W
C
[
mu
mod
M
]
C
(13.64)
k
(
u
)=sin
2
π
m
M
=
W
S
[
mu
mod
M
]
M
S
(13.65)
ohne zusatzlichen Berechnungsvorgang fur beliebige Werte von
m
und
u
ermittelt werden. Die entsprechende Modifikation der
DFT()
-Methode
in Prog. 13.1 ist eine einfache Ubung (Aufg. 13.5).
Trotz dieser deutlichen Verbesserung bleibt die direkte Implementie-
rung der DFT rechenaufwendig. Tatsachlich war es lange Zeit unmoglich,
die DFT in dieser Form auf gewohnlichen Computern ausreichend schnell
zu berechnen und dies gilt auch heute noch fur viele konkrete Anwen-
dungen.
13.4.2 Fast Fourier Transform (FFT)
Zur praktischen Berechnung der DFT existieren schnelle Algorithmen,
in denen die Abfolge der Berechnungen so ausgelegt ist, dass gleichartige
Zwischenergebnisse nur einmal berechnet und in optimaler Weise mehr-
fach wiederverwendet werden. Die sog.
Fast Fourier Transform
,vonder
es mehrere Varianten gibt, reduziert i. Allg. die Zeitkomplexitat der Be-
rechnung von
(
M
2
)auf
(
M
log
2
M
). Die Auswirkungen sind vor al-
lem bei großeren Signallangen deutlich. Zum Beispiel bringt die FFT bei
eine Signallange
M
=10
3
bereits eine Beschleunigung um den Faktor 100
und bei
M
=10
6
um den Faktor 10
.
000, also ein eindrucksvoller Gewinn.
Die FFT ist daher seit ihrer Erfindung ein unverzichtbares Werkzeug in
praktisch jeder Anwendung der digitalen Spektralanalyse [11].
Die meisten FFT-Algorithmen, u. a. jener in der beruhmten Publika-
tion von Cooley und Tukey aus dem Jahr 1965 (ein historischer Uber-
blick dazu findet sich in [30, S. 156]), sind auf Signallangen von
M
=2
k
,
also Zweierpotenzen, optimiert. Spezielle FFT-Algorithmen wurden aber
auch fur andere Langen entwickelt, insbesondere fur eine Reihe kleinerer
Primzahlen [7], die wiederum zu FFTs unterschiedlichster Große zusam-
mengesetzt werden konnen.
Wichtig ist jedenfalls zu wissen, dass DFT und FFT
dasselbe
Er-
gebnis berechnen und die FFT nur eine spezielle - wenn auch außerst
geschickte -
Methode
zur Implementierung der diskreten Fouriertrans-
formation (Gl. 13.43) ist.
O
O
