Digital Signal Processing Reference
In-Depth Information
Programmbeispiel 4-2
Signalflussgraf-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, wie z. B. in [OpSc95], reduzieren die Kom-
plexitä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 die MATLAB-Indizierung mit 1 beginnt.
Zusammenfassend lässt sich der beschriebene Algorithmus zur FFT wie folgt charakterisieren:
1.
Radix-2-FFT
)
wenn die Transformationslänge eine Zweierpotenz ist
2.
Decimation-in- time
(DIT)
)
wenn die Gruppierung im Zeitbereich erfolgt
3.
In-place-Verfahren
)
wenn während der Berechnung frei werdender
Speicherplatz überschrieben wird
Anmerkungen:
(i) Ist die Transformationslänge keine Zweierpotenz, kann u. U. durch Anhängen von
Nullen an das Signal, Zero-padding genannt, eine geeignete Länge eingestellt werden. (ii) Eine alternative
Form des Signalflussgrafen erhält man mit einer Gruppierung im Frequenzbereich, der
Decimation-in-
frequency
(DIF) -Algorithmus.
