Der dadurch beschriebene Algorithmus ist durch folgende Schritte gekennzeichnet:
-
Die Eingangsfolge 〈d(ν)〉 der Länge N wird in zwei Teilfolgen 〈d1(ν)〉 und 〈d2(ν)〉 jeweils halber Länge separiert (gelb bzw. grün hinterlegt). Mit 0 ≤ ν < N/2 ergeben sich die Folgeelemente
-
Die Ausgangsfolgen 〈D1(μ)〉 und 〈D2(μ)〉 der beiden Teilblöcke ergeben sich daraus jeweils durch eine eigene DFT, aber nun nur noch mit halber Länge N/2 = 8:
-
Die Ausgangswerte D2(μ) der unteren DFT (mit 0 ≤ μ < N/2) werden anschließend im rot umrandeten Block durch komplexe Drehfaktoren hinsichtlich ihrer Phasenlage verändert:
-
Jeder einzelne Butterfly im blau umrandeten Block liefert durch Addition bzw. Subtraktion zwei Elemente der gesuchten Ausgangsfolge. Mit
0 ≤ μ < N/2 gilt dabei:
Durch diese erste Anwendung des Überlagerungssatzes reduziert sich der Rechenaufwand etwa um die Hälfte. Man benötigt nun anstelle von O = 1920 reellen Rechenoperationen nur mehr
Der erste Summand berücksichtigt die Rechenoperationen der beiden DFT–Berechnungen mit N/2 = 8, der zweite die 8 komplexen Multiplikationen des Drehfaktors (roter Block) und der letzte Summand die 16 komplexen Additionen bzw. Subtraktionen des blau umrandeten Blocks.
