Digital Signal Processing Reference
In-Depth Information
20.4
Lösungen: Schnelle Fourier-Transformation
A4.2
Wachstum der Komplexität
Das Wachstum der Komplexität der DFT, in (4.3) abgeschätzt durch die Anzahl der
benötigten FLOPs, liefert einen quadratischen Anstieg mit zunehmender DFT-
Länge. Eine Verdopplung der DFT-Länge bedeutet demzufolge eine Vervierfachung
der Anzahl der FLOPs.
Für die DIT-Radix-2-FFT folgt mit der Abschätzung (4.14) ein im Wesentlichen
linearer Anstieg der Komplexität mit der DFT-Länge. Eine Verdopplung der DFT-
Länge bedeutet dann eine Verdopplung der Anzahl der FLOPs.
Nimmt man an, dass die bei der Ausführung des Algorithmus durch den Rechner
verbrauchte Zeit proportional zu der Anzahl der FLOPs ist, so sollte das lineare bzw.
quadratische Wachstum an den Rechenzeiten beobachtbar sein.
M4. 1
Programm für die DIT-Radix-2-FFT
function X = dit2fft(x)
% Computation oft the decimation-in-time radix-2 fft [OpSc75]
% function X = dit2fft(x)
% x : time-domain signal
% X : dft spectrum of x
% dit2fft.m * mw * 13Oct2010
X = x;
N = length(X);
NV2 = N/2; NM1 = N-1; J = 1;
%
Decimation in time (reverse ordering)
for I=1:NM1
if (I<J)
T = X(J);
X(J) = X(I);
X(I) = T;
end
K = NV2;
while (K<J)
J = J-K;
K = K/2;
end
J = J + K;
end
for S=1:log2(N)
%
Flow graph, number of decimation steps
L = 2^S;
LV2 = L/2;
W1 = 1;
W2 = exp(-j*pi/LV2);
for J=1:LV2
for I=J:L:N
IP = I + LV2;
T = X(IP)*W1;
%
Butterfly
X(IP) = X(I) - T;
X(I) = X(I) + T;
end
W1 = W1 * W2;
end
end
