Numerische Berechnung der komplexen Fourier-Koeffizienten

Zur numerischen Bestimmung von c_k wendet man auf (19.216b) analog zu (19.207) und (19.208) die Trapezformel an und erhält die diskreten komplexen FOURIER-Koeffizienten :

mit

Der Zusammenhang (19.219a) unter Beachtung von (19.219b) wird dann als diskrete komplexe FOURIER-Transformation der Länge N der Werte bezeichnet.
Die Potenzen genügen sämtlich der Gleichung z^N=1. Sie werden deshalb auch als N-te Einheitswurzel bezeichnet. Wegen gilt:

Die effektive Berechnung der Summe (19.219a) ergibt sich aus der Tatsache, daß eine diskrete komplexe FOURIER-Transformation der Länge N=2n auf zwei Transformationen der Länge N/2=n in folgender Weise zurückgeführt werden kann:

a) Für alle Koeffizienten  mit geradem Index,

d.h. , erhält man:

Dabei wurde beachtet, daß ist. Substituiert man

und berücksichtigt man, daß gilt, dann ist

die diskrete komplexe FOURIER-Transformation der Werte mit der Länge .

b) Für alle Koeffizienten  mit ungeradem Index,

d.h. mit , erhält man analog:

Substituiert man

und beachtet man, daß auch hier gilt, dann ist

die diskrete komplexe FOURIER-Transformation der Werte mit der Länge .

Die Reduzierung gemäß a) und b), d.h. die Zurückführung einer diskreten komplexen FOURIER-Transformation auf jeweils zwei diskrete komplexe FOURIER-Transformationen der halben Länge, läßt sich fortsetzen, wenn N eine Potenz von 2 ist, d.h. wenn N = 2^p (p natürliche Zahl) gilt. Die p-malige Anwendung der Reduzierung wird als FFT bezeichnet. Da jeder Reduktionsschritt wegen (19.223) N/2 komplexe Multiplikationen erfordert, ist der Rechenaufwand bei der FFT von der Größenordnung