Digital Signal Processing Reference
In-Depth Information
mk M
mk
mM
mk
w
w
w
w
MM
M
(4.12)
1
gilt
U
[0] =
U
[4],
U
[1] =
U
[5], usw. Die von
V
[0], ...,
V
[3] ausgehenden Pfade werden entspre-
chend (4.11) mit den Faktoren
w
gewichtet.
u
[0]
U
[0]
x
[0]
X
[0]
w
8
0
U
[1]
u
[1]
x
[2]
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]
v
[1]
x
[3]
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
Signalflussgraph der Radix-2-FFT der Länge
N
= 8 mit Aufteilung im Zeitbereich nach der
ersten Zerlegung mit den Zwischenergebnissen
U
[
k
] und
V
[
k
]
Die beiden weiteren Zerlegungen ergeben schließlich den dreistufigen Signalflussgraphen in
Bild 4-2. Er zeigt, dass in jeder Zerlegungsstufe jeweils
N
komplexe Multiplikationen und
komplexe Additionen benötigt werden. Ist die Transformationslänge eine Zweierpotenz
N
= 2
p
,
dann existieren genau
p
= log
2
(
N
) Zerlegungen. Der Rechenaufwand reduziert sich demzufolge
auf etwa 8
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) circa 8.4
Millionen FLOPs und nach Radix-2-Zerlegung nur 0.082 Millionen FLOPs, und damit um
zwei Größenordnungen weniger.
Eine genaue Analyse des Signalflussgraphen zeigt, dass die Komplexität weiter reduziert wer-
den kann. Man betrachte beispielsweise die Eingangswerte
x
[0] und
x
[4]. Aus ihnen werden
N
ohne Verwendung weiterer Eingangswerte
in der ersten Stufe genau zwei Zwischenwerte be-
rechnet. Die Eingangswerte werden danach zur DFT nicht mehr benötigt, sodass ihr Speicher-
platz mit den Zwischenwerten überschrieben werden kann. Man spricht von einem
In-place-
Verfahren
.
