Schemata zur FFT

Für den speziellen Fall N = 8 = 2³ sollen die dazugehörigen 3 Reduktionsschritte der FFT gemäß (19.221) und (19.223) im folgenden Schema 1 zusammengestellt werden:
Schema 1:

Die Zuordnung der gesuchten komplexen FOURIER-Koeffizienten zu den y-Werten des 3. Schrittes erkennt man, wenn man sich überlegt, wie in jedem Reduktionsschritt jeweils die Berechnung der Koeffizienten mit geraden und ungeraden Indizes erfolgt. In dem folgenden Schema 2 ist diese Verfahrensweise schematisch dargestellt.
Schema 2:

Schreibt man in Schema 1 die Koeffizienten auf und gibt man die Dualdarstellung ihrer Indizes vor dem ersten und nach dem dritten Reduktionsschritt an, dann erkennt man, daß die Reihenfolge der gesuchten Koeffizienten durch sogenannte Bitumkehr auf besonders einfache Weise ermittelt werden kann, wie in dem folgenden Schema 3 dargestellt ist.

Beispiel

Für die Funktion , die periodisch mit der Periode sein soll, werde mit Hilfe der FFT die diskrete FOURIER-Transformation durchgeführt. Man wähle . Mit
,
erhält man das folgende Schema 4:

Aus dem dritten (letzten) Reduktionsschritt erhält man die nachstehend aufgeführten gesuchten reellen FOURIER-Koeffizienten gemäß (19.218):

In diesem Beispiel kann man auch die allgemeine Eigenschaft

der diskreten komplexen FOURIER-Koeffizienten überprüfen.
Für k=1,2,3 sieht man, daß gilt: .