Exercise 5.5Z: Complexity of the FFT

• Return to book

Letzte Stufe der FFT für $N=8$

Der FFT–Algorithmus (Fast Fourier Transform) realisiert eine Diskrete Fouriertransformation mit dem kleinstmöglichen Rechenaufwand, wenn der Parameter $N$ eine Zweierpotenz ist. Im Einzelnen sind zur Durchführung einer FFT folgende Rechenschritte notwendig:

• Die FFT geschieht in ${\rm log_2} \ N$ Stufen, wobei in jeder Stufe die genau gleiche Anzahl an Rechenoperationen durchzuführen ist.
• Die Grafik zeigt die dritte und letzte Stufe für das Beispiel $N = 8$. Man erkennt, dass in dieser und auch den anderen Stufen jeweils $N/2$ Basisoperationen durchzuführen sind.
• In jeder Basisoperation, die man häufig auch als Butterfly bezeichnet, werden aus den beiden komplexen Eingangsgrößen $E_1$ und $E_2$ zwei komplexe Ausgänge berechnet:

$$A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu},$$

$$A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$

• Hierbei bezeichnet $w = {\rm e}^{-{\rm j} 2\pi/N}$ den komplexen Drehfaktor. Für das Beispiel $N = 8$ hat dieser den Wert $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}.$
• Der Exponent $\mu$ dieses komplexen Drehfaktors kann alle ganzzahligen Werte zwischen $0$ und $N/2-1$ annehmen. Für $N = 8$ gilt:

$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j} \cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j} \cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$

Mit dieser Aufgabe sollen die für die FFT erforderliche Anzahl von Rechenoperationen $(\mathcal{O}_{\rm FFT})$ ermittelt und mit dem für die DFT angebbaren Wert $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$ verglichen werden.

Zu beachten ist:

• Sinnvollerweise werden die Potenzen von $w$ vor dem eigentlichen Algorithmus berechnet und in einer Lookup–Tabelle abgelegt. Die hierfür notwendigen Operationen sollen deshalb unberücksichtigt bleiben.
• Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.

Hinweise:

• Die Aufgabe gehört zum Kapitel Fast-Fouriertransformation (FFT).
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Wieviele reelle Additionen $(A_{\rm A})$ erfordert eine komplexe Addition?

$A_{\rm A} \hspace{0.3cm} = \ $

2

Wieviele reelle Additionen $(A_{\rm M})$ und Multiplikationen $(M_{\rm M})$ sind für eine komplexe Multiplikation erforderlich?

$A_{\rm M} \hspace{0.3cm} = \ $

$M_{\rm M} \hspace{0.2cm} = \ $

3

Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation („Butterfly”)?
Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?

$a_{\rm B} \hspace{0.32cm} = \ $

$m_{\rm B} \hspace{0.2cm} = \ $

4

Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation?

$\mathcal{O}_{\rm B} \ = \ $

5

Wieviele reelle Operationen $(\mathcal{O}_{\rm FFT})$ erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für $N = 16$ und $N = 1024$?

$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $

$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $

6

Wie groß ist der Zeitgewinn $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$ für $N = 16$ und $N = 1024$?

$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $

$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $

Musterlösung

Solution

(1)  Jede komplexe Addition erfordert zwei reelle Additionen:

$$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 + R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm} \hspace{0.15 cm}\underline{ A_{\rm A} = 2}\hspace{0.05cm}.$$

(2)  Eine jede komplexe Multiplikation benötigt vier reelle Multiplikationen und zwei reelle Additionen:

$$(R_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdot R_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdot I_1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} = 4} \hspace{0.05cm}.$$

(3)  Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^\mu$:

$$A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu},\hspace{0.5cm} A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$

Dies bedeutet eine komplexe Multiplikation und zwei komplexe Additionen:   $\hspace{0.15 cm}\underline{a_{\rm B} = 2, \hspace{0.2cm}m_{\rm B} = 1} \hspace{0.05cm}.$

(4)  Im Gegensatz zu den ersten Computern nimmt heute eine Multiplikation keine wesentlich größere Rechenzeit in Anspruch als eine Addition bzw. Subtraktion.

Mit den Ergebnissen der Teilaufgaben (1), (2) und (3) erhält man für die Gesamtzahl der Rechenoperationen:

$$\mathcal{O}_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M} +M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10} \hspace{0.05cm}.$$

(5)  Insgesamt gibt es ${\rm log_2} \ N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind:

$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot \mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$

$$\Rightarrow \hspace{0.3cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=16) = 5\cdot 16 \cdot 4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=1024) = 5\cdot 1024 \cdot 10 \hspace{0.15 cm}\underline{= 51200} \hspace{0.05cm}.$$

(6)  Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:

$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm log_2}\hspace{0.1cm}N}$$

$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot \frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164} \hspace{0.05cm}.$$