Digital Signal Processing Reference
In-Depth Information
M
1
M
1
¦
¦
(2
mk
1)
2
mk
Xk
[]
x m w
[2 ]
x m
[2
1]
w
(4.6)
N
N
m
0
m
0
Berücksichtigt man noch die Umformungen für die komplexen Faktoren
2
mk
mk
ww
(4.7)
N
M
und
(2
1
mk
k k
NM
w
w
w
(4.8)
so resultieren zwei Transformationen der halben Länge des Signals.
M
1
M
1
¦
¦
mk
k
mk
Xk
[]
xmw
[2 ]
w
xm
[2
1]
w
(4.9)
M
N
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-
graf
der Radix-2-FFT entwickeln. Die erste Zerlegung (4.9) führt mit den Substitutionen
um
[]
x m
[2]
und
[]
vm
x m
[2
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 Signalflussgrafen 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
mk M
(
)
mk
mM
mk
w
w
w
w
M
MM
N
(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.
Die beiden weiteren Zerlegungen ergeben schließlich den dreistufigen Signalflussgrafen 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
