Die Grafik zeigt den Signalflussplan der DFT für das Beispiel N = 8, die aus den acht Zeitkoeffizienten d(0), … , d(7) die Spektralkoeffizienten D(0), … , D(7) ermittelt. Für diese gilt mit 0 ≤ μ ≤ 7:
wobei der komplexe Drehfaktor w = exp(–j2π/N) zu verwenden ist. Mit N = 8 ergibt sich exp(–jπ/4).
Am Eingang wird die alternierende ±1–Folge 〈d(ν)〉 angelegt. Nach der Bitumkehroperation ergibt sich daraus die Folge 〈b(κ)〉. Es gilt b(κ) = d(ν), wenn man ν als Dualzahl darstellt und die resultierenden 3 Bit als κ in umgekehrter Reihenfolge geschrieben werden.
Beispielsweise folgt aus ν = 1 (001) die Position κ = 4 (100), während d(2) an der gleichen Position 2 (010) verbleibt.
Der eigentliche FFT–Algorithmus geschieht für das Beispiel N = 8 in ld N = 3 Stufen (L = 1, 2, 3), wobei in jeder Stufe vier Basisoperationen – sog. Butterflies – durchzuführen sind. Die Werte am Ausgang der ersten Stufe werden in dieser Aufgabe mit X(0), … , X(7) bezeichnet, die der zweiten mit Y(0), … , Y(7). Nach der dritten und letzten Stufe sind alle Werte noch durch N zu dividieren.
Hinweis: Die Aufgabe bezieht sich auf den Theorieteil zuKapitel 5.5.
