Digital Signal Processing Reference
In-Depth Information
Die Substitutionen
nm
2
für
n
gerade
nm
2
1
für
n
ungerade
(4.5)
und
MN
2
liefern dann
M
1
M
1
21
mk
2
mk
N
Xk
x m w
2
x m
2
1
w
(4.6)
N
m
0
m
0
Berücksichtigt man noch die Umformungen für die komplexen Faktoren
2
mk
mk
w
w
(4.7)
N
M
und
2
mk
k mk
NM
(4.8)
w
w
w
N
so resultieren zwei Transformationen der halben Länge des Signals.
M
1
M
1
mk
k
mk
Xk
x m w
2
w
x m
2
1
w
(4.9)
MN
M
m
0
m
0
Ist die ursprüngliche DFT-Länge
N
eine Zweierpotenz, kann die Zerlegung Schritt für Schritt
weitergeführt werden, bis schließlich die DFT-Länge 2 erreicht ist.
Das folgende Beispiel für die DFT-Länge
N
= 8 zeigt die Methode auf. Es wird der
Signalfluss-
graph
der Radix-2-FFT entwickeln. Die erste Zerlegung (4.9) führt mit den Substitutionen
um
[]
x m
[2]
und
[]
vm
x m
[2
1]
für
m
= 0:
M
1
(4.10)
und
M
1
M
1
mk
k
mk
Xk
um w
w
vm w
M
N
M
(4.11)
m
0
m
0
Uk
Vk
auf den Signalflussgraphen in Bild 4-1. Beachten Sie auch, dass Pfadgewichte (Faktoren), falls
nicht angegeben, zu 1 angenommen werden.
Die Aufteilung der Eingangsfolge, englisch
Decimation-in-time decomposition
genannt, ergibt
sich unmittelbar aus der Substitution (4.10). Es wird zweimal eine DFT der Länge
M
=
N
/ 2 =
4 berechnet. Danach werden die DFT-Koeffizienten der Zwischenergebnisse entsprechend
(4.11) zusammengefasst. Dabei kann vorteilhaft deren Periodizität bzgl. des DFT-Index
k
be-
nutzt werden
.
Wegen
