Schnelle Fourier-Transformation - Digitale Signalverarbeitung mit MATLAB - page 49

4.3.2 Signalverarbeitung im Signalflussgraphen

Nach dem Sortieren der Eingangsfolge kann die Signalverarbeitung entsprechend dem Signal-
flussgraphen in Bild 4-4 beginnen.
Für die Programmierung der Radix-2-FFT ist es vorteilhaft, die jeweiligen Werte der Para-
meter im Signalflussgraphen in Bild 4-4 bzw. in den Basisoperationen in Bild 4-9 in
allgemeiner Form anzugeben.
Die Indizes I und J bezeichnen die Knoten im Signalflussgraphen von oben nach unten. Die
Zählung beginnt mit dem Wert null.
Anmerkung: Die Indizes I und J hier haben nichts mit der Bit-reversal-Adressierung für x [ n ] in Bild 4-4
zu tun.

I I

L

w

2 s

J = I + 2 s 1

J

1

Bild 4-9 Basisoperation (Butterfly) der Radix-2-FFT in der Stufe s mit einer komplexen Multiplikation
mit L {0, 1, ..., 2 s 1

2 1} und den Ein- bzw. Ausgangsknoten I und J

In der Stufe s werden in den Butterflies jeweils die Eingangs- bzw. Zwischenwerte der Knoten
mit den Indizes I und J verknüpft. Dabei gilt aus Bild 4-4 für die Knoten der Zusammenhang

2 s

1

(4.16)

JI

Die Abhängigkeit des Index I von der Stufe s liefert der Ansatz

I II

(4.17)

12

mit den Werten

s s s s

I 02,12,22,32,

0,1, 2,

, N

1

(4.18)

s 1

I , 2

2

Man beachte die oberen Schranken für die Indizes. Die Zuordnung der Indizes zu den Basis-
operationen lässt sich für die DFT-Länge N = 8 anhand Tabelle 4-2 und Bild 4-4 anschaulich
nachvollziehen.
Ebenfalls in Tabelle 4-2 eingetragen sind die jeweils zugehörigen komplexen Faktoren W für
die Basisoperationen. Der Vergleich mit der Zeile für I 2 zeigt den Zusammenhang

2 !

W exp j I

(4.19)

" #

2

2 s

& '

Damit sind zur Konstruktion des FFT-Programms alle notwendigen Bausteine bereitgelegt.