LNTwww

Ein Nachteil der direkten Berechnung der (im Allgemeinen komplexen) DFT–Zahlenfolgen

gemäß den in Kapitel 5.2 angegebenen Gleichungen ist der große Rechenaufwand. Beispielsweise kann dieser Aufwand für die Diskrete Fouriertransformation (DFT)

wie folgt abgeschätzt werden:

Wir gehen davon aus, dass die Potenzen des komplexen Drehfaktors w = exp(–j2π/N) bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.

Zur Berechnung eines einzelnen Koeffizienten benötigt man N – 1 komplexe Multiplikationen und ebenso viele komplexe Additionen.

Jede komplexe Addition erfordert zwei reelle Additionen:

Jede komplexe Multiplikation erfordert vier reelle Multiplikationen und zwei reelle Additionen (eine Subtraktion wird wie eine Addition behandelt):

Somit sind zur Berechnung aller N Koeffizienten die folgende Anzahl M reeller Multiplikationen und die Anzahl A reeller Additionen erforderlich:

In heutigen Rechnern benötigen Multiplikationen und Additionen/Subtraktionen etwa die gleiche Rechenzeit und es genügt, die Gesamtanzahl O = M + A aller Rechenoperationen zu betrachten:

Daraus folgt: Man benötigt bereits für eine DFT (oder eine IDFT) mit N = 1000 knapp 8 Millionen Rechenoperationen. Für N = 16 sind immer noch 1920 Rechenoperationen erforderlich.

Ist der Parameter N eine Potenz zur Basis 2, so können rechenzeitgünstigere Algorithmen angewandt werden. Die Vielzahl solcher aus der Literatur bekannten Verfahren werden unter dem Sammelbegriff Fast–Fouriertransformation – abgekürzt FFT – zusammengefasst. Alle diese Methoden basieren auf dem Überlagerungssatz der DFT.

Rechenaufwand der DFT bzw. IDFT