Digital Signal Processing Reference
In-Depth Information
Eine genaue Analyse des Signalflussgrafen zeigt, dass die Komplexität weiter reduziert werden
kann. Man betrachte beispielsweise die Eingangswerte
x
[0] und
x
[4]. Aus ihnen werden ohne
Verwendung weiterer Eingangswerte in der ersten Stufe genau zwei Zwischenwerte be-
rechnet. Die Eingangswerte werden danach zur DFT nicht mehr benötigt, so dass ihr Speicher-
platz mit den Zwischenwerten überschrieben werden kann. Man spricht von einem
In-place-
Verfahren
.
Die Verknüpfung über Kreuz stellt die Basisoperation der Radix-2-FFT dar. Sie tritt in allen
Stufen auf. Bild 4-3 zeigt links die Basisoperation wie sie direkt aus dem Signalflussgrafen
abgelesen werden kann. Im Aussehen ausgebreiteten Schmetterlingsflügeln ähnlich, hat sich
für sie die englische Bezeichnung
Butterfly
durchgesetzt.
Die zwei komplexen Multiplikationen in Bild 4-3 links lassen sich auf eine zurückführen, da in
jeder Stufe
s
stets gilt
s
1
s
1
l
2
2
l
l
für
l
= 0, 1, …, 2
s
1
1
w
w
w
1
w
(4.13)
s
s
s
s
2
2
2
2
Damit erhält man den Butterfly in Bild 4-3 rechts.
Knoten
m
Knoten
m
Knoten
m
Knoten
m
w
2
s
w
s
1
m+
2
s
1
m+
2
s
1
m+
2
s
1
m+
2
s
1
1
w
2
2
s
s
Bild 4-3
Basisoperation (Butterfly) der Radix-2-FFT in der Stufe
s
mit zwei (links) bzw. einer (rechts)
komplexen Multiplikation mit
l
{0, 1, ... , 2
s
1
1}
2
In Bild 4-4 sind die Überlegungen zum Signalflussgrafen der
Decimation-in-time
(DIT)
-
Radix-2-FFT
zusammengefasst. Näherungsweise sind pro Stufe
N
/ 2 komplexe Multiplikation
und
N
komplexe Additionen bzw. Subtraktionen erforderlich. Im Vergleich mit Bild 4-2 redu-
ziert 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, so dass die Zahl der Multiplikationen noch etwas reduziert werden kann.
Für die FFT werden in der Literatur verschiedene Modifikationen vorgeschlagen, die je nach
Anwendung unterschiedlichen Zielvorstellungen gehorchen, wie kleiner 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, so dass sie besonders schnell ausgeführt werden kann. Beispielsweise warb eine
Anzeige für einen bekannten Signalprozessor im Dezember 2003 mit dem Versprechen eine
komplexe FFT der Länge 1024 in Gleitkomma-Arithmetik in ca. 17 Ps auszuführen, eine
