Digital Signal Processing Reference
In-Depth Information
Die bisherigen Überlegungen zum Signalflussgraphen der
Decimation-in-time
(DIT)
-Radix-2-
FFT
werden in Bild 4-4 zusammengefasst. Näherungsweise sind pro Stufe
N
/ 2 komplexe
Multiplikation und
N
komplexe Additionen bzw. Subtraktionen erforderlich. Im Vergleich mit
Bild 4-2 reduziert sich der Rechenaufwand auf
R
/
5l g
N
N
FLOPs
(4.14)
Radix-2-FFT
2
Es ist offensichtlich, dass in den ersten beiden Stufen keine echten Multiplikationen erforder-
lich sind, sodass die Zahl der Multiplikationen noch etwas reduziert werden kann.
X
[0]
x
[0]
x
[4]
1
X
[1]
x
[2]
1
X
[2]
x
[6]
1
j
1
X
[3]
x
[1]
X
[4]
1
w
8
1
x
[5]
X
[5]
1
1
w
8
2
x
[3]
X
[6]
1
1
w
8
3
x
[7]
X
[7]
1
j
1
1
Stufe
1
Stufe
2
Stufe
3
Bild 4-4
Signalflussgraph der DIT-Radix-2-FFT für die DFT-Länge
N
= 8
Für die FFT werden in der Literatur verschiedene Modifikationen vorgeschlagen, die je nach
Anwendung unterschiedlichen Zielvorstellungen gehorchen, wie geringer Speicherplatzbedarf,
kleine Rechenungenauigkeiten, kompaktes Programm, optimale Ausnutzung der Prozessor-
architektur, usw. Dabei werden auch unterschiedliche Voraussetzungen berücksichtigt, z. B.
dass die DFT-Länge keine Zweierpotenz ist (Split-Radix-Algorithmus), dass die Eingangs-
folgen rein reell sind oder nur einige wenige Werte des Spektrums gesucht werden (Goertzel-
Algorithmus).
Ihrer Bedeutung gemäß wird die FFT oft durch spezielle Hardware auf Signalprozessoren
unterstützt, sodass sie besonders schnell ausgeführt werden kann. Die FFT wird deshalb nicht
nur zur Spektralanalyse verwendet, sondern findet beispielsweise auch zur Datenübertragung
mit dem OFDM(Orthogonal Frequency Division Multiplex)-Verfahren ihre Anwendung in
drahtlosen lokalen Rechnernetzen (WLAN, Wireless Local Area Network), dem terrestrischen
digitalen Fernsehen (DVB-T, Digital Video Broadcasting Terrestrial) und der vierten Mobil-
funkgeneration (LTE, Long Term Evolution). Darüber hinaus wird die FFT auch bei der
MPEG(Moving Pictures Experts Group)-Audio-Codierung eingesetzt.
