Digital Signal Processing Reference
In-Depth Information
Tabelle 4-2
Zuordnung der Indizes der Eingangs- bzw. Zwischenwerte zu den Basisoperationen
in den Stufen
s
des Radix-2-FFT-Signalflussgraphen für die DFT-Länge
N
= 8 und
die zugehörigen komplexen Faktoren
W
s
1
2
3
I
1
0
2
4
6
0
4
0
I
2
0
0
1
0
1
0
1
2
3
I
0
2
4
6
0
1
4
5
0
1
2
3
J
1
3
5
7
2
3
6
7
4
5
6
7
j
4
j
24
j
34
W
1
1
1
1
1
j
1
j
1
e
e
e
Eine mögliche Implementierung stellt der folgende Programmausschnitt vor. Dort wird die
Bearbeitung aller Basisoperationen durch die zwei ineinander geschachtelten
while
-Schleifen
mit
I
2
und
I
1
für die äußere bzw. innere Schleife sichergestellt. Letzteres fasst die Basis-
operationen mit gleichen komplexen Faktoren zusammen, was die Zahl der komplexen Multi-
plikationen etwas reduziert.
Programmbeispiel 4-2
Signalflussgraph-Implementierung I (Programmausschnitt)
%
flow graph DIT-Radix-2-FFT
for
S=1:log2(N)
%
number of stages of flow graph
L = 2^S;
LV2 = L/2;
I2 = 0;
W1 = 1;
W2 = exp(-j*pi/LV2);
while
(I2<LV2)
I1 = 0;
while
(I1<NM1)
I = I1 + I2 + 1;
%
+1 due to MATLAB indexing
J = I + LV2;
%
butterfly
T = X(J)*W1;
X(J) = X(I) - T;
X(I) = X(I) + T;
I1 = I1 + L;
end
I2 = I2 + 1;
W1 = W1 * W2;
end
end
FFT-Programme nach Cooley, Welch und Lewis reduzieren die Komplexität und damit die
Rechenzeit noch etwas, indem sie die Indexrechnung mit den
while
-Schleifen durch
for
-
Schleifen vereinfachen. Programmbeispiel 4-3 zeigt die überarbeitete Version. Dabei ist
berücksichtigt, dass die MATLAB-Indizierung mit 1 beginnt.
