Schnelle Fourier-Transformation - Digitale Signalverarbeitung mit MATLAB - page 51

Zusammenfassend lässt sich der beschriebene FFT-Algorithmus wie folgt charakterisieren:

1. Radix-2-FFT wenn die Transformationslänge eine Zweierpotenz ist

2. Decimation-in-time (DIT)-Zerlegung 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 unter Umständen durch
Anhängen von Nullen an das Signal, Zero-padding genannt, eine geeignete Länge eingestellt werden. (ii)
Eine alternative Form des Signalflussgraphen erhält man mit einer Gruppierung im Frequenzbereich, der
Decimation-in-frequency (DIF) -Zerlegung.

Programmbeispiel 4-3 Signalflussgraph Implementierung II (Programmausschnitt)

% flow graph DIT-Radix-2-FFT
for S=1:log2(N) % number of stages of flow graph

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
% butterfly
T = X(IP)*W1;
X(IP) = X(I) - T;
X(I) = X(I) + T;
end
W1 = W1 * W2;
end
end

4.4 Vorbereitende Aufgaben

A4.1 In der Versuchsdurchführung sollen Sie eine MATLAB-Funktion zur DIT-Radix-2-

FFT erstellen. Machen Sie sich mit den Programmbeispielen 4-1, 2 und 3 vertraut.

A4.2 In der Versuchsdurchführung sollen die Wachstumsgesetze des Rechenaufwands

(Zahl der FLOPs) der DFT in direkter Form mit dem Programm dft und des von
Ihnen erstellten FFT-Programms dit2fft verifiziert werden. MATLAB stellt
Befehle zur Zeitmessung während eines Programmablaufs zur Verfügung. Über-
legen Sie, wie Sie mit einer Zeitmessung die Wachstumsgesetze verifizieren können.

Machen Sie sich mit dem Programmbeispiel 4-4 vertraut.

Programmbeispiel 4-4 Wachstumsgesetz der Komplexität der DFT

% Elapsed time for the dft and the dit-2-fft algorithm
% dsplab4_1.m * mw * 13Oct2010
%% dft
M1 = [9 10 11 12 13]; % signal length 2^M for dft

M1 = 2.^M1;