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}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  den komplexen Drehfaktor. Für  $N = 8$  ergibt sich der 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$  für diesen komplexen Drehfaktor 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.

Hinweis:

• Die Aufgabe gehört zum Kapitel  Fast-Fouriertransformation (FFT).

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^{\hspace{0.04cm}\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}.$$