Digital Signal Processing Reference
In-Depth Information
M4.3
Mit dem Programm
dsplab4_1
wurden die in Tabelle 20-1 angegebenen Rechen-
zeiten bestimmt. Die resultierenden Wachstumsfaktoren in der Tabelle von ungefähr
4 bzw. 2 bestätigen die Abschätzungen.
Die Grafik in Bild 20-7 bestätigt obige Aussagen anschaulich.
10
2
dft
dit2fft
10
1
10
0
10
-1
8
9
10
11
12
13
14
15
16
17
18
DFT length, log
2
(
N
)
o
Bild 20-7
CPU-Zeiten für die DFT (
dft
) und DIT-Radix-2-FFT (
dit2fft
) in Abhängigkeit von der
DFT-Länge (mit dem MATLAB-Befehl
cputime
geschätzte Werte, PC mit T2300-CPU,
1.66 GHz und 1 GB RAM)
M4.4
Für die DFT des Audiosignals der Dauer 1 s folgt mit der Abtastfrequenz
f
s
= 8 kHz
eine DFT-Länge
N
= 8000. Die nächstmögliche Radix-2-FFT-Länge ergibt sich zu
8192. Dafür ist mit der direkten DFT-Implementierung, dem Programm
dft
, eine
Rechenzeit von etwa 90 s mal 4.3, also ungefähr 6.5 Minuten zu veranschlagen.
Mit der DIT-Radix-2-FFT, dem Programm
dit2dft
, ist eine Rechenzeit von etwa
320 ms erforderlich.
Anmerkung:
Die DFT-Länge als Zweierpotenz
N
= 2
13
lässt sich durch Anfügen von Nullen
an das Audiosignal erzwingen, siehe Zero-padding in Abschnitt 5.2.5.
M4.5
Mit dem Programm
dsplab4_1b
wurde Bild 20-8 für die MATLAB-Built-in-
Funktion
fft
bestimmt.
In der logarithmischen Darstellung ist wieder der näherungsweise lineare Anstieg
der Rechenzeit mit dem Faktor 2 zu erkennen.
Anmerkungen:
(i) Beim erstmaligen Aufruf der Funktion können sich durch das Laden in den
Hauptspeicher merkliche Verzögerungen ergeben. (ii) Bei zu großen DFT-Längen wird der
Hauptspeicher ausgeschöpft und für die Auslagerungen auf eine Swap-Datei auf der Festplatte
viel zusätzliche Zeit verbrauchen kann. (iii) In der digitalen Bildverarbeitung ist die Effizienz
des FFT-Algorithmus von besonderer Bedeutung. Dort wird die FFT oft auf die Zeilen und
Spalten eines Bildes angewendet, was den Aufwand entsprechend steigert.
