Digital Signal Processing Reference
In-Depth Information
x
[0]
X
[0]
w
2
0
w
4
0
w
8
0
x
[4]
X
[1]
w
2
1
w
4
1
w
8
1
x
[2]
X
[2]
w
4
2
w
2
0
w
8
2
X
[3]
w
4
3
x
[6]
w
2
1
w
8
3
w
8
4
x
[1]
X
[4]
w
2
0
w
4
0
w
8
5
X
[5]
w
2
1
x
[5]
w
4
1
w
8
6
x
[3]
w
4
2
X
[6]
w
2
0
w
4
3
w
8
7
x
[7]
X
[7]
w
2
1
1.
Stufe
2.
Stufe
3.
Stufe
Bild 4-2
Vorläufiger Signalflussgraph der Radix-2-FFT nach drei Zerlegungen mit Aufteilung im
Zeitbereich (
N
= 8)
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 Signalflussgraphen
abgelesen werden kann. Im Aussehen ausgebreiteten Schmetterlingsflügeln ähnlich, hat sich
für sie die englische Bezeichnung
Butterfly
durchgesetzt.
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
2
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}
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
w
w
w
1
w
1
(4.13)
s
s
s
s
2
2
2
2
Damit erhält man den Butterfly in Bild 4-3 rechts.
