Die schnelle Fourier-Transformation (FFT)

Bei der schnellen Fourier-Transformation (FFT) handelt es sich um einen Algorithmus zur Berechnung der DFT, der durch Anwendung des Divide and Conquer-Paradigmas eine Zeitkomplexität von $O(N \log N)$ erreicht. Im folgenden soll der iterative FFT-Algorithmus und seine Datenflußstruktur hergeleitet werden, da diese auch die Grundlage paralleler Implementierungen bilden.

Sei $N := 2^p > 1, p \in {\rule[0pt]{0.21mm}{8pt}\hspace*{0.08mm}{\sf N}}$ und $n := N/2$.

Die Berechnung der Komponenten $y_j$ wird getrennt für gerade und ungerade Indizes $j$ betrachtet. Ziel ist jeweils, die Berechnung der Komponenten $y_j$ auf die Berechnung einer DFT der halben Länge $n$ zurückzuführen.

Für $j = 0, \dots n-1$ gilt

$$y_{2j} = \sum_{k=0}^{N-1} x_k \omega_N^{2jk} = \sum_{k=0}^{n-1} (x_k \omega_N^{2jk} + x_{n+k} \omega_N^{2j(n+k)})$$ (7)

Um die beiden Summanden zusammenzufassen betrachten wir

$$\omega_N^{2j(n+k)} = \omega_N^{jN+2jk} = \omega_N^{2jk} = \omega_n^{jk}$$ (8)

Wir erhalten also

$$y_{2j} = \sum_{k=0}^{n-1} (x_k + x_{n+k}) \omega_n^{jk}$$ (9)

Analog erhalten wir für ungerade Indizes von y

$$y_{2j+1} = \sum_{k=0}^{N-1} x_k \omega_N^{(2j+1)k} = \sum_{k... ...n-1} (x_k \omega_N^{(2j+1)k} + x_{n+k} \omega_N^{(2j+1)(n+k)})$$ (10)

$$= \sum_{k=0}^{n-1} (x_k \omega_N^{2jk} \omega_N^k + x_{n+k} \omega_N^{2j(n+k)} \omega_N^{n+k})$$ (11)

Zum Zusammenfassen der Summanden benötigen wir noch, daß gilt

$$\omega_N^{n+k} = \omega_N^{N/2+k} = \cos(\frac{2\pi}N (N/2+k)) - i \sin(\frac{2\pi}N (N/2+k))\\$$ (12)

$$= \cos(\pi + \frac{2\pi}N k) - i \sin(\pi + \frac{2\pi}N k) = -\cos(\frac{2\pi}N k) + i \sin(\frac{2\pi}N k) = -\omega_N^k$$

Damit ergibt sich für diesen Fall

$$y_{2j+1} = \sum_{k=0}^{n-1} (x_k - x_{n+k}) \omega_N^k \quad \omega_n^{jk}$$ (13)

Die Gleichungen und zeigen, daß wir $(y_{2j})_{0 \leq j < n-1}^T$ durch die DFT der Länge n von $(x_j + x_{n+j})_{0 \leq j < n-1}^T$ und $(y_{2j+1})_{0 \leq j < n-1}^T$ durch die DFT von $((x_j - x_{n+j}) \omega_N^j)_{0 \leq j < n-1}^T$ erhalten. Für $n > 1$ läßt sich dieses Verfahren auf die beiden DFTs der Länge $n$ getrennt rekursiv anwenden.

Dieses Vorgehen führt zu einem Butterfly-Graph der Dimension ${\mbox{ld}\,}N$ zur Basis 2 als Datenflußgraph der FFT (Abbildung ).

Abbildung: Datenflußgraph der FFT ($N = 8$).

Im ersten Schritt ergeben sich folgende Funktionen in den Knoten

$$f_j^{(1)}(a, b) = \left\{ \begin{array}{ll} a+b & \mbox{fall... ...ega_{N}^{j-n} & \mbox{falls $n \leq j < N$} \end{array}\right.$$ (14)

Auf die Datenflußstruktur haben die Gewichte $\omega_{N}^{j-n}$ keine Auswirkung, so daß es im Folgenden ausreicht nur die beiden Typen

$$\begin{array}{ll} f_1(a, b) = a+b & \mbox{f\uml {u}r die ers... ...hbf{C}}& \mbox{f\uml {u}r die zweite H\uml {a}lfte} \end{array}$$ (15)

zu unterscheiden.

Durch das in jedem Schritt vorgenommene Anordnen der Ergebnisse zu geraden Indizes in der oberen Hälfte des betrachteten Ausschnitts, befindet sich das Ergebnis $y_j$ der DFT in der letzten Spalte in der durch die gespiegelte ${\mbox{ld}\,}N$-stellige Dualdarstellung von $j$ bestimmten Zeile (Bitreversal).