Digital Signal Processing Reference
In-Depth Information
In der Stufe
s
werden in den Butterflies jeweils die Eingangs- bzw. Zwischenwerte der Knoten
mit den Indizes
I
und
J
verknüpft. Dabei gilt aus Bild 4-4 für die Knoten der Zusammenhang
2
s
1
(4.16)
JI
Die Abhängigkeit des Index
I
von der Stufe
s
liefert der Ansatz
I
I
I
(4.17)
12
mit den Werten
s
s
s
s
I
02,12,22,32,
!
N
1
(4.18)
s
1
I
0,1, 2,
!
2
2
Man beachte die oberen Schranken für die Indizes. Die Zuordnung der Indizes zu den Basis-
operationen lässt sich für die DFT-Länge
N
= 8 anhand Tabelle 4-2 und Bild 4-4 anschaulich
nachvollziehen.
Ebenfalls in Tabelle 4-2 eingetragen sind die jeweils zugehörigen komplexen Faktoren
W
für
die Basisoperationen. Der Vergleich mit der Zeile für
I
2
zeigt den Zusammenhang
§
2
S
·
¹
W
exp
j
I
(4.19)
¨
¸
2
2
s
©
Damit sind zur Konstruktion des FFT-Programms alle notwendigen Bausteine bereitgelegt.
Tabelle 4-2
Zuordnung der Indizes der Eingangs- bzw. Zwischenwerte zu den Basisoperationen
in den Stufen
s
des Radix-2-FFT-Signalflussgraphen für die DFT-Länge
N
= 8 und
die zugehörigen komplexen Faktoren
W
s
1
2
3
I
1
0
2
4
6
0
4
0
I
2
0
0
1
0
1
0
1
2
3
I
0
2
4
6
0
1
4
5
0
1
2
3
J
1
3
5
7
2
3
6
7
4
5
6
7
j
S
4
j
24
S
j
34
S
W
1
1
1
1
1
j
1
j
1
e
e
e
Eine mögliche Implementierung stellt der folgende Programmausschnitt vor. Dort wird die
Bearbeitung aller Basisoperationen durch die zwei ineinander geschachtelten
while
-Schleifen
mit
I
2
und
I
1
für die äußere bzw. innere Schleife sichergestellt. Letzteres fasst die Basis-
operationen mit gleichen komplexen Faktoren zusammen, was die Zahl der komplexen Multi-
plikationen etwas reduziert.
