Digital Signal Processing Reference
In-Depth Information
auf etwa 8
N
log
2
(
N
) FLOPs. Das exponentielle Wachstum des Rechenaufwandes mit der DFT-
Länge ist nun durch ein, im Wesentlichen, lineares Wachstum ersetzt. Im Beispiel einer DFT-
Länge
N
= 1024 benötigt die Berechnung der DFT in der direkten Form (4.3) ca. 8,4 Millionen
FLOPs und nach Radix-2-Zerlegung nur 0,082 Millionen FLOPs, und damit um zwei Größen-
ordnungen weniger.
u
[0]
U
[0]
x
[0]
X
[0]
w
8
0
U
[1]
x
[2]
u
[1]
X
[1]
DFT
4
w
8
1
u
[2]
U
[2]
x
[4]
X
[2]
w
8
2
u
[3]
U
[3]
x
[6]
X
[3]
w
8
3
v
[0]
V
[0]
x
[1]
w
8
4
X
[4]
V
[1]
x
[3]
v
[1]
w
8
5
X
[5]
DFT
4
v
[2]
V
[2]
x
[5]
w
8
6
X
[6]
v
[3]
V
[3]
x
[7]
w
8
7
X
[7]
Bild 4-1
Signalflussgraf der Radix-2-FFT der Länge
N
= 8 mit Aufteilung im Zeitbereich nach erster
Zerlegung mit den Zwischenergebnissen
U
[
k
] und
V
[
k
]
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]
X
[6]
w
4
2
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 Signalflussgraf der Radix-2-FFT nach drei Zerlegungen mit Aufteilung im
Zeitbereich (
N
= 8)
